Solution


Approach Notes

The approaches described below assume some familiarity with the two pointer technique that can be used to solve the LeetCode problem "Two Sum".

In the problem, we have a sorted array A of unique elements, and want to know how many i < j with A[i] + A[j] == target.

The idea that does it in linear time, is that for each i in increasing order, the j's that satisfy the equation A[i] + A[j] == target are decreasing.

def solve(A, target):
    # Assume A already sorted
    i, j = 0, len(A) - 1
    ans = 0
    while i < j:
        if A[i] + A[j] < target:
            i += 1
        elif A[i] + A[j] > target:
            j -= 1
        else:
            ans += 1
            i += 1
            j -= 1
    return ans

This is not a complete explanation. For more on this problem, please review the LeetCode problem "Two Sum".


Approach 1: Three Pointer

Intuition and Algorithm

Sort the array. For each i, set T = target - A[i], the remaining target. We can try using a two-pointer technique to find A[j] + A[k] == T. This approach is the natural continuation of trying to make the two-pointer technique we know from previous problems, work on this problem.

Because some elements are duplicated, we have to be careful. In a typical case, the target is say, 8, and we have a remaining array (A[i+1:]) of [2,2,2,2,3,3,4,4,4,5,5,5,6,6]. We can analyze this situation with cases.

Whenever A[j] + A[k] == T, we should count the multiplicity of A[j] and A[k]. In this example, if A[j] == 2 and A[k] == 6, the multiplicities are 4 and 2, and the total number of pairs is 4 * 2 = 8. We then move to the remaining window A[j:k+1] of [3,3,4,4,4,5,5,5].

As a special case, if A[j] == A[k], then our manner of counting would be incorrect. If for example the remaining window is [4,4,4], there are only 3 such pairs. In general, when A[j] == A[k], we have pairs (j,k) (with j < k) that satisfy A[j] + A[k] == T, where is the multiplicity of A[j] (in this case ).

For more details, please see the inline comments.

Complexity Analysis

  • Time Complexity: , where is the length of A.

  • Space Complexity: .


Approach 2: Counting with Cases

Intuition and Algorithm

Let count[x] be the number of times that x occurs in A. For every x+y+z == target, we can try to count the correct contribution to the answer. There are a few cases:

  • If x, y, and z are all different, then the contribution is count[x] * count[y] * count[z].

  • If x == y != z, the contribution is .

  • If x != y == z, the contribution is .

  • If x == y == z, the contribution is .

(Here, denotes the binomial coefficient .)

Each case is commented in the implementations below.

Complexity Analysis

  • Time Complexity: , where is the length of A, and is the maximum possible value of A[i]. (Note that this solution can be adapted to be even in the case that is very large.)

  • Space Complexity: .


Approach 3: Adapt from Three Sum

Intuition and Algorithm

As in Approach 2, let count[x] be the number of times that x occurs in A. Also, let keys be a sorted list of unique values of A. We will try to adapt a 3Sum algorithm to work on keys, but add the correct answer contributions.

For example, if A = [1,1,2,2,3,3,4,4,5,5] and target = 8, then keys = [1,2,3,4,5]. When doing 3Sum on keys (with i <= j <= k), we will encounter some tuples that sum to the target, like (x,y,z) = (1,2,5), (1,3,4), (2,2,4), (2,3,3). We can then use count to calculate how many such tuples there are in each case.

This approach assumes familiarity with 3Sum. For more, please visit the associated LeetCode problem here https://leetcode.com/problems/3sum.

Complexity Analysis

  • Time Complexity: , where is the length of A.

  • Space Complexity: .


Analysis written by: @awice.