Friedrich Ewald My Personal Website

Leetcode: Three sum

Given a list of integers, add three integers at the same time so that the sum of those integers is 0. There should be no repetition of integers, for example [-1, 0, 1] is equivalent to [-1, 1, 0]. The solution makes use of the fact that duplicate numbers can be ignored. To do this, the numbers need to be sorted first. Then, if the next number is the same as the previous, it can be skipped. This does not affect the number of the other pointers, thus there can be the same number in different pointers. In total there are two loops needed. The outer loop iterates from the smallest to the third-largest number. For every iteration, a pointer p2 and p3 are defined. The pointer p2 starts directly one position right of p1 while p3 starts at the end of the list. We then need to distinguish three cases. If the sum is exactly 0, we can add the item to the results. If it is greater than 0, we move the pointer p3 to the left which makes the number smaller. If it is less than 0, we move p2 to the right which increases the total sum. We continue this approach until p2 and p3 meet, then continue with the outer iteration. Additionally, there is some logic to deal with duplicates.

from typing import List

class Solution:
  def threeSum(self, nums: List[int]) -> List[List[int]]:
    # Sort in place

    result = []
    for p1 in range(len(nums) - 2):
      if p1 > 0 and nums[p1] == nums[p1 - 1]:

      p2 = p1 + 1
      p3 = len(nums) - 1

      while p2 < p3:
        s = nums[p1] + nums[p2] + nums[p3]
        if s == 0:
          result += [[nums[p1], nums[p2], nums[p3]]]
          p3 -= 1

          while p2 < p3 and nums[p3] == nums[p3 + 1]:
            p3 -= 1
        elif s > 0:
          p3 -= 1
          p2 += 1

    return result

if __name__ == '__main__':
  s = Solution().threeSum
  print(s([-1,0,1,2,-1,-4]), [[-1,-1,2],[-1,0,1]])
  print(s([-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]])
  print(s([-2,0,1,1,2]), [[-2,0,2],[-2,1,1]])
Runtime: 1340 ms, faster than 50.64% of Python3 online submissions for 3Sum. Memory Usage: 18.2 MB, less than 39.78% of Python3 online submissions for 3Sum.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.