Swift 1 pass solution with comments (credit to @dietpepsi)


  • 0
    M
    class Solution {
        // a bit hard to follow, but 1 pass, constant space
        // blueIdx >= whiteIdx >= redIdx is always true
        func sortColors(_ nums: inout [Int]) {
            var redIdx = 0
            var whiteIdx = 0
            for blueIdx in 0..<nums.count {
                let col = nums[blueIdx]
                // always write blue
                nums[blueIdx] = 2
                // this part is the tricky bit
                // if the color is not blue, write at whiteIdx and increment
                // we write white for *both* white and red, we will
                // correct this in the next condition if necessary
                // we only lose the white value *if* it is actually supposed to be red anyhow
                if col < 2 {
                    nums[whiteIdx] = 1
                    whiteIdx += 1
                }
                // if the color is red, write at redIdx and increment
                // we're tracking reds from 0 and white has already been
                // incremented past this index above
                if col == 0 {
                    nums[redIdx] = 0
                    redIdx += 1
                }
            }
        }
    }
    

Log in to reply
 

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