CODEWITHSUNDEEP
pythonpython-2.7
Julien Chien
Julien Chien

Reputation: 2190

Why does the swapping work one way but not the other?

For this question on leetcode, I attempted to solve with Python 2.7 with the code at the bottom of the post. However, for an input of [2,1], the function will loop forever. But, if I change the line doing the swap, and switch the variables so the order is the opposite, the swapping will actually work and the function executes correctly.

So currently the code has the swap as: nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i], which doesn't work (this is in the while loop). If I change the order of swapping to nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1], the swap/assignment does work. Why is that? I looked on SO and it seemed like Python's a,b=b,a swap works by putting both a and b on the stack (evaluating the right side of = first) and then reassigning them (description here). If that is how it works, then why shouldn't b,a=a,b achieve the same effects?

On Leetcode's online judge, my current (looping forever way) freezes the page. I tried it on my local Python 2.7 environment and it also loops forever. I tested that a,b=b,a is equivalent to b,a=a,b in my environment. So then - why does my code below loop forever when the swap is in one order and work perfectly in the other order?

def firstMissingPositive(nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 1:
            if nums[0] != 1:
                return 1
            else:
                return 2
        i = 0
        while i < len(nums):
            if nums[i] > 0 and nums[i] - 1 < len(nums) and nums[i] != nums[nums[i]-1]:
                #Line below does not work
                nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]

                #=>> ??But this works?? # nums[nums[i]-1], nums[i]  = nums[i], nums[nums[i]-1]
            else:
                i += 1

        for i, int in enumerate(nums):
            if int != i + 1:
                return i + 1

        return len(nums) + 1

Upvotes: 1

Views: 44

Answers (1)

Prune
Prune

Reputation: 77857

The use of nums[i]-1 as a subscript for nums introduces an extra evaluation that isn't in the order you want. Run a simple test, such as on the list [1, 2, 3, 4, 5, 6, 7] with just a few of these statements, and you'll see the result.

If you handle just one intermediate operation, I think you'll get the semantics you want:

index = nums[i]
nums[i], nums[index-1] = nums[index-1], nums[i]

Upvotes: 1

Related Questions