Finding the Second Smallest Element
Apply the logic of the second largest problem to finding the second smallest element, mastering the inversion of conditions.
Inverting the Logic
Once you master finding the second largest element, finding the second smallest element is trivial. The logic is completely identical; you simply invert the mathematical conditions and the initializations.
Inverting Initializations
To find maximums, we initialize state variables to the smallest possible numbers. To find minimums, we must initialize state variables to the largest possible numbers.
int min = Integer.MAX_VALUE;
int second_min = Integer.MAX_VALUE;
Inverting Conditions
The one-pass logic works identically, just looking for smaller values instead of larger ones.
for (int current : array) {
if (current < min) {
second_min = min; // Old min gets demoted
min = current; // New absolute min
} else if (current < second_min && current != min) {
second_min = current; // Takes second place
}
}
Why Practice Both?
Interviewers frequently ask candidates to find the minimums specifically to see if they understand the initialization trap. If you initialize min to 0, and the array is [5, 10, 15], your algorithm will incorrectly return 0 as the minimum because none of the positive elements are smaller than 0.
The Takeaway
Algorithmic patterns are reusable. The "demotion" pattern used for maximums works perfectly for minimums. Always remember to invert your initializations (start high to go low) to prevent logical bugs when searching for minimums.
The structural logic is identical. The only differences are initializing variables to very large numbers instead of very small ones, and checking for < instead of >.
If you initialize 'min' to 0 and the array contains only positive numbers, the condition (current < min) will never trigger, and 0 will incorrectly be returned.
In Java, use Integer.MAX_VALUE. In C++, use INT_MAX from the <climits> library. In Python, use float('inf').
Yes. When a new absolute minimum is found, the previous minimum is 'demoted' to the second minimum position.
Exactly the same way. The second condition must explicitly include (current != min) to ensure duplicates of the absolute minimum are ignored.