The Two-Pass Algorithm for Finding the Second Largest
Learn how to optimize the second largest problem from O(N log N) to O(N) by traversing the array twice using the two-pass method.
Moving to Linear Time
Once you realize that sorting (O(N log N)) is too slow, the next logical step is to find a solution that runs in O(N) linear time. The easiest way to conceptualize this is the Two-Pass Method.
Pass 1: Find the Maximum
You cannot find the second largest if you don't know what the absolute largest is.
- Initialize a variable
maxto a very small number. - Loop through the array. If the current element is greater than
max, updatemax. When this loop finishes, you have the absolute maximum value.
Pass 2: Find the Second Maximum
Now that you know the highest score, you do a second loop to find the highest score that is not the absolute maximum.
- Initialize a variable
second_maxto a very small number. - Loop through the array again.
- If the current element is greater than
second_maxAND strictly less thanmax, updatesecond_max.
Time and Space Complexity
- Time: We loop through the array twice. O(N) + O(N) = O(2N). In Big O notation, we drop constants, so the final time complexity is O(N).
- Space: We only use two integer variables, so the space complexity is O(1).
The Takeaway
The Two-Pass algorithm is a perfectly valid and robust solution. It handles duplicates naturally because the second pass strictly ignores the absolute maximum value. While it can be optimized further into a single pass, understanding this intermediate step is vital for algorithmic problem-solving.
It is an algorithm that iterates entirely through a dataset exactly two times to achieve the final result.
It is O(2N), which simplifies to O(N) Linear Time in Big O notation, making it highly efficient.
During the second pass, the condition explicitly checks that the current number is strictly less than the maximum, automatically bypassing any duplicates of the max.
Yes, it is a great intermediate solution. However, after presenting it, the interviewer will almost certainly ask you to optimize it into a single pass.
The second pass will never find a number strictly less than the maximum. The 'second_max' variable will remain at its initial value, signaling no valid answer.