Share My O(n) Solution With Constant Space O(1)


  • 0
    C

    Please refer to my comments in code. My thought is straight forward: Array starts with 0 and ends with 2. So use 2 pointers to iterate this array from beginning and end respectively. Each time we find 0, put them to the front (insertRed); Otherwise if 2 is found, put them to the last (insertBlue).

    public class Solution {
    public void sortColors(int[] A) {
    if (A == null || A.length <= 1) {
    return;
    }

        // insertRed indicates the location to insert 0, insertBlue
        // indicates the location to insert 2. Use index to iterate array.
        int index = 0, insertRed = 0, insertBlue = A.length - 1;
        while (index <= insertBlue) {
            
            // if current element is 0 and it happens to be the position
            // needs to insert 0, continue
            if (A[index] == 0 && index == insertRed) {
                insertRed++;
                index++;
                continue;
            } 
            
            // if current element is 0, then we need to insert it to A[insertRed]
            if (A[index] == 0) {
                int temp = A[insertRed];
                A[insertRed] = 0;
                A[index] = temp;
                insertRed++;
                continue;
            }
            
            // if current element is 2, then insert it to A[insertBlue]
            if (A[index] == 2) {
                int temp = A[insertBlue];
                A[insertBlue] = 2;
                A[index] = temp;
                insertBlue--;
                continue;
            }
            
            // if current element is 1, loop to next element
            if (A[index] == 1) {
                index++;
            }
        }
    }
    

    }


Log in to reply
 

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