algoadvance

Leetcode 75. Sort Colors

Problem Statement

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. Here, we 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.

Clarifying Questions

1. Input Constraints:
   • What is the length of nums? Is there a constraint on n?
   • Are there other values besides 0, 1, and 2 in the array?
2. Output Requirements:
   • Should the sorted array be returned, or is it sufficient to modify the input array nums?
3. Edge Cases:
   • Can the input array be empty?
   • Can all elements in the input array be of the same color?

Strategy

To solve this problem efficiently, we can utilize the Dutch National Flag algorithm proposed by Edsger W. Dijkstra. This algorithm uses three pointers to partition the array into three sections:

• All elements to the left of the low pointer should be 0.
• All elements between the low pointer and the mid pointer should be 1.
• All elements between the high pointer and the end of the array should be 2.

We can achieve this in one pass through the array with a linear time complexity O(n) and constant space complexity O(1).

Code

#include <vector>
#include <algorithm>

void sortColors(std::vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;

    while (mid <= high) {
        if (nums[mid] == 0) {
            std::swap(nums[low], nums[mid]);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            std::swap(nums[mid], nums[high]);
            high--;
        }
    }
}

Explanation

1. Initialization:
   • low starts at the beginning of the array and will track where the next 0 should go.
   • mid starts at the beginning too and will traverse the array.
   • high starts at the end of the array and will track where the next 2 should go.
2. Traversal:
   • If nums[mid] is 0, swap it with nums[low], then increment both low and mid.
   • If nums[mid] is 1, just move the mid pointer forward.
   • If nums[mid] is 2, swap it with nums[high], then decrement high, without moving mid because the swapped element at mid needs to be examined.

Time Complexity

• The algorithm goes through the list once, so the time complexity is O(n).

Space Complexity

• It uses constant extra space, so the space complexity is O(1).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?