Finding the Second Largest Element — From Data Structures to Optimal Thinking

#dsa #programming #cpp #beginners

This problem looks simple, but it quietly tests pattern selection.
Here’s how I approached it — and what I learned about optimal thinking.

Problem Summary

Given an array, return the second largest distinct element.
If it doesn’t exist, return -1.

What I Tried — Priority Queue

Idea

Use a max-heap, remove the largest, then find the next distinct value.

Issue

Risk of accessing empty heap. O(n log n) time complexity. It Overkill Correct idea, heavy tool.

What I Tried — Set Approach

Code

set<int> s;
for(int x : arr) s.insert(x);

s.erase(prev(s.end())); // remove largest

if(!s.empty()) return *s.rbegin();
return -1;

Analysis

Handles duplicates automatically. Time: O(n log n) Extra data structure. Conceptually strong — not optimal.

What I Learned — Optimal Pattern (Single Pass)

Key Insight

You don’t need extra data structures. Just track two values.

✅ Optimal Solution

int getSecondLargest(vector<int>& arr) {
    int largest = -1, second = -1;

    for(int x : arr) {
        if(x > largest) {
            second = largest;
            largest = x;
        }
        else if(x < largest && x > second) {
            second = x;
        }
    }
    return second;
}

How This Works

largest keeps the maximum so far. Second keeps the best candidate below largest. Duplicates are naturally ignored

Complexity

Time: O(n)
Space: O(1)

This is the expected interview solution.

What I Learned

My thinking was correct — I identified distinct values. I used tools I already knew (set / heap). The optimal solution uses a greedy tracking pattern. Pattern mastery comes after exposure