75. Sort Colors

Published on January 23, 2024

Question

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]

Algorithm

You cannot assume the amount of 0, 1, 2 are the same.
Basically the idea is to put the 0s at the left side and 2s at the right side, and the positions left in the middle are 1s
There should be a optimization that we can solve it without extra space, that is to do it in-place.
1. I was stuck at where to stop the iteration and swap-> it's index2.

Code

class Solution {
    public void sortColors(int[] nums) {
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = nums[i];
            nums[i] = 1;
        }
        int index0 = 0, index2 = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            if (res[i] == 0) {
                nums[index0++] = 0;
            } else if (res[i] == 2) {
                nums[index2--] = 2;
            }
        }
    }
}

class Solution {
    public void sortColors(int[] nums) {
        int index0 = 0, index2 = nums.length - 1;
        int index = 0;
        
        while (index <= index2) {
            if (nums[index] == 0) {
                swap(nums, index0--, index++);
            } else if (nums[index] == 2) {
                swap(nums, index2--, index++);
            } else {
                index++;
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}