Find the Second Largest Number in an Array - Java

Category: Medium | Concepts used: Single-pass tracking, sorting alternative

---

Problem Statement

Given an array of integers, find the second largest distinct value.

Input : [3, 7, 1, 9, 4]      Output: 7
Input : [5, 5, 5]              Output: N/A (no second distinct value)

Examples (with edge scenarios)

#	Input	Output	Why
1	[3, 7, 1, 9, 4]	7	9 is largest, 7 is second largest
2	[5, 5, 5]	N/A	Only one distinct value — no valid “second largest”
3	[9, 9, 7]	7	Duplicates of the max don’t count as a “different” second largest
4	[5] (single element)	N/A	Not enough distinct values
5	[-1, -5, -3] (all negative)	-3	Careful: “-3 is greater than -5”

Common Fresher Mistake

Mistake	What happens	Fix
Sorting the array and picking arr[length-2]	Wrong if the array has duplicate max values (e.g., [9,9,7] → arr[length-2] gives 9, not 7)	Must specifically skip duplicates of the max, not just take the second-to-last sorted position
Initializing secondLargest = 0	Fails for all-negative arrays	Initialize using sentinel values like Integer.MIN_VALUE, or handle via the first two elements directly

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: The Championship Podium

Imagine you are managing the podium of a running tournament:

• You have two pedestals: 1st Place (largest) and 2nd Place (secondLargest). Both start empty.
• A runner with score 3 arrives. Since 1st Place is empty, they take it (largest = 3).
• A runner with score 7 arrives. They beat the 1st Place runner.
  • The runner at 1st Place is demoted to 2nd Place (secondLargest = 3).
  • The new runner takes 1st Place (largest = 7).
• A runner with score 1 arrives. They are slower than 2nd Place (3), so they are ignored.
• A runner with score 9 arrives. They beat the 1st Place runner (7).
  • The runner at 1st Place (7) is demoted to 2nd Place (secondLargest = 7).
  • The new runner takes 1st Place (largest = 9).
• A runner with score 4 arrives. They are slower than 1st Place (9) but faster than 2nd Place (7)? No, 4 is slower than 7, so they are ignored.
• Duplicate Runner: If a runner with score 9 arrives again: since we only care about distinct values, we don’t demote our current 2nd Place runner (7) — we ignore the duplicate because it doesn’t give us a new second-best value.

---

Solution 1 — Sort and Pick the Second-Last Distinct Value

Intuition

If everything is sorted smallest to largest, the largest value sits at the very end. But the “true” second largest isn’t necessarily right next to it if there are duplicates — so after sorting, we should scan backward from the end looking for the first value that’s different from the maximum.

import java.util.Arrays;

public class SecondLargestSort {
    public static Integer secondLargest(int[] arr) {
        int[] sorted = arr.clone();
        Arrays.sort(sorted);

int largest = sorted[sorted.length - 1];

// scan backward, skipping any duplicates of the largest value
        for (int i = sorted.length - 2; i >= 0; i--) {
            if (sorted[i] != largest) {
                return sorted[i];
            }
        }
        return null; // no distinct second value found
    }

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

Output:

7
7
null

Dry Run (arr = [9, 9, 7])

sorted = [7, 9, 9]
largest = 9 (last element)
i=1: sorted[1]=9 -> equals largest -> skip
i=0: sorted[0]=7 -> not equal to largest -> return 7

Interviewer’s take

Correct, but not efficient: sorting takes O(n log n), when this problem can actually be solved in a single O(n) pass. Interviewers will typically push for the optimized version next.

Follow-up questions you might get:

• “Can you do this in a single pass without sorting?” → leads to Solution 2.

---

Solution 2 — Single Pass, Track Largest and Second Largest Together (Recommended)

Intuition

Just like tracking a single “champion” (max) in one pass, we can track two champions at once: the current largest, and the current second largest. Walking through the array once: if a new number beats the largest, the old largest gets demoted to second largest, and the new number becomes largest. If a number doesn’t beat the largest but beats the second largest (and isn’t equal to the largest), it takes the second-largest spot.

public class SecondLargestSinglePass {
    public static Integer secondLargest(int[] arr) {
        Integer largest = null, secondLargest = null;

for (int num : arr) {
            if (largest == null || num > largest) {
                secondLargest = largest; // old largest gets demoted
                largest = num;             // new number becomes largest
            } else if (num != largest && (secondLargest == null || num > secondLargest)) {
                secondLargest = num;
            }
        }
        return secondLargest;
    }

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

Output:

7
7
null
-3

Dry Run (arr = [3, 7, 1, 9, 4])

Start: largest=null, secondLargest=null

num=3: largest==null -> secondLargest=null, largest=3
num=7: 7>3 -> secondLargest=3, largest=7
num=1: 1>7? no. 1!=7 && (secondLargest=3, 1>3? no) -> no change
num=9: 9>7 -> secondLargest=7, largest=9
num=4: 4>9? no. 4!=9 && (secondLargest=7, 4>7? no) -> no change

Final: largest=9, secondLargest=7

Dry Run (arr = [9, 9, 7]) — handling duplicates correctly

num=9: largest==null -> secondLargest=null, largest=9
num=9: 9>9? no. 9!=9? NO (equal!) -> condition fails -> no change (correctly ignores duplicate)
num=7: 7>9? no. 7!=9 && (secondLargest=null, so true) -> secondLargest=7

Final: largest=9, secondLargest=7  (duplicate of max correctly skipped)

Interviewer’s take

This is the preferred final answer — O(n) time, single pass, and correctly handles duplicates of the maximum value (a very common trap in this exact problem). The num != largest check is the key detail interviewers look for — many candidates forget it and get tripped up by arrays like [9, 9, 7].

Follow-up questions you might get:

• “What if the array has fewer than 2 distinct elements?” → Returns null (or however you choose to signal “not found”) — always ask the interviewer how they’d like this communicated (exception vs. sentinel value vs. Optional).
• “Why use Integer (boxed) instead of primitive int for the tracking variables?” → So we can use null to represent “not yet found,” which a primitive int can’t naturally express without a sentinel value like Integer.MIN_VALUE.

---

📊 Visual Flowchart

graph TD
    Start["Input Element num"] --> CheckL{"largest == null OR num > largest?"}
    CheckL -->|Yes| Demote["secondLargest = largest<br>largest = num"]
    CheckL -->|No| CheckEqual{"num == largest?"}
    CheckEqual -->|Yes| Skip["Ignore (Duplicate Max)"]
    CheckEqual -->|No| CheckSL{"secondLargest == null OR num > secondLargest?"}
    CheckSL -->|Yes| UpdateSL["secondLargest = num"]
    CheckSL -->|No| Skip

---

Final Verdict — Which Solution Should You Give?

Solution 1 (sort-based)  ──O(n log n)──►  Correct but not optimal
Solution 2 (single-pass tracking)  ──O(n)──►   PREFERRED FINAL ANSWER

• Solution 2 is the expected final answer. It’s efficient and specifically demonstrates awareness of the duplicate-max edge case.

---

Quick Recap

Approach	Time	Space	Handles duplicates of max?
Sort + scan	O(n log n)	O(n) for copy	Yes, if implemented carefully
Single-pass tracking	O(n)	O(1)	Yes