Simple Python solution without using triple indices, is this one pass though?


  • 0
    L

    The concept is quite simple, scan left to right and put all 0s to the left by swapping it with the first non-zero position, then continue scanning to put all 1s to where 0 stopped.

    This is using one for loop only, but at one point when I reset j to i to do run the iteration for color 1. Is this still considered one pass or did I break it into two passes?

    class Solution(object):
        def sortColors(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            i = j = 0
            k = 0  # 0, 1 cuz 2 will be automatically left out
            while i < len(nums):
                if nums[j] == k and j > i:
                    nums[i], nums[j] = nums[j], nums[i]
                if nums[i] == k:
                    i += 1
                j += 1
                # reset 
                if j >= len(nums) and k == 0:
                    k = 1
                    j = i
                elif j >= len(nums):
                    break
    

Log in to reply
 

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