17. Find the Second Smallest Element

Difficulty:EasyPattern:Two-Value TrackingTime:O(n)Space:O(1)

Find the second smallest distinct element in an array without sorting it.

How It Works & Algorithmic Design

Maintain two values: the smallest and second smallest:

Initialize both to positive infinity.
For each value, if it is smaller than the current smallest, move the smallest value into second smallest.
Otherwise, if it is greater than the smallest but smaller than the second smallest, update second smallest.
Return null if a distinct second smallest value does not exist.

Why This Approach Works Best

Sorting would require $O(n \log n)$ time. Tracking two values allows a single $O(n)$ traversal with $O(1)$ extra space.

Example Walkthrough

Input: [8, 3, 5, 1, 4]

The smallest value is 1 and the second smallest distinct value is 3.

Tracking: smallest=1 | secondSmallest=3

The two smallest distinct values are tracked during one traversal.

Output: 3

3 is the second smallest distinct value.

Answer: Find second smallest

function secondSmallest(arr) {
  let first = Infinity;
  let second = Infinity;

  for (const x of arr) {
    if (x < first) {
      second = first;
      first = x;
    } else if (x > first && x < second) {
      second = x;
    }
  }

  return second === Infinity ? null : second;
}

💡 Track the two smallest distinct values during a single traversal.

Key Takeaways

Track the two smallest distinct values instead of sorting.
The condition x > first prevents duplicate minimum values from becoming second smallest.
The algorithm runs in O(n) time and O(1) space.