Duplicates and Second Highest Interview Questions

Duplicates — Optimal: Hash set while walking; failed insert means duplicate found. Complexity: Time O(n) , Space O(n)

Duplicates — Follow-up: Sort and compare neighbors O(n log n) , or Floyd cycle on index mapping for O(1) space when values are 1..n with one duplicate.

Second-highest: Single pass tracking first and second max. Update second only when value is strictly between first and second.

I keep two variables, first and second, starting at negative infinity or null. For each number, if it is greater than first I shift first into second and update first. Else if it is greater than second and not equal to first I update second. Equal-to-first should not become second unless they want duplicates as second. I ask. One pass, O(1) extra memory. Sorting is easier and I would mention it, then do the one-pass because they asked for it.

The pigeonhole trick: negate the index abs(x)-1 when I see x. If it is already negative, x is a duplicate. I restore if I must not mutate, or I copy. This is O(n) time and O(1) extra. The hash-set version is simpler and O(n) extra. I would ask if mutation is allowed. I would not sort if they want linear time and they gave the 1..n constraint — that constraint is a hint.

XOR of all indices and values, or sum formula n(n+1)/2 minus the sum. XOR avoids overflow. Both are O(n) time O(1) extra. I would not sort unless n is tiny. If multiple numbers are missing I switch to a set or the negate-index trick depending on constraints. I state the assumption: exactly one missing.

Two pointers. Slow writes the next unique. Fast scans. When nums[fast] differs from nums[slow], I increment slow and copy. The new length is slow plus one. O(n) time O(1) extra. This only works because it is sorted. Unsorted unique would need a set or a sort first. I would mention I return the new length and that the tail garbage does not matter.