Solving the LeetCode 3sum problem in Python

Question

I'm trying to solve the 3Sum problem on LeetCode. I'm come up with the following solution:

import collections


class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        d = collections.defaultdict(dict)
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                d[-nums[i]-nums[j]].update(
                    {tuple(sorted([nums[i], nums[j]])): (i, j)})

        triplets = set()
        for index, num in enumerate(nums):
            if num in d:
                for doublet, indices in d[num].items():
                    if index not in indices:
                        triplet = tuple(sorted([num, *doublet]))
                        if triplet not in triplets:
                            triplets.add(triplet)
                            break

        return [list(triplet) for triplet in triplets]

with the following test suite:

def set_equals(a, b):
    # Auxiliary method for testing
    return set(tuple(x) for x in a) == set(tuple(y) for y in b)


def test_unique():
    assert Solution().threeSum([0, 0]) == []


def test_1():
    nums = [-1, 0, 1, 2, -1, 4]
    assert set_equals(
        Solution().threeSum(nums),
        [
          [-1, 0, 1],
          [-1, -1, 2]
        ])


def test_with_duplicates():
    nums = [-1, 0, -1, 0, 1]
    assert set_equals(
        Solution().threeSum(nums),
        [[-1, 0, 1]])


def test_same_number():
    assert Solution().threeSum([0, 0, 0]) == [[0, 0, 0]]


def test_3():
    assert set_equals(Solution().threeSum(
        [-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6]),
        [
            [-4, -2, 6],
            [-4, 0, 4],
            [-4, 1, 3],
            [-4, 2, 2],
            [-2, -2, 4],
            [-2, 0, 2]])


def test_4():
    assert set_equals(Solution().threeSum(
        [-4, -2, 1, -5, -4, -4, 4, -2, 0, 4, 0, -2, 3, 1, -5, 0]),
        [
            [-5, 1, 4],
            [-4, 0, 4],
            [-4, 1, 3],
            [-2, -2, 4],
            [-2, 1, 1],
            [0, 0, 0]])


def test_6():
    assert set_equals(
        Solution().threeSum([0, 3, 0, 1, 1, -1, -5, -5, 3, -3, -3, 0]),
        [[-3, 0, 3], [-1, 0, 1], [0, 0, 0]])

All the tests pass locally:

$ pytest 3sum.py -s
============================= test session starts ==============================
platform darwin -- Python 3.6.6, pytest-3.8.1, py-1.6.0, pluggy-0.7.1
rootdir: /Users/kurtpeek/GoogleDrive/LeetCode, inifile:
collected 7 items                                                              

3sum.py .......

=========================== 7 passed in 0.04 seconds ===========================

However, if I submit the solution on LeetCode, I get a "Wrong Answer" result:

Note, however, that this is the same test case as test_6 in my local test suite!

Indeed if I run this input in an ipython shell (after renaming the file to threesum.py to avoid an import error), I get the expected three results, albeit in a different order:

$ ipython
Python 3.6.6 (v3.6.6:4cf1f54eb7, Jun 26 2018, 19:50:54) 
Type 'copyright', 'credits' or 'license' for more information
IPython 6.5.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: from threesum import *

In [2]: Solution().threeSum([0, 3, 0, 1, 1, -1, -5, -5, 3, -3, -3, 0])
Out[2]: [[-1, 0, 1], [0, 0, 0], [-3, 0, 3]]

It seems that somehow, LeetCode's "Output" is not the same as my output. Any idea how I could get the solution to be accepted?

ababuji · Accepted Answer · 2018-10-12 20:31:37Z

4

I ran many tests as to what was happening.

This has something to do with the fact that dictionary items key, value pairs are not present in the same order in which they were pushed into the dictionary.

For example, your dictionary may have d = {1:'a', 2:'b', 3:'c'} But when ITERATING through the dictionary:

for key, value in d.items():
    print(key, value)

There is no guarantee that you get this print:

1, 'a'
2, 'b'
3, 'c'

Because dictionaries are inherently supposed to be UNORDERED.

As to why it is WORKING in YOUR machine and even MY machine is because I can venture to guess that we have Python 3.5+ (I do for sure) where the order of entry into the dictionary is being preserved.

Leetcode runs Python 3. Not 3.5+.

So when you're iterating through the dictionary

for doublet, indices in d[num].items():

Depending on the order in which doublet, indices appear, (THERE IS NO GUARANTEE THAT IT WILL APPEAR IN ANY SPECIFIC ORDER), you cannot guarantee that loop execution will be the same!

What can you do? I say learn to use OrderedDict. This preserves the order in which the key, value pair are PUT into the dictionary.

I am not an expert at OrderedDict, so I can't help.

But a simple print statement:

for doublet, indices in d[num].items():
    print(doublet, indices)

in both your own local machine and in your Leetcode output will show you what I mean.. Printing doublet, indices makes them show up in different order in your Leetcode output and in your local machine output.

answered Oct 12, 2018 at 20:31

ababuji

1,7412 gold badges17 silver badges41 bronze badges

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

2 Comments

Kurt Peek Over a year ago

From the wording of the example on LeetCode, "A solution set is:", it would seem that the order of the output does not matter, which is what I tried to emulate using the set_equal auxiliary function. Further, even if the order did matter, LeetCode is reporting for my code's output a result, [[-1, 0, 1], [-3, 0, 3]], which does not include the [0, 0, 0] result, which my code does generate as seen from the 'local' tests. So why is an entire result missing only on LeetCode?

ababuji Over a year ago

I see Expected output to include [0, 0, 0] as posted in your picture. It is only OUR output generated from our code that does not include [0, 0, 0], the reasoning for which I have given saying that depending on the order in which the key, value pairs are seen in the dictionary, computation proceeds.

Kurt Peek · Accepted Answer · 2018-10-13 06:40:54Z

1

At the heart of the problem is the break statement which introduces the 'order dependency' explain by Abhishek. If I comment out the break statement, I get a different error, Time Limit Exceeded:

Apparently, my O(N^2) solution is too slow, but at least it is now giving the correct answers.

answered Oct 13, 2018 at 6:40

Kurt Peek

58.5k104 gold badges354 silver badges572 bronze badges

Collectives™ on Stack Overflow

Solving the LeetCode 3sum problem in Python

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related