Leetcode Problem 15: 3 Sum

Problem description:

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.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
```ruby

Constraints:

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

As usual my priority is to get any solution at all, even if inefficient. The first code attempt uses the N choose K formula from combinatorics. The problem description really can be reworded roughly as “out of all the possible distinct triplets within the array, choose the ones that sum to zero”.

(Attempted) combinatorial Python solution Link to heading


# leetcode_15.py

from itertools import combinations

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        if n < 3:
            return []
        result = []
        index_range = list(range(0, n))
        triplets = list(combinations(index_range, 3))
        for triplet in triplets:
            a, b, c = nums[triplet[0]], nums[triplet[1]], nums[triplet[2]]
            if a + b + c == 0:
                valid = sorted([a, b, c])
                if valid not in result:
                    result.append(valid)
        return result

I was so proud of myself until I was greeted with:

Memory Limit Exceeded

I tried to make this work with combinatorics but my implementation was either too slow or too memory hungry. The trick to solving this neatly is realising that this requires a slight modification from the Two Sum problem with input array sorted (Problem 167).

Solution Link to heading


# leetcode_15.py

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        sorted_nums = sorted(nums)
        triplets = []
        for i in range(0, n):
            # skip duplicates
            if i > 0 and sorted_nums[i] == sorted_nums[i - 1]:
                continue
            # from here on it follows from the TwoSum exercise with
            # input array sorted (Problem 167)
            l = i + 1
            r = n - 1
            while l < r:
                sigma = sorted_nums[i] + sorted_nums[l] + sorted_nums[r]
                if sigma > 0:
                    r -= 1
                elif sigma == 0:
                    triplets.append([sorted_nums[i], sorted_nums[l], sorted_nums[r]])
                    l += 1
                    while sorted_nums[l] == sorted_nums[l - 1] and l < r:
                        l += 1
                elif sigma < 0:
                    l += 1
        return triplets
Python statistics Link to heading
Runtime: 1133 ms -  beats 65.34 % of python3 submissions..
Memory Usage: 18.2 MB - beats 22.07 % of python3 submissions.
Complexity analysis Link to heading

  • Time: $ O(n) $, because of the loop.

  • Space: $ O(n) $ where $ n $ is the length of the input array sorted. There’s additional space required for the result triplets array, but it’s negligible compared to the cost of sorting the input array. To save space we could sort the array in place, but I’m ok with this solution.



Share on:
LinkedIn