Segmented Array Rearrangement — Problem Statement & Solution Guide
Problem Description
Given an array of integers nums where each element is either 0, 1, or 2, rearrange the array in-place such that all elements with value 0 come first, followed by elements with value 1, and then elements with value 2. You must solve this problem in a single pass using O(1) extra space.
Examples
Input
nums = [2,0,2,1,1,0]
Output
[0,0,1,1,2,2]
Explanation: Step 1: Initialize three pointers - low = 0, mid = 0, high = 5. Step 2: nums[mid] is 2, swap nums[mid] with nums[high] (high becomes 4, array becomes [0,0,2,1,1,2]). Step 3: Process elements with mid pointer until mid > high. Final rearranged array is [0, 0, 1, 1, 2, 2].
Input
nums = [2,0,1]
Output
[0,1,2]
Explanation: Step 1: low = 0, mid = 0, high = 2. Step 2: nums[mid] is 2, swap nums[0] and nums[2] -> nums becomes [1, 0, 2], high becomes 1. Step 3: nums[mid] is 1, mid becomes 1. Step 4: nums[mid] is 0, swap nums[0] and nums[1] -> nums becomes [0, 1, 2], low becomes 1, mid becomes 2. Since mid > high, traversal terminates. Final array: [0, 1, 2].
Constraints
- 1 <= n <= 300
- arr[i] is either 0, 1, or 2.
Optimal Approach & Strategy
Three pointers: low, mid, high. Iterate with mid. If 0, swap with low and increment both. If 1, just increment mid. If 2, swap with high and decrement high. Time O(N), Space O(1).
Brute Force Approach
Count occurrences of 0, 1, 2 and then overwrite array. Requires two passes.
Verified Code Solutions
function solution(nums) {
let low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] === 0) {
[nums[low], nums[mid]] = [nums[mid], nums[low]];
low++;
mid++;
} else if (nums[mid] === 1) {
mid++;
} else {
[nums[mid], nums[high]] = [nums[high], nums[mid]];
high--;
}
}
return nums;
}#include <vector>
#include <utility>
class Solution {
public:
void solution(std::vector<int>& nums) {
int low = 0, mid = 0, high = nums.size() - 1;
while (mid <= high) {
if (nums[mid] == 0) {
std::swap(nums[low], nums[mid]);
low++;
mid++;
} else if (nums[mid] == 1) {
mid++;
} else {
std::swap(nums[mid], nums[high]);
high--;
}
}
}
};class Solution {
public void solution(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) {
int temp = nums[low];
nums[low] = nums[mid];
nums[mid] = temp;
low++;
mid++;
} else if (nums[mid] == 1) {
mid++;
} else {
int temp = nums[mid];
nums[mid] = nums[high];
nums[high] = temp;
high--;
}
}
}
}def solution(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return numsfunction solution(nums) {
let low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] === 0) {
[nums[low], nums[mid]] = [nums[mid], nums[low]];
low++;
mid++;
} else if (nums[mid] === 1) {
mid++;
} else {
[nums[mid], nums[high]] = [nums[high], nums[mid]];
high--;
}
}
return nums;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.