Solution: Sort Colors
Explore how to implement the two-pointer technique to sort an array containing three colors (0, 1, and 2) efficiently. Understand how to rearrange elements in place using the Dutch National Flag algorithm to achieve a single-pass O(n) time and O(1) space solution without built-in sorting functions.
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, and the final order is: red (0), then white (1), and then blue (2).
Note: You are not allowed to use any built-in sorting functions. The goal is to solve this efficiently without extra space.
Constraints:
colors.length...