75. Sort Colors

Problem Statement

Pattern: Pattern Array Partitioning

---

Naive Solution

public void sortColors(int[] nums) {
	int[] freqs = new int[3];
	for (int num : nums) 
		freqs[num]++;
	int index = 0, color=0;
	for(int freq : freqs) {
		while(freq-- > 0)
			nums[index++] = color;
		color++;
	}
}

Notes

• Simple Solution, but we need to build a freq array. still a O(1) time and place solution. But we can do better

---

Dutch National Flag / 3 Way QuickSort / 3 Way Partition

public void sortColors (int[] nums){
	int zero = 0, two = nums.length-1, i = 0;
	// 'i' hasn't crossed 'two' partition
	while(i <= two) {
		if(nums[i] < 1) {
			// swap to the 'zero' partition
			swap(nums, i, zero);
			i++; zero++;
		}
		else if(nums[i] > 1) {
			// swap to the 'two' partition
			swap(nums, i, two);
			two--;
		}
		else i++;
	}
}

Notes

Check GFG Three Way Paritioning

• This is a specific implementation of the 3 way quicksort algorithm
  • zero and two pointers point to the partition of the array containing those respective element
  • we traverse the array from zero to two and swap suitable elements into those respective paritions
  • for more details Check GFG Three Way Paritioning 👈

Sort Array By Parity - LeetCode Move all negative numbers to beginning and positive to end with constant extra space - GeeksforGeeks