Modified: August 02 2024

Description:

Given an array nums with n objects colored red, white, or blue, sort in-place so that objects of the same color are adjacent. Colors are integers 0, 1, and 2 respectively.

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

Basically, sort them in order without using the built-in sort function.

So I worked on this at work, and I got to a certain point where I was using a hash map to count the amount of times they went through, which I was able to make. However, I was having issues with sorting. I tried on my own for a while, I will try to get the code from my school LeetCode account and paste it here. Otherwise, I had a decent idea of what to do. I used ChatGPT to ask why my sorting wasn’t working, and it gave the best answer from LeetCode below:

class Solution:
	def sortColors(self, nums: List[int]) -> None:
		low, mid, high = 0, 0, len(nums) - 1

		while mid <= high:
			if nums[mid] == 0:
				nums[low], nums[mid] = nums[mid], nums[low]
				low += 1
				mid += 1
			elif nums[mid] == 1:
				mid += 1
			else:
				nums[mid], nums[high] = nums[high], nums[mid]
				high -= 1

This is a true two pointer approach, and it only kind of makes sense to me. I followed the code with some test cases and understood it, but I think it would be hard to explain without looking at notes.

One approach I preferred from another source was from a commentor who used counting the amount of zeros and ones, indexing to fill those in, then placing the rest with 2’s. Less efficient, but I think I prefer this way.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zeros, ones, n = 0, 0, len(nums)

        for num in nums:
            if num == 0:
                zeros += 1
            elif num == 1:
                ones += 1

        for i in range(0, zeros):
            nums[i] = 0
        for i in range(zeros, zeros + ones):
            nums[i] = 1
        for i in range(zeros + ones, n):
            nums[i] = 2