Sharing C++ solution with Good Explanation


  • 64
    A

    The solution requires the use of tracking 3 positions, the Low, Mid and High.

    We assume that the mid is the "Unknown" area that we must evaluate.

    If we encounter a 0, we know that it will be on the low end of the array, and if we encounter a 2, we know it will be on the high end of the array.

    To achieve this in one pass without preprocessing (counting), we simply traverse the unknown will generating the low and high ends.

    Take this example:

    Assume our input is: 1 0 2 2 1 0 (short for simplicity).

    Running the algorithm by hand would look something like:

        1 0 2 2 1 0
        ^         ^
        L         H
        M
    
        Mid != 0 || 2
        Mid++
    
        1 0 2 2 1 0
        ^ ^       ^
        L M       H
    
        Mid == 0
        Swap Low and Mid
        Mid++
        Low++
    
        0 1 2 2 1 0
          ^ ^     ^
          L M     H
    
        Mid == 2
        Swap High and Mid
        High--
    
        0 1 0 2 1 2
          ^ ^   ^
          L M   H
    
        Mid == 0
        Swap Low and Mid
        Mid++
        Low++
    
        0 0 1 2 1 2
            ^ ^ ^
            L M H
    
        Mid == 2
        Swap High and Mid
        High--
    
        0 0 1 1 2 2
            ^ ^
            L M
              H
    
        Mid <= High is our exit case
    

    Implemented in C++, it looks like:

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

  • 0
    A

    Nice explanation, thanks


  • 0
    V

    So far the best explanation for this problem I've seen. Thanks !


  • 0
    A

    @Atomsktron Thank you so much for offering the explanation and the solution


  • 0
    L
    This post is deleted!

  • 2
    C

    Nice thought! Just a heads-up. C++ has built-in swap, and there is no need to have int temp;

    void sortColors(vector<int>& nums) {
        int l{}, mid{}, h{nums.size() - 1};
        while (mid <= h)
            if (nums[mid] == 0)
                swap(nums[mid++], nums[l++]);
            else if (nums[mid] == 1)
                mid++;
            else 
                swap(nums[mid], nums[h--]);
    }

  • 1

    Another note, the swap is not even necessary either because we know what the value of nums[mid] is entering every if condition.

    So,

    if(nums[mid] == 0)
    {
        tmp = nums[low];
        nums[low] = nums[mid];
        nums[mid] = tmp;
        low++;
        mid++;
    }
    

    becomes

    if(nums[mid] == 0) {
        nums[mid] = nums[low];
        nums[low] = 0;
        low++;
        mid++;
    }
    

  • 1
    X
    Why when mid==2 satisfy, we dont need mid++? 
    

    @Atomsktron
    See the follow. Thks.
    Mid == 2
    Swap High and Mid
    High--


  • 0
    C

    @Atomsktron Lovely.


  • 1
    D

    @xhp0407 The reason why we don't need mid++ is because on the right side of mid, it could be a 0 swapped back, that will need be further swapped to left to mid. This is a problem when doing scanning from left to right. If doing scanning from right to left, we have following

        public void sortColors(int[] nums) {
            if (nums == null || nums.length == 0)
                return;
            int n = nums.length;
            int i = n - 1, j = 0, k = n - 1;
            while (j <= i) {
                if (nums[i] == 0) {
                    int t = nums[i];
                    nums[i] = nums[j];
                    nums[j] = t;
                    j++;
                } else if (nums[i] == 1) {
                    i--;
                } else {
                    int t = nums[i];
                    nums[i] = nums[k];
                    nums[k] = t;
                    k--;
                    i--;
                }
            }
        }
    

  • 0
    L

    @daniexia This explanation is great and necessary, thanks


  • 0
    T

    @Atomsktron Thanks for the nice solution.

    My method is straightforward.
    What I've done is simply cut the nums into three part (red, white, blue) and combine them.

    class Solution {
    public:
        void sortColors(vector<int>& nums) {
            vector<int> red, white, blue;
            vector<int> res;
            for(int i = 0; i < nums.size(); ++i)
            {
                if(nums[i] == 0)
                {
                    red.push_back(nums[i]);
                    continue;
                }
                if(nums[i] == 1)
                {
                    white.push_back(nums[i]);
                    continue;
                }
                if(nums[i] == 2)
                {
                    blue.push_back(nums[i]);
                    continue;
                }
            }
            res.insert(res.end(), red.begin(), red.end());
            res.insert(res.end(), white.begin(), white.end());
            res.insert(res.end(), blue.begin(), blue.end());
            nums = res;
        }
    };
    
    

  • 0
    B

    Good explanation. Actually, someone who familiar with partition in Quicksort will find that the idea is the same.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.