How to Find Top Two Maximum Number from Integer array in Java

In this post, I have come with another simple programming problems for Java beginners. I love to share short programming problems because they help in developing programming sense. Many people will argue against simple problems like prime numbers, palindrome, and factorial, but I really find them useful, especially for beginners. A beginner is far away to solve a complex data structure problem or even more complex problems like those appear in TopCoder or other programming sites. Programmers learn gradually and they need the joy of doing something and seeing result much quickly than any other. Small success motivates them. Anyway, here is our problem statement, you need to write a Java program to find top two maximum numbers in the given array. You can not use any sorting functions and you should iterate the array only once. Use of any kind of collection class e.g. TreeSet or LinkedHashSet is also not allowed.

For example, if given integer array is [20, 34, 21, 87, 92, 2147483647] then first maximum is 2147483647 and second maximum is 92. Bonus points are for those, who can also write JUnit test cases, more test scenarios, more points.

Few more bonus points for those who can write code to deal with really large array, something which may not entirely fit on memory.





Java Program To Find Top Two Maximum Numbers from Integer Array

Calculate Top Two Maximum Numbers in Integer Array JavaHere is our sample Java program, It solves the problem following given problem statement and under constraints states. For example it doesn't use any sorting algorithm e.g. bubble sort or quicksort, or Collections.sort() method. As I said before,  this kind of program is good exercise for mastering basic building blocks of any programming language e.g. loops, if-else block and learning relational operator like less than (<) and greater than (>). It take advantage of if-else control statement to solve this problem. All we do is we start with two variables as max1 and max2 and initialized them with Integer.MIN_VALUE, which is the limit of minimum value. Now we iterate through array and compare each number against these two number, if current number is greater than max1 then max1 = number and max2 = max1. Otherwise if it only greater than max2 then we only update max2 with current number. At the end of iteration, max1 and max2 points to top two numbers from given array. You see problem solved without any utility class or third-party library.

import java.util.Arrays;
/**
 * Java program to find top two maximum numbers from an integer array. 
 * 
 * @author http://java67.blogspot.com
 */
public class TopTwoMaximum{

    public static void main(String args[]) {
        topTwo(new int[]{20, 34, 21, 87, 92, Integer.MAX_VALUE});
        topTwo(new int[]{0, Integer.MIN_VALUE, -2});
        topTwo(new int[]{Integer.MAX_VALUE, 0, Integer.MAX_VALUE});
        topTwo(new int[]{1, 1, 0});
    }

    public static void topTwo(int[] numbers) {
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        for (int number : numbers) {
            if (number > max1) {
                max2 = max1;
                max1 = number;
            } else if (number > max2) {
                max2 = number;
            }
        }

        System.out.println("Given integer array : " + Arrays.toString(numbers));
        System.out.println("First maximum number is : " + max1);
        System.out.println("Second maximum number is : " + max2);
    }

}

Output:
Given integer array : [20, 34, 21, 87, 92, 2147483647]
First maximum number is : 2147483647
Second maximum number is : 92
Given integer array : [0, -2147483648, -2]
First maximum number is : 0
Second maximum number is : -2
Given integer array : [2147483647, 0, 2147483647]
First maximum number is : 2147483647
Second maximum number is : 2147483647
Given integer array : [1, 1, 0]
First maximum number is : 1
Second maximum number is : 1

From output, you can see that our method topTwo(int[] numbers) are working properly for different set of inputs. I have choose main method over JUnit test for testing my code, which is quick and dirty. JUnit testing provides you more option and better framework to write testcases. If you don't know how to write JUnit test case, see that link. It explains that in details.

That's all on how to find two maximum from integer array in Java. How about extending it further and finding top three numbers from integer array? Can you do that without any help? Once you done that, You can probably try finding top three minimum numbers from array. For example if given array is [11, 2, 5, 4] then top three minimum numbers are 2, 4 and 5. You can even extend this logic even to find largest and smallest number in array, as shown in that example


10 comments:

  1. public static void topTwo2(int[] numbers) {
    Arrays.sort(numbers);

    System.out.println(numbers[numbers.length-2]);
    System.out.println(numbers[numbers.length-1]);

    }

    ReplyDelete
  2. public class TwoMaxNumbers {

    public static void main(String a[]){
    int[] A = { 1, 2, 3, 5, 8, 9, 4, 6 }; // answer should be 9 and8
    int top1 = 1;
    int top2 = 0;
    for (int i = 0; i < A.length; i++) {
    if (top1 < A[i]) {
    top2 = top1;
    top1 = A[i];
    }
    }
    System.out.println(top1 + " and " + top2);
    }

    }

    ReplyDelete
    Replies
    1. Your program will fail when highest number is in 2 place.
      e.g int[] A = { 1, 10, 3, 5, 1, 9, 4, 6 }
      your program will give output 10 and 1
      But expected output is 10 and 9

      Correct program would be:
      public static void main(String a[]){
      int[] A = { 1, 10, 3, 5, 1, 9, 4, 6 }; // answer should be 10 and 9
      int top1 = 1;
      int top2 = 0;
      for (int i = 0; i < A.length; i++) {
      if (top1 < A[i]) {
      top2 = top1;
      top1 = A[i];
      }
      else if (top2 < A[i]) {
      top2 = A[i];
      }
      }
      System.out.println(top1 + " and " + top2);
      }

      Delete
  3. That was my first option at first glance at the problem, but then I realized that there are at least 2 test-cases in which this method fails:

    1. Array contains only negative values -> In this case, the if condition will never be satisfied and the block inside the if block will never be executed, hence the top1 and top2 int will remain at their default values (1 and 0)
    2. The second largest number is after the largest number. In this case, when the second largest number comes into the loop, it if block statements will not execute because the if condition will verify if the current number checked (second number) is larger than the current largest number. This will return false, so the top2 int will not change, even though is is supposed to.

    ReplyDelete
  4. class maximum
    {
    public static void main(String a[])
    {
    int arr[]={10,13,15,4,34};
    int max1=arr[0];
    int max2;
    for(i=1;i<=arr.length();i++)
    {
    if(max1<arr[i])
    {
    max1=arr[i];
    max2=max1;
    }
    }
    System.out .println(max1+" "+max2);
    }
    }

    ReplyDelete
  5. when I provide duplicate numbers, first and second maximum values become the same:
    Given integer array : [1, 1, 2, 2, 4, 4, 5, 5, 3]
    First maximum number is : 5
    Second maximum number is : 5

    we can modify the else if like the following:

    public static void topTwo(int[] numbers) {
    int max1 = Integer.MIN_VALUE;
    int max2 = Integer.MIN_VALUE;
    for (int number : numbers) {
    if (number > max1) {
    max2 = max1;
    max1 = number;
    } else if (number > max2 && number!=max1) {
    max2 = number;
    }
    }

    System.out.println("Given integer array : " + Arrays.toString(numbers));
    System.out.println("First maximum number is : " + max1);
    System.out.println("Second maximum number is : " + max2);
    }


    ReplyDelete
    Replies
    1. @Can, thanks for handling duplicates, good work.

      Delete
  6. public static void getTopTwoMax(int[] arr){
    int firstMax , secondMax ;
    if(arr[0]>arr[1]){
    firstMax=arr[0];
    secondMax=arr[1];
    }
    else{
    firstMax=arr[1];
    secondMax=arr[0];
    }

    for(int i=2;ifirstMax ){
    firstMax= arr[i];
    }
    if(arr[i]>secondMax&&arr[i]<firstMax){
    secondMax= arr[i];
    }
    }
    System.out.println("FirstMax="+firstMax+" SecondMax="+secondMax);

    }

    ReplyDelete
  7. public class test17 {

    public static void main(String[] args)
    {
    int[] numbers={45,23,56,23,56,4,89,4,3};
    int intTopElement=numbers[0];
    int intSecondTopElement=numbers[0];
    for(int i=0;iintTopElement)
    {
    intSecondTopElement=intTopElement;
    intTopElement=numbers[i];
    }
    }
    System.out.println("Top Element: "+ intTopElement);
    System.out.println("Second Top Element: "+intSecondTopElement);
    }

    }

    ReplyDelete