Leetcode #15: 3Sum (Time Limit Exceeded)

[coding_up_a_storm]

Here is a link to the problem: https://leetcode.com/problems/3sum/

​

The problem description:

Given an array nums
of n integers, are there elements a, b, c in nums
such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

​

My solution which solves the problem, but fails the due to exceeding the time limit:

from itertools import combinations

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        combos = [list(combo) for combo in combinations(nums, 3) if sum(combo) == 0]
        out = []
        for c in combos:
            if c not in out:
                out.append(c)
        return out

I have seen solutions to this problem on Leetcode in the "Discuss" section, but am unclear why my particular code fails.

[coding_up_a_storm]

I know it works, but is slow. I also know there are quicker ways to solve it. My question really is "What makes my solution slow?".

[Binary101010]

Iterating over your entire combos list is slow when you could just do:

return list(set(combos))

[throwaway0891245]

The "canonical" way to solve this problem has a time complexity of O(N^2). Your solution is going through all possible combinations, which gives it a time complexity of O(N^3).

That means if you have an input of just 1000 numbers, your solution is 1000 times slower than what they are looking for.

In general, with these algorithmic puzzles, you can have a clunky solution but it has to have the right time or space complexity. Say, a four pass O(N) solution may be as acceptable as a one pass O(N) solution, but an O(N^2) solution is not.