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