{x}
blog image

Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

 

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

 

Constraints:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] is either 0, 1, or 2.

 

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Solution Explanation: Sorting Colors (LeetCode 75)

This problem requires sorting an array of integers representing colors (0 for red, 1 for white, 2 for blue) in-place, without using a sorting function. The optimal solution uses a three-pointer approach for a single-pass, constant-space solution.

Approach: Three Pointers

We employ three pointers:

  • i: Tracks the index of the last '0' (red) encountered. It starts at -1 (no '0's initially).
  • j: Tracks the index of the first '2' (blue) encountered. It starts at n (the array's length – beyond the last element).
  • k: Iterates through the array, examining each element. It starts at 0.

The algorithm proceeds as follows:

  1. Iteration: The while k < j loop iterates through the array. This condition ensures we don't go past the j pointer (which marks the beginning of unsorted '2's).

  2. Case 1: nums[k] == 0 (Red): If we find a '0', it needs to be moved to the left (before the '1's and '2's). We swap nums[k] with nums[i+1], effectively placing the '0' at the correct position. Both i and k are incremented because we've placed a '0' correctly and need to check the next element.

  3. Case 2: nums[k] == 2 (Blue): If we find a '2', it needs to be moved to the right (after the '0's and '1's). We swap nums[k] with nums[j-1], moving the '2' to the right end of the unsorted region. Only j is decremented because k remains unchanged; we need to check the element that swapped into position k.

  4. Case 3: nums[k] == 1 (White): If we find a '1', it's already in its correct sorted position (between the '0's and '2's). Thus, only k is incremented.

After the loop finishes, the array will be sorted in the order 0, 1, 2.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the array. We perform a single pass through the array.
  • Space Complexity: O(1). We only use a constant amount of extra space for the three pointers.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, C#)

The code examples in various languages are provided in the original response. They all implement the same three-pointer algorithm, showcasing its concise and efficient nature. The swap function (present in some examples) simply exchanges the values at two array indices.

This three-pointer technique cleverly avoids nested loops, resulting in an optimal solution that is both efficient and elegant.