Finding the Second Minimum Without Counting Duplicates

The second minimum must be strictly greater than the minimum

For the array [4, 1, 1, 3, 2], the minimum element is 1. The second minimum is not the second item with value 1, because that value is not distinct from the minimum. The answer is 2, the smallest value strictly greater than 1.

The word distinct changes the comparison. You are not looking for the second position in sorted order when equal values are allowed. You are looking for a different value that comes after the minimum in value order. Here, the distinct values are 1, 2, 3, and 4, so the second minimum is 2.

A new minimum moves the old minimum into second place

A one-pass scan can keep two candidates: min and second. Start with the first value 4 as min, with no distinct second candidate yet. When the next value 1 arrives, it is smaller than min, so the old min value 4 must move into second before min becomes 1.

int min = 4;
int second = 0;
bool hasSecond = false;

int x = 1;
if (x < min) {
    second = min;
    hasSecond = true;
    min = x;
}

The order of these assignments is part of the algorithm. If you write min = x first, the old value 4 is gone, and assigning second = min would store 1 instead. That would make second equal to the new minimum, which is not allowed.

Only strict comparisons keep duplicate minimum values out

After processing 4 and 1, the state is min = 1, second = 4, and hasSecond = true. The next value is another 1. It is not smaller than min, and it is not strictly greater than min, so it must be ignored. The duplicate cannot replace either candidate.

The remaining values use the second-candidate rule. A value x may replace second only when x > min and either no second candidate exists or x < second. For 3, both conditions hold, so second changes from 4 to 3. For 2, both conditions hold again, so second changes from 3 to 2.

if (x < min) {
    second = min;
    hasSecond = true;
    min = x;
} else if (x > min && (!hasSecond || x < second)) {
    second = x;
    hasSecond = true;
}

else if (______________________________) {
    second = x;
}

The answer is -1 until a distinct second candidate exists

The prefix containing only the first value 4 has a minimum but no distinct second minimum. There is no value to place in second, so the scan needs a separate hasSecond flag. This flag describes whether second contains a real array value; it is not inferred from the number stored in second.

Do not use -1 as an internal candidate. The array could contain values for which -1 would distort the comparisons, and a special output value should not be mixed with real data. Keep hasSecond false until a distinct value is found, then print second. If the scan ends while hasSecond is false, print -1.

if (hasSecond) {
    cout << second;
} else {
    cout << -1;
}

For [4, 1, 1, 3, 2], the candidates finish as min = 1, second = 2, and hasSecond = true. The duplicate 1 never becomes a candidate because it is not strictly greater than min. The final output is therefore 2, while a scan of a prefix with no distinct second value would output -1.