Start learning free

LESSON 201 OF 344 · SORTING

Find Second Largest in Java: Sort and Scan from the Back

Practice O(n log n) Read the full explanation

Given an array of integers, return the second largest value.

Example:

Input: nums = [2, 7, 11, 8, 11, 8, 3, 11]
Output: 8
Explanation: The maximum value is 11. The second largest value is 8.

Note:

You may assume the array contains at least two distinct values.


Follow up:

Could you solve this in one pass without sorting?


STEP 1 OF 5
    Ctrl + Enter to check

    JAVA · SORTING

    Find Second Largest in Java, explained

    Problem overview

    The method secondLargest receives an int[] called nums and returns the second largest value. "Value" matters: a number that appears several times still counts once. You may assume the array holds at least two distinct values.

    For nums = [2, 7, 11, 8, 11, 8, 3, 11] the largest value is 11, which appears three times. The next value down is 8, so the answer is 8. Returning the second element from the end of a sorted array would give 11 here, which is wrong.

    Approach: sort, then skip the maximum

    After sorting in ascending order, the largest value sits at the last index, nums.length - 1, and every copy of it forms a run at the end. The second largest value is the first element, walking backwards, that differs from the maximum. Duplicates of the maximum are skipped automatically, and the first different value is the next one down.

    On the example, sorting gives [2, 3, 7, 8, 8, 11, 11, 11]. The last element is 11. Walking back from index 6 you meet 11, 11 and then 8 at index 4. That is the answer.

    This costs O(n log n) because of the sort. The statement's follow-up asks for a single pass without sorting. That is possible by tracking the largest and second largest values while scanning once, but this lesson uses the sort because it is simpler to reason about.

    Step by step

    1. Sort the array. Arrays.sort(nums) orders an int[] ascending, in place. There is no descending option for primitive arrays, so you read from the back instead.
    2. Walk backwards. Start at nums.length - 2, the element just before the maximum, and count down to 0. The last index is the maximum itself, so there is no reason to look at it.
    3. Compare with the maximum. Inside the loop, check whether nums[i] differs from nums[nums.length - 1]. While the values are equal, you are still inside the run of maximums.
    4. Return the first different value. Because the array is sorted, that value is the largest one below the maximum.
    5. Add the fallback return. After the loop, return -1. It is only reached if every element equals the maximum, and the statement rules that case out. Java still requires every path through a method with a return type to end in a return or a throw, so the line has to be there.

    The solution in Java

    class Solution {
    public int secondLargest(int[] nums) {
        Arrays.sort(nums);
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] != nums[nums.length - 1]) {
                return nums[i];
            }
        }
        return -1;
    }
}

    The Java details worth a closer look:

    • Arrays.sort changes the caller's array. Arrays are objects, so the method receives a reference to the same array and sorts it in place. After the call, the caller's array is sorted. To keep the original order, sort a copy made with nums.clone() or Arrays.copyOf(nums, nums.length).
    • Comparing with != is fine here. The elements are primitive int values, so != compares the numbers themselves. With Integer objects it would compare references, and you would need equals.
    • The loop counts down. i-- with i >= 0 includes index 0. Writing i > 0 would skip the first element, which matters for [1, 2]: the answer is at index 0.
    • A missing return is a compile error. The compiler can't know that the guarantee about distinct values means the loop always returns, so the final return -1 is required.

    Complexity

    Time: O(n log n). Sorting dominates. The backward scan visits each element at most once, so it is O(n).

    Space: O(1) extra, apart from whatever working memory the library sort uses internally. The loop needs one integer. The sort rearranges the input array rather than building a new one.

    Edge cases and common mistakes

    • Taking nums[nums.length - 2] directly. This returns the second element from the end, not the second distinct value. For [5, 5, 1] it gives 5, while the answer is 1.
    • Only two elements. [1, 2] returns 1. The loop starts at index 0 and finds a value different from 2.
    • Negative numbers. [-3, -7, -3] returns -7. Sorting handles negatives like any other numbers.
    • Several repeated maximums at the end. [3, 3, 9, 9, 9] returns 3: the loop skips all three 9s.
    • Ending the loop at the wrong index. A condition like i > 0 skips the smallest element, which can be the answer.
    • Using -1 as a real answer. The fallback is not a valid result. The input is guaranteed to contain two distinct values, so a correct program never reaches it.

    Testing

    • [2, 7, 11, 8, 11, 8, 3, 11] gives 8.
    • [5, 5, 1] gives 1.
    • [1, 2] gives 1.
    • [-3, -7, -3] gives -7.
    • [3, 3, 9, 9, 9] gives 3.
    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free