easyArray ProblemsJava

Find the Second Largest Element in an Array

Return the second largest distinct value in an integer array using a single pass.

Quick Answer

Keep two trackers, first and second, both starting at Integer.MIN_VALUE. For each element: if it beats first, push the old first down into second and set first to it; otherwise, if it sits strictly between second and first, update second. One pass gives the second largest distinct value while ignoring duplicate maximums.

Problem Statement

Given an array of integers, return its second largest distinct element. The "second largest" is the largest value that is strictly smaller than the maximum, so duplicate copies of the maximum do not count. Solve it in a single pass without sorting.

For example, in [3, 7, 2, 9, 4] the largest is 9 and the second largest is 7. In [10, 10, 5] the largest is 10 and the second largest is 5.

Input: An array of integers arr with at least two distinct values.

Output: The second largest distinct value in arr.

Examples

Example 1
Input:  [3, 7, 2, 9, 4]
Output: 7

9 is the largest; 7 is the largest value strictly below it.

Example 2
Input:  [10, 10, 5]
Output: 5

10 is the largest; the duplicate 10 is skipped, so the second largest is 5.

Constraints

  • arr contains at least two distinct values
  • Elements may be negative, zero, or positive

Think Before You Code

Reveal the questions to ask yourself first
  • How do you track two ranks at once as you scan?
  • When a new maximum appears, what happens to the old maximum?
  • How do you make sure a repeated maximum does not become the second largest?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
Use two variables, `first` and `second`, initialized to `Integer.MIN_VALUE`.
Hint 2
If the current value is greater than `first`, the old `first` becomes `second` and the value becomes the new `first`.
Hint 3
Otherwise only update `second` when the value is strictly less than `first` and greater than the current `second` — this skips duplicates of the maximum.

Approach

Reveal the step-by-step approach

Maintain the top two distinct values in one pass.

  1. Set first = Integer.MIN_VALUE and second = Integer.MIN_VALUE.
  2. For each x in the array:
    • If x > first: set second = first, then first = x.
    • Else if x > second and x < first: set second = x.
  3. Return second.

The x < first guard is what excludes duplicate maximums: a second copy of the largest value is neither greater than first nor allowed into second.

Dry Run

Walk through the example step by step

Finding the second largest in [3, 7, 2, 9, 4]:

start: first = MIN, second = MIN

x | x > first? | action                | first | second
--+------------+-----------------------+-------+-------
3 | yes        | second=MIN, first=3   | 3     | MIN
7 | yes        | second=3,  first=7    | 7     | 3
2 | no         | 2<7 & 2>3? no         | 7     | 3
9 | yes        | second=7,  first=9    | 9     | 7
4 | no         | 4<9 & 4>7? no         | 9     | 7
result: second = 7

Solution

Reveal the full Java solution
public class SecondLargest {
    public static int secondLargest(int[] arr) {
        int first = Integer.MIN_VALUE;
        int second = Integer.MIN_VALUE;
        for (int x : arr) {
            if (x > first) {
                second = first;
                first = x;
            } else if (x > second && x < first) {
                second = x;
            }
        }
        return second;
    }

    public static void main(String[] args) {
        System.out.println(secondLargest(new int[]{3, 7, 2, 9, 4})); // 7
        System.out.println(secondLargest(new int[]{10, 10, 5}));      // 5
    }
}

Two trackers move together so the answer comes from one linear pass rather than a sort. The x < first condition is the crucial detail: it prevents a repeated maximum from sliding into second, which is why [10, 10, 5] correctly returns 5 instead of 10.

Time: O(n) where n is the array lengthSpace: O(1)

Common Mistakes

  • Omitting the `x < first` check, so a duplicate of the maximum wrongly becomes the second largest.
  • Sorting the array just to read the second-from-last element, which is slower and mutates the input.

Edge Cases to Test

  • An array where the maximum repeats, like [10, 10, 5], must skip the duplicate.
  • Arrays containing negatives, like [-1, -2, -3], return the second largest negative (-2).
  • If no distinct second value exists (all elements equal), second stays Integer.MIN_VALUE — validate the input beforehand.

Interview Follow-Ups

  • How would you generalize this to the k-th largest element?
  • How would you handle the case where every element is identical?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us