Handling Arrays with Duplicate Elements
Learn how to prevent logical flaws when your algorithm encounters duplicate values while searching for the second largest element.
The Duplicate Trap
One of the most common reasons candidates fail basic array interviews is ignoring duplicate values. If an array is [10, 10, 5], what is the second largest element?
Mathematically, 10 is the largest, and 5 is the second largest. Duplicates do not take up the "second place" slot.
The Bug in Naive Code
If you write a simple check like this:
if (current > second_max) {
second_max = current;
}
When the loop hits the second 10, 10 is greater than second_max (which is 5). The code updates second_max to 10. Now, both your max and second max are 10. The logic has failed.
The Strict Inequality Fix
To properly handle duplicates, your second condition must enforce strict inequality.
if (current > second_max && current != max) {
second_max = current;
}
This simple current != max check ensures that a duplicate of the absolute maximum is completely ignored by the second place slot.
Complete Uniformity
What if the array is [7, 7, 7, 7]?
In this case, a second largest element doesn't exist. Your logic will safely ignore all the sevens. second_max will remain at its initial value (like -Infinity). At the end of the function, you should check if second_max is still -Infinity, and if so, throw an error or return -1 to indicate no valid answer exists.
The Takeaway
Edge cases involving duplicates are guaranteed to be tested by interviewers. Always trace your code's behavior when encountering identical, back-to-back maximum values.
If not explicitly ignored, a duplicate of the maximum value will overwrite the second largest variable, resulting in both variables holding the maximum value.
Add a logical AND condition (current != max) when evaluating whether to update the second largest variable.
It does not exist. The only distinct value is 5. Your code should recognize this and return a sentinel value like -1 or throw an exception.
If the current value equals the max, the first condition (current > max) fails. It falls to the second condition, which also fails because of the current != max check, safely ignoring the duplicate.
No, a simple boolean check (current != max) takes a microscopic fraction of a microsecond and has zero impact on the O(N) time complexity.