Practice/Google/Leetcode 75. Sort Colors

Leetcode 75. Sort Colors

CodingMust

Problem

Given an array containing only the integers 0, 1, and 2, rearrange the elements in-place so that all 0s appear first, followed by all 1s, and finally all 2s. The relative ordering within each group doesn't matter.

Your goal is to solve this with a single pass through the array and using only constant extra space. Do not use any built-in sorting functions.

Requirements

1. Modify the array in-place (do not create a new array)
2. Use only O(1) extra space
3. Complete the task in a single pass through the array (O(n) time)
4. Return the modified array

Constraints

• 1 ≤ arr.length ≤ 300
• arr[i] is either 0, 1, or 2
• Must achieve O(n) time complexity
• Must achieve O(1) space complexity

Examples

Example 1:

Input: arr = [2, 0, 1, 2, 1, 0] Output: [0, 0, 1, 1, 2, 2] Explanation: All 0s are moved to the beginning, 1s in the middle, and 2s at the end

Example 2:

Input: arr = [2, 0, 2, 1, 1, 0] Output: [0, 0, 1, 1, 2, 2] Explanation: The array is partitioned into three sections

Example 3:

Input: arr = [0] Output: [0] Explanation: Single element array is already sorted