Coding

Sort an array of 0's 1's and 2's

Asked at

Microsoft

Nvidia

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array nums consisting of only 0, 1, or 2. Sort the array in non-decreasing order.

The sorting must be done in-place, without making a copy of the original array.

Input: nums = [1, 0, 2, 1, 0] Output: [0, 0, 1, 1, 2] Explanation: The nums array in sorted order has 2 zeroes, 2 ones and 1 two

Input: nums = [0, 0, 1, 1, 1] Output: [0, 0, 1, 1, 1] Explanation: The nums array in sorted order has 2 zeroes, 3 ones and zero twos

Input: nums = [1, 1, 2, 2, 1]

1 <= nums.length <= 105
nums consists of 0, 1 and 2 only.

cpp

class Solution {
public:
    void sortZeroOneTwo(vector<int>& nums) {
        
    }
};

java

class Solution {
    public void sortZeroOneTwo(int[] nums) {
        
    }
}

python

class Solution:
    def sortZeroOneTwo(self, nums):

javascript

class Solution {
    sortZeroOneTwo(nums) {

       }
}

csharp

public class Solution {
    public void SortZeroOneTwo(List<int> nums) {
        // User will write code here
    }
}

func sortZeroOneTwo(nums []int) {

}

Stuck? Show a way to structure it+

01Maintain low for next 0, mid for current unknown, and high for next 2.
02Swap 0 at mid with low and advance both.
03Advance mid for a 1.
04Swap 2 at mid with high and only move high.

Reference answer

Keep four regions: [0,low) are 0s, [low,mid) are 1s, [mid,high] unknown, and (high,n) are 2s. Inspect nums[mid]: for 0, swap with low, increment both; for 1, increment mid; for 2, swap with high and decrement high, but do not increment mid because the swapped-in value has not been classified. This Dutch National Flag algorithm is O(n) time and O(1) space. Its correctness follows from preserving those four regions after each branch, while the unknown interval shrinks whenever mid advances or high retreats. The algorithm remains safe when low==mid and when the array contains only one color. The common bug is advancing mid after a 2 swap: that skips classification of the element copied from the right.

Then expect these follow-ups

How would you partition around an arbitrary pivot?
Tests: generalization
Why is each element examined at most a constant number of times?
Tests: complexity proof

Hiring now

Nvidia has 1,936 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior System Software Engineer
India, Pune
Senior E2E Hardware Architect, AI Networking
Israel, Yokneam
Senior Software Engineer - Infrastructure
India, Pune

Or practice this question first

Next question