Sort Colors

                                            
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0, high = nums.size() - 1, i = 0;
        
        while (i <= high) {
            if (nums[i] == 0) {
                swap(nums[i], nums[low]);
                i++;
                low++;
            } else if (nums[i] == 2) {
                swap(nums[i], nums[high]);
                high--;
            } else {
                i++;
            }
        }
    }
};

                                            
class Solution {
    public void sortColors(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        int index = 0;

        while (index <= end) {
            if (nums[index] == 0) {
                int temp = nums[start];
                nums[start] = nums[index];
                nums[index] = temp;
                start++;
                index++;
            } else if (nums[index] == 2) {
                int temp = nums[end];
                nums[end] = nums[index];
                nums[index] = temp;
                end--;
            } else {
                index++;
            }
        }
    }
}

                                            
class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        """
        left, right, i = 0, len(nums) - 1, 0
        
        while i <= right:
            if nums[i] == 0:
                nums[left], nums[i] = nums[i], nums[left]
                left += 1
                i += 1
            elif nums[i] == 2:
                nums[right], nums[i] = nums[i], nums[right]
                right -= 1
            else:
                i += 1

                                            
void sortColors(int* nums, int numsSize) {
    int low = 0, high = numsSize - 1, i = 0;
    
    while (i <= high) {
        if (nums[i] == 0) {
            int temp = nums[low];
            nums[low] = nums[i];
            nums[i] = temp;
            low++;
            i++;
        } else if (nums[i] == 2) {
            int temp = nums[high];
            nums[high] = nums[i];
            nums[i] = temp;
            high--;
        } else {
            i++;
        }
    }
}

                                            
public class Solution {
    public void SortColors(int[] nums) {
        int low = 0;
        int high = nums.Length - 1;
        int i = 0;

        while (i <= high) {
            if (nums[i] == 0) {
                Swap(nums, i, low);
                i++;
                low++;
            } else if (nums[i] == 2) {
                Swap(nums, i, high);
                high--;
            } else {
                i++;
            }
        }
    }

    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify 
 * nums in-place instead.
 */
var sortColors = function(nums) {
    let low = 0;
    let high = nums.length - 1;
    let i = 0;

    while (i <= high) {
        if (nums[i] === 0) {
            [nums[i], nums[low]] = [nums[low], nums[i]];
            low++;
            i++;
        } else if (nums[i] === 2) {
            [nums[i], nums[high]] = [nums[high], nums[i]];
            high--;
        } else {
            i++;
        }
    }
};

                                            
/**
 Do not return anything, modify nums in-place 
instead.
 */
function sortColors(nums: number[]): void {
    let left = 0;
    let right = nums.length - 1;
    let i = 0;

    while (i <= right) {
        if (nums[i] === 0) {
            [nums[i], nums[left]] = [nums[left], nums[i]];
            left++;
            i++;
        } else if (nums[i] === 2) {
            [nums[i], nums[right]] = [nums[right], nums[i]];
            right--;
        } else {
            i++;
        }
    }
}

                                            
class Solution {
    /**
     * @param Integer[] $nums
     */
    function sortColors(&$nums) {
        $red = 0;
        $white = 0;
        $blue = count($nums) - 1;
        
        while ($white <= $blue) {
            if ($nums[$white] == 0) {
                $this->swap($nums, $white, $red);
                $white++;
                $red++;
            } elseif ($nums[$white] == 1) {
                $white++;
            } else {
                $this->swap($nums, $white, $blue);
                $blue--;
            }
        }
    }
    
    function swap(&$nums, $i, $j) {
        $temp = $nums[$i];
        $nums[$i] = $nums[$j];
        $nums[$j] = $temp;
    }
}

                                            
class Solution {
    func sortColors(_ nums: inout [Int]) {
        var low = 0
        var high = nums.count - 1
        var i = 0
        
        while i <= high {
            if nums[i] == 0 {
                nums.swapAt(i, low)
                low += 1
                i += 1
            } else if nums[i] == 2 {
                nums.swapAt(i, high)
                high -= 1
            } else {
                i += 1
            }
        }
    }
}

                                            
class Solution {
    fun sortColors(nums: IntArray): Unit {
        var low = 0
        var high = nums.size - 1
        var i = 0
        
        while (i <= high) {
            when {
                nums[i] == 0 -> {
                    nums[i] = nums[low]
                    nums[low] = 0
                    low++
                    i++
                }
                nums[i] == 1 -> {
                    i++
                }
                nums[i] == 2 -> {
                    nums[i] = nums[high]
                    nums[high] = 2
                    high--
                }
            }
        }
    }
}

                                            
class Solution {
  void sortColors(List<int> nums) {
    int low = 0;
    int high = nums.length - 1;
    int i = 0;
    
    while (i <= high) {
      if (nums[i] == 0) {
        int temp = nums[i];
        nums[i] = nums[low];
        nums[low] = temp;
        low++;
        i++;
      } else if (nums[i] == 2) {
        int temp = nums[i];
        nums[i] = nums[high];
        nums[high] = temp;
        high--;
      } else {
        i++;
      }
    }
  }
}

                                            
func sortColors(nums []int)  {
    low, high := 0, len(nums)-1
    i := 0
    for i <= high {
        if nums[i] == 0 {
            nums[i], nums[low] = nums[low], nums[i]
            low++
            i++
        } else if nums[i] == 2 {
            nums[i], nums[high] = nums[high], nums[i]
            high--
        } else {
            i++
        }
    }
}

                                            
# @param {Integer[]} nums
# @return {Void} Do not return anything, modify nums in-place instead.
def sort_colors(nums)
    left = 0
    right = nums.length - 1
    i = 0
    
    while i <= right
        if nums[i] == 0
            nums[i], nums[left] = nums[left], nums[i]
            left += 1
            i += 1
        elsif nums[i] == 2
            nums[i], nums[right] = nums[right], nums[i]
            right -= 1
        else
            i += 1
        end
    end
end

                                            
object Solution {
    def sortColors(nums: Array[Int]): Unit = {
        var low = 0
        var high = nums.length - 1
        var i = 0

        while (i <= high) {
            nums(i) match {
                case 0 =>
                    val temp = nums(i)
                    nums(i) = nums(low)
                    nums(low) = temp
                    i += 1
                    low += 1
                case 1 =>
                    i += 1
                case 2 =>
                    val temp = nums(i)
                    nums(i) = nums(high)
                    nums(high) = temp
                    high -= 1
            }
        }
    }
}

                                            
impl Solution {
    pub fn sort_colors(nums: &mut Vec<i32>) {
        let (mut left, mut right, mut current) = (0, nums.len() - 1, 0);
        
        while current <= right {
            if nums[current] == 0 {
                nums.swap(current, left);
                left += 1;
                current += 1;
            } else if nums[current] == 2 {
                nums.swap(current, right);
                if right == 0 {
                    break;
                }
                right -= 1;
            } else {
                current += 1;
            }
        }
    }
}

To solve this coding challenge, we need to sort an array of integers representing colors (0 for red, 1 for white, and 2 for blue) in a specific order: red, white, and blue. The challenge specifically requires an in-place solution and optimally, a one-pass algorithm with constant extra space. This can be achieved using the Dutch National Flag algorithm proposed by Edsger W. Dijkstra.

Explanation

The Dutch National Flag algorithm partitions the array into three parts:

All 0's (red) on the left.
All 1's (white) in the middle.
All 2's (blue) on the right.

We will use three pointers to achieve this:

left

pointer to track the boundary between 0's and the rest.
right

pointer to track the boundary between 2's and the rest.
i

pointer to go through each element in the array.

Initially,

left

is set to the beginning of the array,

right

is set to the end of the array, and

i

is used as an iterator that will go through each element. The general idea is that:

If
nums[i]

is 0, swap it with the element at the
left

pointer, then move both
left

and
i

pointers to the right.
If
nums[i]

is 2, swap it with the element at the
right

pointer, then move the
right

pointer to the left.
If
nums[i]

is 1, just move the
i

pointer to the right.

The loop continues until the

i

pointer surpasses the

right

pointer. This ensures that all elements are sorted in one pass with constant extra space (using only a few additional variables).

Here is the detailed pseudocode with explanations:

Initialize pointers :

                                            
left = 0         # Initialize `left` pointer to track the boundary for 0's
right = length(nums) - 1   # Initialize `right` pointer to track the boundary for 2's
i = 0             # `i` pointer to iterate through the array

While loop to process the array :

                                            
while i <= right:
if nums[i] == 0:
# Swap elements at `left` and `i`
temp = nums[left]
nums[left] = nums[i]
nums[i] = temp

# Move the `left` and `i` pointers to the right
left += 1
i += 1
elif nums[i] == 2:
# Swap elements at `right` and `i`
temp = nums[right]
nums[right] = nums[i]
nums[i] = temp

# Move the `right` pointer to the left
right -= 1
else:
# If the element is 1, just move the `i` pointer to the right
i += 1

End of the loop :

                                            
# At this point, the array is sorted in-place with all 0's at the beginning,
# followed by 1's, and all 2's at the end.

Step-by-Step Explanation of Pseudocode:

Initialization :

Set
left

to 0,
right

to the last index of the array, and
i

to 0.

Iteration and swapping :

The loop runs as long as
i

is less than or equal to
right

.
If
nums[i]

equals 0, the current element is a red color which should be moved to the front section. Swap this element with the element at the
left

pointer and move both
left

and
i

to the right.
If
nums[i]

equals 2, the element is blue which should be moved to the end section. Swap it with the element at the
right

pointer and move the
right

pointer to the left. Do not move the
i

pointer because the new element at index
i

needs to be checked.
If
nums[i]

equals 1, the element is white and already in the correct middle section, so simply move the
i

pointer to the right.

Completion :

When the while loop exits, the array will be sorted in the desired order.

By following this thought-out approach, one can effectively and efficiently sort the colors in the given array in a single pass with minimal extra space. This ensures both optimality and simplicity in addressing the problem requirements.