Leetcode 3Sum: why is result duplicated?

Question

I am trying the 15. 3Sum code challenge on LeetCode:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]] 

Here is my attempt:

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return []
        nums.sort()
        ret_val = []
        for i in range(len(nums) - 2):
            if i - 1 >= 0 and nums[i - 1] == nums[i]:
                while nums[i - 1] == nums[i] and i < len(nums) - 2:
                    i += 1
                if nums[i - 1] == nums[i]:
                    break
            j = i + 1
            k = len(nums) - 1
            # This is our target sum
            target = -nums[i]            
            while j < k:
                if j - 1 != i and nums[j - 1] == nums[j]:
                    while nums[j - 1] == nums[j] and j < k:
                        j += 1
                elif k + 1 != len(nums) and nums[k + 1] == nums[k]:
                    while nums[k + 1] == nums[k] and j < k:
                        k -= 1
                else:
                    if nums[j] + nums[k] == target:
                        ret_val.append([nums[i], nums[j], nums[k]])
                        j += 1
                        k -= 1
                    elif nums[j] + nums[k] < target:
                        j += 1
                    else:
                        k -= 1
        return ret_val

There is apparently a bug in my code that I couldn't figure out, even after running the Python Debugger. My code gives the wrong result when I use the input of [-11, 1, -12, -12, 10]. It creates an unnecessary duplicate in the answer. I've never seen this happen before, but Python seems to run the for loop one too many times.

The expected output should be [[-11, 1, 10]], but it instead gives [[-11, 1, 10], [-11, 1, 10]]. Another interesting thing I discovered is that by removing either one or both instances of -12, it ends up giving the correct answer of [[-11, 1, 10]].

What is the problem in my code?

You told us the input, but could you explain what your program should do, what you get as a result and what you expect? — Matthias
– Matthias, Commented Jul 17, 2021 at 8:41
Just for fun: that's a one-liner if you use itertools from the standard library: print({tuple(sorted(combi)) for combi in itertools.combinations(nums, 3) if sum(combi) == 0}) — Matthias
– Matthias, Commented Jul 18, 2021 at 12:36

trincot · Accepted Answer · 2021-07-17 16:15:11Z

1

The reason is that your outer loop will sometimes increment i (the loop variable). This is not good, because that incremented i value is scheduled to be i's value in a next iteration of that loop, and so you will have two iterations happening with the same value for i.

Note how Python's for i in range iteration does not take into account any increment you apply to i in one of the iterations. The full range of values will be iterated, no matter what you do with i in the mean time. This is different from more traditional for loop constructs that you find in other programming languages:

for (int i = 0; i < len(nums) - 2; i++)

...as in that case the loop's i++ will just act on whatever value i has at that moment, taking into account any change you made to i during an iteration. Again, this is not how it works with an iterator such as Python's range function returns.

The solution is to just exit the current iteration when you would have wanted to increment i, since you know that the next iteration will have that incremented value for i anyhow.

So change this piece of code:

   if i - 1 >= 0 and nums[i - 1] == nums[i]:
        while nums[i - 1] == nums[i] and i < len(nums) - 2:
            i += 1
        if nums[i - 1] == nums[i]:                
            break

to this:

    if i - 1 >= 0 and nums[i - 1] == nums[i]:
        continue

That will solve the issue.

answered Jul 17, 2021 at 16:15

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

BishopsScope Over a year ago

You're totally right! Now it makes sense why removing -12 fixed the solution. Thanks!

Collectives™ on Stack Overflow

Leetcode 3Sum: why is result duplicated?

Example 1:

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Example 1:

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related