HomeLeetcode75. Sort Colors - Leetcode Solutions
Leetcode

75. Sort Colors – Leetcode Solutions

Declan Clarke

Description:

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.

Examples:

Example 1:

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

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

Solution in Python:

Python
from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # Initialize pointers for the current element (mid),
        # the boundary for zeros (low), and the boundary for twos (high).
        low, mid, high = 0, 0, len(nums) - 1
        
        # Process elements in the array
        while mid <= high:
            if nums[mid] == 0:
                # Swap the mid element with the low element
                nums[low], nums[mid] = nums[mid], nums[low]
                # Increment both low and mid pointers
                low += 1
                mid += 1
            elif nums[mid] == 1:
                # If the element is 1, just move the mid pointer
                mid += 1
            else:
                # Swap the mid element with the high element
                nums[high], nums[mid] = nums[mid], nums[high]
                # Decrement the high pointer
                high -= 1

Explanation:

  1. Initialization:
    • low: Pointer to the boundary of the next position for 0.
    • mid: Pointer to the current element being processed.
    • high: Pointer to the boundary of the next position for 2.
  2. Traversal:
    • The algorithm processes the elements while mid <= high.
  3. Conditions:
    • If nums[mid] == 0:
      • Swap the element at mid with the element at low.
      • Increment both low and mid because the element at mid is now sorted.
    • If nums[mid] == 1:
      • Move the mid pointer because 1 is already in the correct position.
    • If nums[mid] == 2:
      • Swap the element at mid with the element at high.
      • Decrement high because the element at mid needs to be checked again.

This approach ensures that all 0s are moved to the beginning, all 2s to the end, and all 1s remain in the middle in a single pass with constant space complexity.

Solution in Javascript:

JavaScript
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    // Initialize pointers for the current element (mid),
    // the boundary for zeros (low), and the boundary for twos (high).
    let low = 0;
    let mid = 0;
    let high = nums.length - 1;
    
    // Process elements in the array
    while (mid <= high) {
        if (nums[mid] === 0) {
            // Swap the mid element with the low element
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            // Increment both low and mid pointers
            low++;
            mid++;
        } else if (nums[mid] === 1) {
            // If the element is 1, just move the mid pointer
            mid++;
        } else {
            // Swap the mid element with the high element
            [nums[high], nums[mid]] = [nums[mid], nums[high]];
            // Decrement the high pointer
            high--;
        }
    }
};

Solution in Java:

Java
class Solution {
    public void sortColors(int[] nums) {
        // Initialize pointers for the current element (mid),
        // the boundary for zeros (low), and the boundary for twos (high).
        int low = 0;
        int mid = 0;
        int high = nums.length - 1;
        
        // Process elements in the array
        while (mid <= high) {
            if (nums[mid] == 0) {
                // Swap the mid element with the low element
                swap(nums, low, mid);
                // Increment both low and mid pointers
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                // If the element is 1, just move the mid pointer
                mid++;
            } else {
                // Swap the mid element with the high element
                swap(nums, mid, high);
                // Decrement the high pointer
                high--;
            }
        }
    }
    
    // Helper method to swap elements in the array
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Solution in C#:

C#
public class Solution {
    public void SortColors(int[] nums) {
        // Initialize pointers for the current element (mid),
        // the boundary for zeros (low), and the boundary for twos (high).
        int low = 0;
        int mid = 0;
        int high = nums.Length - 1;
        
        // Process elements in the array
        while (mid <= high) {
            if (nums[mid] == 0) {
                // Swap the mid element with the low element
                Swap(nums, low, mid);
                // Increment both low and mid pointers
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                // If the element is 1, just move the mid pointer
                mid++;
            } else {
                // Swap the mid element with the high element
                Swap(nums, mid, high);
                // Decrement the high pointer
                high--;
            }
        }
    }
    
    // Helper method to swap elements in the array
    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com