InternDoor

Sort a row of 0s, 1s and 2s

Easyarrays · two pointers · sorting

Reported in interviews at (where)

nums holds only the values 0, 1 and 2. Return it sorted from smallest to largest.

Try it in a single pass, swapping values inside the array, without counting them first and without a library sort.

Example 1
Input
nums = [2,0,1,2,0]
Output
[0,0,1,2,2]

The 0s go to the front, the 2s to the back, and the 1 stays in between.

Example 2
Input
nums = [1,1]
Output
[1,1]

Nothing needs to move.

Limits

  • 1 <= nums.length <= 100000
  • nums[i] is 0, 1 or 2

Hints

Hint 1

Keep three regions: 0s before low, 2s after high, and the part still unknown between mid and high.

Hint 2

Look at nums[mid]: a 0 is swapped to low, a 2 is swapped to high (do not move mid, the value that came back is unchecked), and a 1 just moves mid on.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.