Skip to content

LC15. 3Sum

Problem Description

LeetCode Problem 15: 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.

Clarification

  • find triplets with sum == 0
  • no duplicate triplets
  • sorted or unsorted?
  • target or array values can be negative

Assumption

Solution

Approach - Sort + Two Pointers

Here are general steps:

  1. Sort array first.
  2. Fix nums[i] by iterating along the array. Then the problem become to a smaller problem Two Sum
  3. Using two pointers front and back for remaining elements to find nums[front] + nums[back] == target - nums[i]
Note

Remember to remove duplicates

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        target = 0
        nums.sort()
        triplets = []
        n = len(nums)
        for i in range(n - 2):
            if nums[i] > 0:
                break

            # Process duplicates of number 1
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            front = i + 1
            back = n - 1
            while (front < back):
                s = nums[i] + nums[front] + nums[back]

                if s < target:
                    front += 1
                elif s > target:
                    back -= 1
                else:
                    current_triplet = [nums[i], nums[front], nums[back]]
                    triplets.append(current_triplet)

                    # Process duplicates of number 2
                    while (front < back and nums[front] == current_triplet[1]):
                        front += 1

                    # Process duplicates of number 3
                    while (front < back and nums[back] == current_triplet[2]):
                        back -= 1

        return triplets

Complexity Analysis

  • Time complexity: \(O(n^2)\)
    • Before for-loop, the sort complexity is \(O(n \log n)\).
    • In the for loop, using two pointers will take \(O(n)\) time. So time complexity of for-loop is \(O(n^2)\)
      So the total time complexity is \(O(n \log n) + O(n^2) = O(n^2)\)
  • Space complexity: \(O(sorting)\)
    • Sort algorithm will take some space. For quick sort, the space complexity is \(O(sorting) = O(\log n)\). For merge sort, the space complexity is \(O(sorting) = O(n)\)
    • The rest of code using index variables, which take \(O(1)\) space
      So the total space complexity is \(O(sorting) + O(1) = O(sorting)\)

Test