How do you solve Sort Colors on LeetCode?

Sort Colors (LeetCode #75) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding the constraints allows for more efficient algorithms.

What is the brute force solution for Sort Colors?

The brute force approach for Sort Colors is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves sorting the array using a simple sorting algorithm like bubble sort or selection sort. This method is straightforward but inefficient for larger arrays due to its high time complexity. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Sort Colors?

Sort Colors uses the following concepts: Array, Two Pointers, Sorting. The recommended patterns to study are: Two Pointers, In-Place Sorting.

What are the interview tips for Sort Colors?

Always clarify the problem constraints before jumping to a solution. Think about the trade-offs of different approaches. Practice explaining your thought process out loud as you code.

What are common mistakes when solving Sort Colors?

Not recognizing that the problem can be solved in one pass. Overcomplicating the solution by trying to use sorting libraries.

#75

Sort Colors

Medium

ArrayTwo PointersSortingTwo PointersIn-Place Sorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses the Dutch National Flag algorithm, which sorts the colors in a single pass with constant space. This method is efficient and leverages the fact that we know the exact values (0, 1, 2) we are sorting.

⚙️

Algorithm

3 steps

1Step 1: Initialize three pointers: low (for 0s), mid (for 1s), and high (for 2s).
2Step 2: Traverse the array with the mid pointer.
3Step 3: Depending on the value at mid, swap with low or high and move the respective pointers.

solution.py17 lines

1def sortColors(nums):
2    low, mid, high = 0, 0, len(nums) - 1
3    while mid <= high:
4        if nums[mid] == 0:
5            nums[low], nums[mid] = nums[mid], nums[low]
6            low += 1
7            mid += 1
8        elif nums[mid] == 1:
9            mid += 1
10        else:
11            nums[mid], nums[high] = nums[high], nums[mid]
12            high -= 1
13
14# Example usage
15nums = [2,0,2,1,1,0]
16sortColors(nums)
17print(nums)  # Output: [0,0,1,1,2,2]

ℹ

Complexity note: This complexity is linear because we traverse the array only once, making it very efficient. The space complexity is constant as we only use a few pointers.

1Understanding the constraints allows for more efficient algorithms.
2Using multiple pointers can significantly reduce time complexity.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.