Find the Third-Largest Distinct Number in an Array - Java

Category: Medium | Concepts used: TreeSet, single-pass tracking (extended)

---

Problem Statement

Given an array, find the third largest distinct value.

Input : [3, 7, 1, 9, 4]      Output: 4
Input : [9, 9, 7, 7]           Output: N/A (only 2 distinct values)

Examples (with edge scenarios)

#	Input	Output	Why
1	[3, 7, 1, 9, 4]	4	9, 7, 4 are the top 3 distinct values
2	[9, 9, 7, 7]	N/A	Only 2 distinct values exist
3	[1, 2] (only 2 elements)	N/A	Not enough elements for a “third”
4	[5, 5, 5, 5]	N/A	Only 1 distinct value
5	[-1, -2, -3, -4]	-3	Third largest among negatives

Common Fresher Mistake

Mistake	What happens	Fix
Just doing arr[length-3] after sorting	Wrong with duplicates — could pick the same value twice	Must deduplicate before indexing, or track distinct values explicitly
Extending the “second largest” single-pass trick by just adding a third variable without care	Easy to make ordering mistakes (shifting variables incorrectly)	Carefully shift third ← second ← largest in the right order, like a 3-slot leaderboard

---

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: Arcade Leaderboard Shifting

Imagine you are updating the scoreboard at a gaming arcade for the top 3 ranks:

• You have three slots: Gold (first), Silver (second), and Bronze (third).
• If a player gets a new high score that beats Gold:
  • The previous Silver player is pushed down to Bronze.
  • The previous Gold player is pushed down to Silver.
  • The new high score takes the Gold position.
• If a player’s score doesn’t beat Gold but beats Silver:
  • The previous Silver player is pushed down to Bronze.
  • The new score takes the Silver position.
• If a player’s score only beats Bronze:
  • The new score replaces Bronze.
• Duplicate Scores: If a player ties with any of the current top 3 scores, you ignore it. We only care about distinct achievements!

---

Solution 1 — Using a TreeSet (Clean and Simple)

Intuition

A TreeSet automatically keeps its elements sorted and removes duplicates for free — both requirements we need here. So just dump all numbers into a TreeSet, and once it’s built, we can walk from the highest end and simply count down three steps.

import java.util.TreeSet;

public class ThirdLargestTreeSet {
    public static Integer thirdLargest(int[] arr) {
        TreeSet<Integer> distinctValues = new TreeSet<>();
        for (int num : arr) {
            distinctValues.add(num); // duplicates automatically ignored
        }

if (distinctValues.size() < 3) {
            return null; // not enough distinct values
        }

// TreeSet is sorted ascending; walk down from the top 3 times
        Integer result = null;
        var descendingIterator = distinctValues.descendingIterator();
        for (int i = 0; i < 3; i++) {
            result = descendingIterator.next();
        }
        return result;
    }

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

Output:

4
null

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

distinctValues (sorted) = [1, 3, 4, 7, 9]
size=5 >= 3, ok to proceed
descendingIterator: 9 -> 7 -> 4
After 3 steps, result = 4

Interviewer’s take

This is a clean, readable solution — TreeSet handles both “sorted” and “distinct” requirements in one data structure, which shows good knowledge of Java’s collection types. It’s O(n log n) due to the tree’s insert cost, which is acceptable for this problem, though a single-pass O(n) solution is more efficient (see Solution 2).

Follow-up questions you might get:

• “What’s the time complexity of building the TreeSet?” → O(n log n) — each insertion into a TreeSet is O(log n), done n times.
• “Can you avoid the log n factor?” → leads to Solution 2.

---

Solution 2 — Single Pass, Track Top 3 Distinct Values (Optimized)

Intuition

Extend the “track the champion(s)” idea from finding the second-largest — but now maintain three slots: first, second, third place. For every new number, check where it would rank among these three (if anywhere), and shift the lower-ranked values down accordingly — just like updating a small leaderboard.

public class ThirdLargestSinglePass {
    public static Integer thirdLargest(int[] arr) {
        Integer first = null, second = null, third = null;

for (int num : arr) {
            if (num == first || num == second || num == third) {
                continue; // skip duplicates of values already tracked
            }
            if (first == null || num > first) {
                third = second;
                second = first;
                first = num;
            } else if (second == null || num > second) {
                third = second;
                second = num;
            } else if (third == null || num > third) {
                third = num;
            }
        }
        return third;
    }

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

Output:

4
null

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

Start: first=null, second=null, third=null

num=3: first==null -> third=null,second=null,first=3
num=7: 7>3 -> third=null(old second),second=3(old first),first=7
num=1: not > first(7), not > second(3) [1>3? no]... 1>third? third==null -> third=1
num=9: 9>7 -> third=3(old second),second=7(old first),first=9
num=4: 4>9? no. 4>second(7)? no. 4>third(3)? yes -> third=4

Final: first=9, second=7, third=4

Interviewer’s take

This is the preferred optimized answer — O(n) time, single pass, no extra data structure overhead. It’s trickier to get the shifting logic exactly right, so walking through your dry run carefully in the interview (as shown above) is important to avoid off-by-one style mistakes.

Follow-up questions you might get:

• “How would you generalize this to find the K-th largest distinct value?” → For large K, a fixed number of tracking variables becomes unwieldy — better to use a min-heap of size K, which naturally generalizes this pattern (see follow-up problems on heaps).

---

📊 Visual Flowchart

graph TD
    Start["Input Element num"] --> DupCheck{"num == first OR num == second OR num == third?"}
    DupCheck -->|Yes| Skip["Skip (Duplicate)"]
    DupCheck -->|No| Check1{"first == null OR num > first?"}
    Check1 -->|Yes| Shift1["third = second<br>second = first<br>first = num"]
    Check1 -->|No| Check2{"second == null OR num > second?"}
    Check2 -->|Yes| Shift2["third = second<br>second = num"]
    Check2 -->|No| Check3{"third == null OR num > third?"}
    Check3 -->|Yes| Shift3["third = num"]
    Check3 -->|No| Skip

---

Final Verdict — Which Solution Should You Give?

• Solution 1 (TreeSet) is a great, readable answer — perfectly acceptable for most interviews, especially at a QA/fresher level.
• Solution 2 (single-pass) is the more optimized answer — offer it if asked to improve time complexity, but be careful to dry-run your shifting logic out loud to avoid mistakes.

---

Quick Recap

Approach	Time	Space	Interview Signal
TreeSet	O(n log n)	O(n)	Clean, good use of collections
Single-pass (3 tracking vars)	O(n)	O(1)	Optimized, but easy to get shifting logic wrong