Solution: Sort Colors
Let's solve the Sort Colors problem using the Two Pointers pattern.
Statement
Given an array, colors
, which contains a combination of the following three elements:

$0$ (representing red)

$1$ (representing white)

$2$ (representing blue)
Sort the array in place so that the elements of the same color are adjacent, with the colors in the order of red, white, and blue. To improve your problemsolving skills, do not utilize the builtin sort function.
Constraints:
 $1 \leq$
colors.length
$\leq$ 300 colors[i]
can only contain $0$s, $1$s, or $2$s.
Solution
So far, youâ€™ve probably brainstormed some approaches and have an idea of how to solve this problem. Letâ€™s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
The naive approach would be to sort the array. This would arrange the elements in the desired positions, i.e., $0$s, then $1$s, and lastly, $2$s. The time complexity of this approach would be $O(nlog(n))$, which is the time required to sort the array. The space complexity of this approach would be $O(1)$ since no extra space is being used.
Optimized approach using two pointers
The essence of the algorithm lies in efficiently partitioning the array into three sections corresponding to the colors red, white, and blue. We keep track of the boundaries of the red and blue sections while iterating through the array. Reds are kept on the left side of the array, while blues remain on the right side, with whites in between. When encountering a red ($0$), itâ€™s placed at the end of the red section, and when finding a blue ($2$), itâ€™s moved to the beginning of the blue section. Elements of value $1$ (white) remain in place. This process continues until all the colors are separated, ensuring proper grouping of colors.
To implement it, we use two pointers (start
and end
) to traverse the array from either end. They keep track of the red and blue elements, respectively. In addition, we maintain another pointer (current
) to keep track of the white elements. These pointers are used to traverse the array in one pass. They are initialized as follows:

start
: This pointer will initially point to the $0^{th}$ index of the array. 
current
: This pointer will initially point to the $0^{th}$ index of the array. 
end
: This pointer will initially point to the last index of the array.
Hereâ€™s how the algorithm works:

Condition 1: If
colors[current]
is0
, thecurrent
pointer points to red. Swap the elements ofcolors[current]
andcolors[start]
. Next, move both thestart
andcurrent
pointers one position forward. 
Condition 2: Otherwise, if
colors[current]
is1
, thecurrent
pointer points to white. Increment thecurrent
pointer by1
to analyze the next element. 
Condition 3: Otherwise,
colors[current]
will be2
, i.e., thecurrent
pointer points to blue. Swap the elements ofcolors[current]
andcolors[end]
. Next, move theend
pointer one position backward.Note: When we decrement the
end
pointer, thecurrent
pointer remains unchanged since it has to analyze the swapped element to determine if further swapping is required with thestart
pointer. 
The three steps above are repeated until the
end
pointer becomes less than thecurrent
pointer, i.e., no elements are left to swap.
Letâ€™s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ handson prep courses.