mediumTwo PointersPattern: Three Pointers / Segregation
Segmented Array Rearrangement Solution
Problem Statement
You are given an array of integers `values` where each element is either 0, 1, or 2. Rearrange the array such that all elements with value 0 come first, followed by elements with value 1, and then elements with value 2. This should be done in a single pass through the array.
Examples
Example 1:
Input:[2,0,2,1,1,0]
Output:[0,0,1,1,2,2]
Explanation: Shipment list rearranged with smalls first, then mediums, then larges
Example 2:
Input:[0,1,0,1,2,2,1,1,0,2,1,2]
Output:[0,0,0,1,1,1,1,1,2,2,2,2]
Explanation: Shipment list rearranged with smalls first, then mediums, then larges
Constraints
- 1 <= n <= 300
- arr[i] is either 0, 1, or 2.
Time: O(N) Space: O(1)
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).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.