LeetCode Python/Java/C++/JS  >  75. Sort Colors  >  Solved in Python, Java, JavaScript, Cpp, Csharp, Go, Ruby, Rust, Kotlin, Swift  >  GitHub

    LeetCode link: 75. Sort Colors, difficulty: Medium.

    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]

    Example 2:

    Input: nums = [2,0,1]

    Output: [0,1,2]

    Constraints:

    • n == nums.length
    • 1 <= n <= 300
    • nums[i] is either 0, 1, or 2.
    • Follow up: Could you come up with a one-pass algorithm using only constant extra space?
    Topics

    Array Two Pointers Sorting

    Hint 1

    A rather straight forward solution is a two-pass algorithm using counting sort.

    Hint 2

    Iterate the array counting number of 0's, 1's, and 2's.

    Hint 3

    Overwrite array with the total number of 0's, then 1's and followed by 2's.

    Intuition
    PreviousNext

    The problem asks us to sort an array containing only 0s, 1s, and 2s in-place. The follow-up challenge is to do it in a single pass using constant extra space.
    This is exactly the "Dutch National Flag" problem proposed by Edsger W. Dijkstra. We can solve it using three pointers to divide the array into three main regions: a region of 0s at the beginning, a region of 2s at the end, and the region of elements currently being processed (which will naturally leave 1s in the middle).

    👋 Hi, I'm the developer behind coder.id — Build your programmer brand. Create your portfolio, resume, and blog in minutes, and land your dream offer!

    Step-by-Step Solution

    1. Initialize three pointers: low = 0 (boundary for 0s), high = nums.length - 1 (boundary for 2s), and i = 0 (current element index).
    2. Loop while i <= high:
      • If nums[i] == 0: Swap nums[i] and nums[low]. We know the swapped element from low is either 0 or 1 (since i has already passed or is at low), so it's safe to increment both low and i.
      • If nums[i] == 1: The element is already in the correct middle region, just increment i.
      • If nums[i] == 2: Swap nums[i] and nums[high]. We decrement high. However, we do not increment i here because the new element swapped from high into i hasn't been checked yet (it could be a 0, 1, or 2).
    3. Once i surpasses high, the array is sorted.

    Complexity

    Time complexity

    O(N)

    Space complexity

    O(1)

    Explanation

    • Time Complexity: O(N), where N is the length of the array nums. We process each element at most twice (once by i and possibly once swapped from high), meaning we do a single pass through the array.
    • Space Complexity: O(1). The sorting is done completely in-place using only three integer variables for pointers, requiring constant extra space.

    Solution in languages: Python Java JavaScript Cpp Csharp Go Ruby Rust Kotlin Swift

    Python # 

    class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # low points to the next position for 0
        # high points to the next position for 2
        low, i, high = 0, 0, len(nums) - 1

        while i <= high:
            if nums[i] == 0:
                # Swap and advance both low and i
                nums[low], nums[i] = nums[i], nums[low]
                low += 1
                i += 1
            elif nums[i] == 2:
                # Swap and decrement high. Do NOT advance i yet
                # because the swapped element needs to be checked
                nums[high], nums[i] = nums[i], nums[high]
                high -= 1
            else:
                # nums[i] == 1, already in place
                i += 1

    Java # 

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

        while (i <= high) {
            if (nums[i] == 0) {
                swap(nums, low, i);
                low++;
                i++;
            } else if (nums[i] == 2) {
                swap(nums, i, high);
                high--;
                // Don't increment 'i' here, the new nums[i] needs to be evaluated
            } else {
                // nums[i] == 1
                i++;
            }
        }
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

    JavaScript # 

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

    while (i <= high) {
        if (nums[i] === 0) {
            // Swap nums[low] and nums[i]
            [nums[low], nums[i]] = [nums[i], nums[low]];
            low++;
            i++;
        } else if (nums[i] === 2) {
            // Swap nums[i] and nums[high]
            [nums[high], nums[i]] = [nums[i], nums[high]];
            high--;
            // Do not increment i, evaluate the newly swapped element
        } else {
            // If it is 1, just move forward
            i++;
        }
    }
};

    Cpp # 

    class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0;
        int i = 0;
        int high = nums.size() - 1;

        while (i <= high) {
            if (nums[i] == 0) {
                swap(nums[low], nums[i]);
                low++;
                i++;
            } else if (nums[i] == 2) {
                swap(nums[i], nums[high]);
                high--;
                // Note: i is not incremented
            } else {
                // nums[i] == 1
                i++;
            }
        }
    }
};

    Csharp # 

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

        while (i <= high) {
            if (nums[i] == 0) {
                // Swap
                int temp = nums[low];
                nums[low] = nums[i];
                nums[i] = temp;

                low++;
                i++;
            } else if (nums[i] == 2) {
                // Swap
                int temp = nums[high];
                nums[high] = nums[i];
                nums[i] = temp;

                high--;
            } else {
                i++;
            }
        }
    }
}

    Go # 

    func sortColors(nums []int) {
    low := 0
    i := 0
    high := len(nums) - 1

    for i <= high {
        if nums[i] == 0 {
            nums[low], nums[i] = nums[i], nums[low]
            low++
            i++
        } else if nums[i] == 2 {
            nums[high], nums[i] = nums[i], nums[high]
            high--
        } else {
            // nums[i] == 1
            i++
        }
    }
}

    Ruby # 

    # @param {Integer[]} nums
# @return {Void} Do not return anything, modify nums in-place instead.
def sort_colors(nums)
    low = 0
    i = 0
    high = nums.length - 1

    while i <= high
        if nums[i] == 0
            nums[low], nums[i] = nums[i], nums[low]
            low += 1
            i += 1
        elsif nums[i] == 2
            nums[high], nums[i] = nums[i], nums[high]
            high -= 1
        else
            i += 1
        end
    end
end

    Rust # 

    impl Solution {
    pub fn sort_colors(nums: &mut Vec<i32>) {
        let mut low = 0;
        let mut i = 0;
        let mut high = nums.len() as i32 - 1;

        while (i as i32) <= high {
            match nums[i] {
                0 => {
                    nums.swap(low, i);
                    low += 1;
                    i += 1;
                }
                2 => {
                    nums.swap(i, high as usize);
                    high -= 1;
                }
                _ => {
                    // It's 1
                    i += 1;
                }
            }
        }
    }
}

    Kotlin # 

    class Solution {
    fun sortColors(nums: IntArray): Unit {
        var low = 0
        var i = 0
        var high = nums.size - 1

        while (i <= high) {
            when (nums[i]) {
                0 -> {
                    val temp = nums[low]
                    nums[low] = nums[i]
                    nums[i] = temp
                    low++
                    i++
                }
                2 -> {
                    val temp = nums[high]
                    nums[high] = nums[i]
                    nums[i] = temp
                    high--
                }
                else -> {
                    i++
                }
            }
        }
    }
}

    Swift # 

    class Solution {
    func sortColors(_ nums: inout [Int]) {
        var low = 0
        var i = 0
        var high = nums.count - 1

        while i <= high {
            if nums[i] == 0 {
                nums.swapAt(low, i)
                low += 1
                i += 1
            } else if nums[i] == 2 {
                nums.swapAt(i, high)
                high -= 1
            } else {
                i += 1
            }
        }
    }
}
    Solution in languages: Python Java JavaScript Cpp Csharp Go Ruby Rust Kotlin Swift

    Other languages

    Welcome to contribute code to GitHub repo -> 75. Sort Colors. Thanks!
    PreviousNext

    Level Up Your Developer Identity

    • 📄 Resume, Portfolio & Blog
    • 🌐 Custom Domain Binding Supported
    • ✨ Premium Subdomain: https://yourname.coder.id

    Build Your Developer Brand at coder.id →