Sort an array of 0's 1's and 2's
Microsoft
NvidiaThe 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
}
}go
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
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
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question