Research

[LeetCode 15] 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != ji != 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]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints:

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

Solution

This problem is a follow-up of Two Sum, and it is a good idea to first take a look at Two Sum and Two Sum II. An interviewer may ask to solve Two Sum first, and then throw 3Sum at you. Pay attention to subtle differences in problem description and try to re-use existing solutions!

Two Sum, Two Sum II and 3Sum share a similarity that the sum of elements must match the target exactly. A difference is that, instead of exactly one answer, we need to find all unique triplets that sum to zero.

Before jumping in, let’s check the existing solutions and determine the best conceivable runtime (BCR) for 3Sum:

  1. Two Sum uses a hashmap to find complement values, and therefore achieves \mathcal{O}(N) time complexity.
  2. Two Sum II uses the two pointers pattern and also has \mathcal{O}(N) time complexity for a sorted array. We can use this approach for any array if we sort it first, which bumps the time complexity to \mathcal{O}(n\log{n}).

Considering that there is one more dimension in 3Sum, it sounds reasonable to shoot for \mathcal{O}(n^2) time complexity as our BCR.


Approach 1: Two Pointers

We will follow the same two pointers pattern as in Two Sum II. It requires the array to be sorted, so we’ll do that first. As our BCR is \mathcal{O}(n^2)O(n2), sorting the array would not change the overall time complexity.

To make sure the result contains unique triplets, we need to skip duplicate values. It is easy to do because repeating values are next to each other in a sorted array.

If you are wondering how to solve this problem without sorting the array, go over the “No-Sort” approach below. There are cases when that approach is preferable, and your interviewer may probe your knowledge there.

After sorting the array, we move our pivot element nums[i] and analyze elements to its right. We find all pairs whose sum is equal -nums[i] using the two pointers pattern, so that the sum of the pivot element (nums[i]) and the pair (-nums[i]) is equal to zero.

As a quick refresher, the pointers are initially set to the first and the last element respectively. We compare the sum of these two elements to the target. If it is smaller, we increment the lower pointer lo. Otherwise, we decrement the higher pointer hi. Thus, the sum always moves toward the target, and we “prune” pairs that would move it further away. Again, this works only if the array is sorted. Head to the Two Sum II solution for the detailed explanation.

Algorithm

The implementation is straightforward – we just need to modify twoSumII to produce triplets and skip repeating values.

  1. For the main function:
    • Sort the input array nums.
    • Iterate through the array:
      • If the current value is greater than zero, break from the loop. Remaining values cannot sum to zero.
      • If the current value is the same as the one before, skip it.
      • Otherwise, call twoSumII for the current position i.
  2. For twoSumII function:
    • Set the low pointer lo to i + 1, and high pointer hi to the last index.
    • While low pointer is smaller than high:
      • If sum of nums[i] + nums[lo] + nums[hi] is less than zero, increment lo.
      • If sum is greater than zero, decrement hi.
      • Otherwise, we found a triplet:
        • Add it to the result res.
        • Decrement hi and increment lo.
        • Increment lo while the next value is the same as before to avoid duplicates in the result.
  3. Return the result res.
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)):
            if nums[i] > 0:
                break
            if i == 0 or nums[i - 1] != nums[i]:
                self.twoSumII(nums, i, res)
        return res

    def twoSumII(self, nums: List[int], i: int, res: List[List[int]]):
        lo, hi = i + 1, len(nums) - 1
        while (lo < hi):
            sum = nums[i] + nums[lo] + nums[hi]
            if sum < 0:
                lo += 1
            elif sum > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1

Complexity Analysis

  • Time Complexity: \mathcal{O}(n^2)twoSumII is \mathcal{O}(n), and we call it n times. Sorting the array takes \mathcal{O}(n\log{n}), so overall complexity is \mathcal{O}(n\log{n} + n^2). This is asymptotically equivalent to \mathcal{O}(n^2).
  • Space Complexity: from \mathcal{O}(\log{n}) to \mathcal{O}(n), depending on the implementation of the sorting algorithm. For the purpose of complexity analysis, we ignore the memory required for the output.
060

Leave a reply