C++ concise One-Pass O(n) time O(1) space 10 line solution


  • 0
    Z

    Main idea is to accumulate 0 from the begin and accumulate 2 from the end.

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

Log in to reply
 

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