title: Solving the LeetCode 3sum problem in Python
body: <p>I'm trying to solve the <a href="https://leetcode.com/problems/3sum/description/" rel="nofollow noreferrer">3Sum</a> problem on LeetCode. I'm come up with the following solution:</p>
  
  <pre><code>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]
  </code></pre>
  
  <p>with the following test suite:</p>
  
  <pre><code>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]])
  </code></pre>
  
  <p>All the tests pass locally:</p>
  
  <pre><code>$ 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 ===========================
  </code></pre>
  
  <p>However, if I submit the solution on LeetCode, I get a "Wrong Answer" result:</p>
  
  <p><a href="https://i.stack.imgur.com/Kjt3U.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Kjt3U.png" alt="enter image description here"></a></p>
  
  <p>Note, however, that this is the same test case as <code>test_6</code> in my local test suite!</p>
  
  <p>Indeed if I run this input in an <code>ipython</code> shell (after renaming the file to <code>threesum.py</code> to avoid an import error), I get the expected three results, albeit in a different order:</p>
  
  <pre><code>$ 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]]
  </code></pre>
  
  <p>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?</p>