09. Find the Second Largest Element

Difficulty:EasyPattern:Single Pass TrackingTime:O(n)Space:O(1)

Find the second largest distinct element in an array without sorting.

How It Works & Algorithmic Design

This uses a Dual-Variable Tracking approach in a single pass:

Variables: Maintain first (largest) and second (second largest), initialized to negative infinity (-Infinity).
Iteration & Rules: Loop through each number $x$:
- Case 1 ($x > first$): A new maximum is found. Demote the old first to second (second = first), then update first = x.
- Case 2 ($x > second$ and $x < first$): $x$ is not the largest, but is strictly greater than second. Update second = x.
- Case 3 ($x \le second$): Ignore $x$.
Distinct Constraint: The check x < first in Case 2 ensures duplicates of the maximum value do not improperly overwrite second.
Result: If second remains -Infinity, no distinct second largest element exists; return null.

Why This Approach Works Best

Sorting takes $O(n \log n)$ time. Scanning twice (once for max, once for second max) takes $O(2n)$ time. This dual-variable method finds the answer in a single $O(n)$ pass using $O(1)$ memory.

Example Walkthrough

Input: [12, 35, 1, 10, 34, 1]

Unsorted array with distinct elements.

Execution Trace: Check 12 (first=12) -> Check 35 (second=12, first=35) -> Check 1 -> Check 10 -> Check 34 (second=34) -> Check 1

Tracks both top distinct values simultaneously.

Output: 34

34 is the second largest distinct element.

Answer: Find second largest distinct element

function secondLargest(arr) {
  let first = -Infinity;
  let second = -Infinity;
  for (const x of arr) {
    if (x > first) {
      second = first;
      first = x;
    } else if (x > second && x < first) {
      second = x;
    }
  }
  return second === -Infinity ? null : second;
}

💡 Track the top two distinct maximum values simultaneously in one traversal.

Key Takeaways

Demote first to second whenever a new maximum is found.
Ensure duplicates of the max value do not overwrite second by checking x < first.
Solves the problem in a single pass ($O(n)$ time) without extra space ($O(1)$ memory).