We’ll cover the following.
- Problem Statement
- Intuition
- Solution
- Code
- Time Complexity
- Space Complexity
Problem Statement
Given an array containing only 0s, 1s and 2s, sort the array in place. Note that you should treat the numbers as objects, hence we can’t count 0s, 1s and 2s to recreate the array. Also you are not supposed to use the library’s sort function for this problem.
Example 1
Input : 1 0 2 1 0
Output : 0 0 1 1 2
Example 2
Input : 2 2 0 1 2 0
Output : 0 0 1 2 2 2
Intuition:
The problem requires tracking the positions of 3 numbers only i.e the 0s, 1s and 2s. So we can track the smallest number(in this case 0) using one pointer and the greatest number using another pointer(in this case 2). So we can proceed with the two pointer technique.
Solution
We can use a Two Pointers approach while iterating through the array. Let’s say the two pointers are called low
and high
which are pointing to the first and the last element of the array respectively. So while iterating, we will move all 0s before low
and all 2s after high
so that in the end, all 1s will be between low
and high
.
Video Tutorial:
Code
Time Complexity:
The time complexity of the above algorithm will be O(N) as we are iterating the input array only once.
Space Complexity:
The algorithm runs in constant space O(1) as we are not using any auxiliary space proportional to our input size.
This article has been contributed by Ashmik Harinkhede