How to find second largest number in an array in Java?

Question

I'm just practicing some MIT java assignments. But, I'm not sure how to find the second largest number. http://ocw.csail.mit.edu/f/13

  public class Marathon {
    public static void main(String[] arguments) {
        String[] names = { "Elena", "Thomas", "Hamilton", "Suzie", "Phil",
                "Matt", "Alex", "Emma", "John", "James", "Jane", "Emily",
                "Daniel", "Neda", "Aaron", "Kate" };

        int[] times = { 341, 273, 278, 329, 445, 402, 388, 275, 243, 334, 412,
                393, 299, 343, 317, 265 };

        for (int i = 0; i < names.length; i++) {
            System.out.println(names[i] + ": " + times[i]);
        }

        System.out.println();
        System.out.println("Largest Timing " + Largest(times));
        System.out.println();

    }

    public static int Largest(int[] times) {
        int maxValue = times[0];

        for (int i = 1; i < times.length; i++) {
            if (times[i] > maxValue) {
                maxValue = times[i];
            }
        }
        return maxValue;
    }

}

Sort the array largest to smallest and subscript the 2nd element? — alex
– alex, Commented Nov 13, 2012 at 1:17
Or just have two running maxValues, one greater than the other. — irrelephant
– irrelephant, Commented Nov 13, 2012 at 1:18
@alex, Sorting an array is overkill for finding min/max. The linear solution is pretty trivial. — jonvuri
– jonvuri, Commented Nov 13, 2012 at 1:21

sampson-chen · Accepted Answer · 2012-11-13 01:24:06Z

7

Instead of resorting to sorting the array, you can simply do the following:

Keep a largestValue and a secondLargestValue
Loop through the entire array once, for each element:
- Check to see if the current element is greater than largestValue:
  - If so, assign largestValue to secondLargestValue, then assign the current element to largestValue (think of it as shifting everything down by 1)
  - If not, check to see if the current element is greater than secondLargestValue
    - If so, assign the current element to secondLargestValue
    - If not, do nothing.

O(n) run time

O(1) space requirement

answered Nov 13, 2012 at 1:24

sampson-chen

47.7k13 gold badges87 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

AppSensei Over a year ago

wow, how do you guys come up with such logic... I feel so stupid lol. I need to keep practicing.

Hot Licks Over a year ago

Minor bug, see comment dasblinkin's post.

sampson-chen Over a year ago

@HotLicks I'm not seeing the bug :<

slashron Over a year ago

There is a minor glitch here, if the largest number is duplicated, both largest and second largest will be same value. To fix this modify the check like "currentElement > secondLargestValue && currentElement != largestValue"

Sergey Kalinichenko · Accepted Answer · 2012-11-13 01:24:51Z

3

Sorting the array simply to find an order statistics is too wasteful. You can find the second largest element by following an algorithm that resembles the one that you already have, with an additional variable representing the second largest number.

Currently, the next element could be larger than the max or equal to/smaller than the max, hence a single if is sufficient:

if (times[i] > maxValue) {
    maxValue = times[i];
}

With two variables to consider, the next element could be

Greater than the max - the max becomes second largest, and the next element becomes the max
Smaller than the max but greater than the second largest - the next element becomes second largest.

A special care must be taken about the initial state. Look at the first two items, and assign the larger one to the max and the smaller to the second largest; start looping at the element number three, if there is one.

Here is how you can code it:

if (times[i] > maxValue) {
    secondLargest = maxValue;
    maxValue = times[i];
} else if (times[i] > secondLargest) {
    secondLargest = times[i];
}

answered Nov 13, 2012 at 1:24

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

6 Comments

Hot Licks Over a year ago

Actually, this algorithm (as "coded") breaks down if you have multiple identical "largest" values. The "secondLargest" variable will end up the same as "largest", rather than reflecting the true second-largest. To do it right the second test needs to check for SMALLER than largest in addition to being LARGER than second-largest.

jonvuri Over a year ago

@HotLicks, That's not necessarily a bug. This problem deals with rankings (see the original problem linked), not with finding the next smallest unique value. In fact, even a mathematically correct "second max" algorithm would probably return the same result if we're dealing with a list, and not a set.

Hot Licks Over a year ago

@Kiyura -- I would argue that if an algorithm reports a "second largest" value that is the same as the "largest" value, it's broken. "Second largest" means that the value is smaller than "largest".

Sergey Kalinichenko Over a year ago

@HotLicks In the context of this problem where all numbers are distinct there is no need to deal with ties. If the logic to deal with ties is desired, an extra if would be necessary.

Hot Licks Over a year ago

In the context of this problem there's no need to write much code, beyond "int largest = 445; int secondLargest = 412;`.

|

Hot Licks · Accepted Answer · 2012-11-13 01:55:56Z

2

Generally speaking:

Have two values -- "largest" and "notQuite".

Initialize both to -9999 or whatever.

Scan through your list. If the number is larger than "largest", set "largest" to that number. But before you do that, copy the old "largest" value to "notQuite".

If, on the other hand, the number is smaller than "largest" but is larger than "notQuite", set "notQuite" to that number.

When you're done examining all the numbers, "notQuite" contains the second-largest.

And note that, as you fill in the above numbers, you can also keep a "largestIndex" and "notQuiteIndex" and fill those in with the corresponding array index values, so you can identify the "winning" value. Unfortunately, though, if there are multiple identical "largest" or "secondLargest" values the simple index scheme doesn't work and you need to keep a list of some sort.

edited Nov 13, 2012 at 1:55

answered Nov 13, 2012 at 1:23

Hot Licks

47.8k19 gold badges96 silver badges156 bronze badges

6 Comments

jonvuri Over a year ago

It's better to have a sentinel check for unset running values, or at least set them to Integer.MIN_VALUE.

Hot Licks Over a year ago

@Kiyura -- Yep. For many cases simply initializing to -1 will suffice. Depends on the nature of your data. The odd case would be a list that consisted entirely of MIN_VALUE entries, in which case the sentinel would be needed, as there would be no "second largest".

jonvuri Over a year ago

Why would that case need special treatment? If the list consists entirely of MIN_VALUE, and that's what you initialize your max and secondMax to, they will both be correct at the end.

Hot Licks Over a year ago

Depends on your definition of "second largest". Can they be the same??

jonvuri Over a year ago

In this problem, they correspond to rankings (specifically, times people get in a competition), so yes. In fact, they should be if multiple indices have the max value. i.e., "Depends on the nature of your data" ;)

|

Saurabh · Accepted Answer · 2015-02-03 07:15:26Z

2

private static int secLargest(int[] numbers) {
        int maxVal = 0;
        int nextMaxVal = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] > maxVal) {
                nextMaxVal = maxVal;
                maxVal = numbers[i];

            }
            if (numbers[i] < maxVal) {
                nextMaxVal = maxVal;
                maxVal = numbers[i];

            }
        }
        return nextMaxVal;

    }

answered Feb 3, 2015 at 7:15

Saurabh

9606 gold badges21 silver badges39 bronze badges

Comments

Deepak Sharma · Accepted Answer · 2014-06-26 10:55:39Z

1

    private void secondLargest(int arr[]){

    int maxOne=arr[0];
    int maxTwo=arr[1];

    for(int i=0;i<arr.length;i++){

        if(arr[i]>maxOne){

            maxTwo=maxOne;
            maxOne=arr[i];
        }else if (arr[i]>maxTwo) {

            maxTwo=arr[i];
        }

    }

    System.out.println(maxOne);
    System.out.println(maxTwo);
}

answered Jun 26, 2014 at 10:55

Deepak Sharma

5,0815 gold badges54 silver badges61 bronze badges

Comments

spenibus · Accepted Answer · 2015-10-21 20:38:45Z

0

int largest=time[0];
int secondLargest=largest;
for(int i=0;i<time.length;i++){
    if(time[i]>largest){
        secondLargest=largest;
        largest=time[i];
    }
    else if(secondLargest<time[i] && time[i]<largest || secondLargest>=largest)
        secondLargest=time[i];
}
return secondLargest;

edited Oct 21, 2015 at 20:38

spenibus

4,41911 gold badges28 silver badges36 bronze badges

answered Oct 21, 2015 at 20:19

Mircea Stefan

1

Comments

Draken · Accepted Answer · 2017-05-30 12:31:01Z

0

public void findMax(int a[]) {
    int large = Integer.MIN_VALUE;
    int secondLarge = Integer.MIN_VALUE;
    for (int i = 0; i < a.length; i++) {
        if (large < a[i]) {
            secondLarge = large;
            large = a[i];
        } else if (a[i] > secondLarge) {
            if (a[i] != large) {
                secondLarge = a[i];
            }
        }
    }
    System.out.println("Large number " + large + " Second Large  number " + secondLarge);
}

The above code has been tested with integer arrays having duplicate entries, negative values. Largest number and second largest number are retrieved in one pass. This code only fails if array only contains multiple copy of same number like {8,8,8,8} or having only one number.

edited May 30, 2017 at 12:31

Draken

3,19614 gold badges38 silver badges56 bronze badges

answered May 30, 2017 at 12:14

Rahul Chauhan

264 bronze badges

Comments

Lokesh Verma · Accepted Answer · 2019-05-12 03:10:40Z

It will also extract second largest number if largest number occours two times as well as in a single for loop.

import java.util.*;
public class SecondLargestInArray
{
    public static void main(String[] args)
    {
        int arr[] = {99,14,46,47,86,92,52,48,36,66,85,92};
        int largest = arr[0];
        int secondLargest = arr[0];
        System.out.println("The given array is:" );
        for (int i = 0; i < arr.length; i++)
        {
            System.out.print(arr[i]+"\t");
        }

        for (int i = 0; i < arr.length; i++)
        {
            if (arr[i] > largest)
            {
                secondLargest = largest;
                largest = arr[i];
            }
            else if((arr[i]<largest && arr[i]>secondLargest) || largest==secondLargest)
            {
                secondLargest=arr[i];
            }
        }
        System.out.println("\nLargest number is:" + largest);
        System.out.println("\nSecond largest number is:" + secondLargest);
    }
}

dinesh pazani · Accepted Answer · 2020-06-09 03:57:43Z

0

Find the second largest element in the given array:

public static void findSecondMax(){
        int[] arr = {3, 2, 20, 4, 1, 9, 6, 3, 8};

        int max = 0;
        int secondMax = 0;

        for(int i =0; i< arr.length; i++) {

            if(max < arr[i]) max = arr[i];

            if((max > arr[i]) && (secondMax < arr[i])) secondMax = arr[i];

        }

        System.out.println(secondMax);
    }

edited Jun 9, 2020 at 3:57

answered Jun 9, 2020 at 3:52

dinesh pazani

751 silver badge12 bronze badges

Comments

Dheeraj · Accepted Answer · 2021-12-18 07:47:05Z

0

public static void main (String args[]) {
    int [] arr = {1,4,3,10,4,8,20,5,33};
    int largest = 0;
    int secondLargest = 0;
    for (int x : arr) {
        if (x > largest) {
            secondLargest = largest;
            largest = x;
        }
        else if (x > secondLargest) {
            secondLargest = x;
        }
    }
    System.out.println("secondLargest:"+secondLargest);
}

answered Dec 18, 2021 at 7:47

Dheeraj

11 bronze badge

1 Comment

Community Over a year ago

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.

Mr X · Accepted Answer · 2021-12-21 04:32:44Z

0

Updated : Changed to Java.

class Main {
  public static void main(String[] args) {
    int a = Integer.MIN_VALUE;
    int b = Integer.MIN_VALUE;
    int[] arr = {44,6,43,8,9,-10,4,15,3,-30,23};

    for(int i=0; i < arr.length; i++){ 
        if( arr[i] > a || arr[i] > b ){
          if( a < b ) {
            a = arr[i];
          } else {
            b = arr[i];
          }
        }
    }  
    int secondLargest = a < b ? a : b;
    System.out.println(secondLargest);
  }
}

edited Dec 21, 2021 at 4:32

answered Jul 26, 2014 at 11:50

Mr X

1,7593 gold badges31 silver badges59 bronze badges

3 Comments

Wilfredo P Over a year ago

This answer not provide any help to OP, he is asking about JAVA not PHP.

Conscript Over a year ago

As you have mentioned, your answer is in PHP. Please take the time to convert it to Java as requested by OP.

Mr X Over a year ago

@Conscript Now it has been updated please upvote it as well.

Collectives™ on Stack Overflow

How to find second largest number in an array in Java?

11 Answers 11

4 Comments

6 Comments

6 Comments

Comments

Comments

Comments

Comments

Comments

Comments

1 Comment

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

11 Answers 11

4 Comments

6 Comments

6 Comments

Comments

Comments

Comments

Comments

Comments

Comments

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related