Sum of Two Lowest Numbers

What they ask

Given an unsorted array of at least two positive integers, return the sum of the two smallest values. The obvious answer is to sort; the interviewer then asks for a single pass.

In the same session they typically add a sibling problem: move all zeros to the left of the array while keeping the order of the non-zero elements.

Examples

• [19, 5, 42, 2, 77] returns 7.
• [10, 343445353, 3453445, 3453545353453] returns 3453455.
• [3, 3, 1] returns 4 (duplicates allowed).

Zeros variant: [1, 0, 2, 0, 3] becomes [0, 0, 1, 2, 3].

Constraints

• 2 <= n <= 10^5, values fit in 64-bit integers.
• Target O(n) time and O(1) extra space.

What they look for

• Tracking min1 and min2 correctly when a new value is smaller than min1 (the old min1 must slide to min2).
• Tests for duplicates and for the minimum appearing last.
• For the zeros variant, a two-pointer in-place solution rather than building two arrays.