Solution by awice


  • 0

    Approach #1: Brute Force [Time Limit Exceeded]

    Intuition

    We try every triple of elements in the array. If it sums to zero, we record the answer.

    Algorithm

    For every triple of indices i < j < k, let's look at if A[i] + A[j] + A[k]. If it does, then sorted([A[i], A[j], A[k]]) occurs somewhere in the answer.

    We keep a set of our answers, then sort the answers at the end.

    Python

    class Solution(object):
        def threeSum(self, A):
            ans = set()
            for i in range(len(A)):
                for j in range(i+1, len(A)):
                    for k in range(j+1, len(A)):
                        if A[i] + A[j] + A[k] == 0:
                            ans.add(tuple(sorted([A[i], A[j], A[k]])))
            return sorted(ans)
    

    Complexity Analysis

    • Time Complexity: $$O(N^3 + N^2 \log N)$$, where $$N$$ is the length of the array. We do $$O(N^3)$$ work looking for triples to add to our answer, but our answer (which may have size $$O(N^2)$$) still needs to be sorted, which takes $$O(N^2 \log N^2) = O(N^2 \log N)$$ work.

      • To justify that our output may have size $$O(N^2)$$, notice after choosing an unordered pair of integers in the array, there is at most one solution. So the number of solutions is bounded above by the number of unordered pairs of integers.

      • For a more concrete example, say we have 1, 2, ..., K, K+1, K+2, ..., 2*K, and -3*K, -3*K+1, ..., -K-2. Then there are order $$O( (\frac{N}{4})^2 ) = O(N^2)$$ ways to choose a positive number from $$[1, K]$$ and another one from $$[K+1, 2K]$$, and all of these choices have a corresponding negative number so that the sum of these values is zero.

    • Space Complexity: $$O(N^2)$$. The answer could be up to $$O(N^2)$$ in size, as justified above.


    Approach 2: Reduction to Two-Sum, Pointer Variation [Accepted]

    Intuition

    Say the given array is A. For each A[i], we have an instance of the two-sum problem on A[i+1:] with target -A[i], where the two-sum problem is the problem of finding unique unordered pairs in an array that sum to a given target.

    Algorithm

    Sort A. For each A[i], we'll solve the corresponding two-sum problem, and take the combined answer at the end.

    To solve two-sum, we use a two-pointer approach. We'll ask for every j, what is the largest k that makes our sum A[i] + A[j] + A[k] equal to zero? If our sum is too big, then we will reduce k. If our sum is too small, then we know there was no such k that could have made this zero, so we'll increment j. Then, since A[j+1] >= A[j], we do not need to check any k larger than the one we have now.

    One annoying detail for those familiar with the basics of two-pointer approaches, is that we didn't want to take repeats into our answer. A straightforward way to handle this is to take the answer in a Set-type data structure, then sort it at the end. However, this sorting introduces a $$O(N^2 \log N)$$ factor which is less desirable.

    A more efficient way is to have our pointer skip repeated values. If we group the sorted array into groups of the same value, then we will only consider the left-most value in each group (right-most for the k pointer.) This is the motivation behind code that checks for A[i-1] == A[i], or while j < k and A[j] == A[j+1], etc.

    Python

    class Solution(object):
        def threeSum(self, A):
            A.sort()
            ans = []
            N = len(A)
            for i in range(N):
                if i > 0 and A[i-1] == A[i]:
                    continue
                j, k = i+1, N-1
                while j < k:
                    if A[i] + A[j] + A[k] < 0:
                        j += 1
                    elif A[i] + A[j] + A[k] > 0:
                        k -= 1
                    else:
                        ans.append((A[i], A[j], A[k]))
                        while j < k and A[j] == A[j+1]:
                            j += 1
                        j += 1
                        while j < k and A[k] == A[k-1]:
                            k -= 1
                        k -= 1
            return ans
    

    Complexity Analysis

    • Time Complexity: $$O(N^2)$$. The outer loop (for i = 0..N-1) is $$O(N)$$. At every step in the while j < k loop, k-j decreases by at least one, which corresponds to an inner loop of $$O(N)$$.

    • Space Complexity: $$O(N^2)$$. The answer could be up to $$O(N^2)$$ in size, as justified in our answer to Approach #1.


    Approach 3: Reduction to Two-Sum, Multiplicity Variation [Accepted]

    Intuition

    What makes this problem hard is having to deal with repeated values in the input and output. This suggests that we instead work with unique values, and keep a count of their multiplicity on the side. For example, instead of working with an array where 19 occurs 4 times, we will work with a structure where 19 appears once, and we also know it has a count of 4 in the initial array.

    The benefit of this approach is that every candidate answer under consideration is unique. The drawback is that our logic and case-work becomes more complicated.

    Algorithm

    Let A be the given array, count[x] be the number of times x appears in A, and keys be a sorted list of unique values in A.

    As before, for each unique value x = keys[i] in A, we would like to know all pairs (y, z) (y = keys[j], z = keys[k]) with x <= y <= z so that x + y + z == 0. What makes this tricky is that x, y, and z could be the same value. That means, instead of $$i < j < k$$, we are considering $$i \leq j \leq k$$.

    Whenever we have keys[i] + keys[j] + keys[k] == 0, we need to check whether there were enough elements in A to actually make this sum. For example, if we have A = [-2, 1], then keys = [-2, 1], but we can't make zero. However, A = [-2, 1, 1] with keys = [-2, 1] can make zero. So we have to look at our count carefully.

    When say, i == j or j == k, then we used keys[j] twice, and we need count[keys[j]] >= 2. When i == j == k, then we use keys[j] three times, and we need count[keys[j]] >= 3. It's impossible to have i != j and i == k, so these are all the cases.

    Python

    class Solution(object):
        def threeSum(self, A):
            count = collections.Counter(A)
            keys = sorted(count)
    
            def twosum(i, target):
                #all two-elements in keys[i:] summing to target
                j, k = i, len(keys) - 1
                while j <= k:
                    if keys[j] + keys[k] < target:
                        j += 1
                    elif keys[j] + keys[k] > target:
                        k -= 1
                    else:
                        if count[keys[j]] >= 1 + (i==j) + (j==k):
                            yield keys[j], keys[k]
                        j += 1
                        k -= 1
    
            ans = []
            for i, x in enumerate(keys):
                for y, z in twosum(i, -x):
                    ans.append((x, y, z))
            return ans
    

    Complexity Analysis

    • $$O(N^2)$$ time and space complexity. The analysis is the same as in Approach #2.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.