We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

3Sum With Multiplicity

Number: 959

Difficulty: Medium

Paid? No

Companies: Apple, Quora

Problem Description

Given an integer array arr and an integer target, return the number of tuples (i, j, k) such that i < j < k and arr[i] + arr[j] + arr[k] == target. Since the answer can be very large, return it modulo 10^9 + 7.

Key Insights

  • Use a frequency counter for elements since arr[i] is in the range [0, 100].
  • Iterate through all possible combinations of numbers x, y, and z with x <= y <= z.
  • For each valid triplet (x, y, z) that sums to target, count the number of ways using combinatorial formulas:
    • All distinct: count[x] * count[y] * count[z].
    • Two numbers the same: use nC2 for the repeated element.
    • All three the same: use nC3.
  • Use modulo arithmetic (MOD = 10^9 + 7) at every step to avoid overflow.

Space and Time Complexity

Time Complexity: O(M^2), where M = 101 (the range of possible numbers), which is efficient given the constraints.
Space Complexity: O(M) for the frequency array.

Solution

The solution first counts the frequency of each number in the array. Then it iterates through all valid triplets (x, y, z) (with x <= y <= z) and checks if they sum up to the target. Depending on whether x, y, and z are distinct or have duplicates, the combination count is computed accordingly:

  • If x, y, and z are all the same, compute the combination as nC3.
  • If only two are the same, compute as nC2 multiplied by the count of the third number.
  • If all are distinct, use the direct product of the counts. This covers all cases while applying the modulo operation to the result.

Code Solutions

MOD = 10**9 + 7

def threeSumMulti(arr, target):
    # Create a frequency array for numbers 0 to 100
    freq = [0] * 101
    for num in arr:
        freq[num] += 1
    
    count = 0
    # Iterate through all possible values for x, y, and implicitly z
    for x in range(101):
        if freq[x] == 0:
            continue
        for y in range(x, 101):
            if freq[y] == 0:
                continue
            z = target - x - y
            if z < 0 or z > 100 or freq[z] == 0:
                continue
            if x == y and y == z:
                # All numbers are the same: nC3 = n*(n-1)*(n-2)/6
                count += freq[x] * (freq[x] - 1) * (freq[x] - 2) // 6
            elif x == y and y != z:
                # x and y are the same, z is different: nC2 for x multiplied by count[z]
                count += (freq[x] * (freq[x] - 1) // 2) * freq[z]
            elif x < y and y < z:
                # All distinct: product of counts
                count += freq[x] * freq[y] * freq[z]
            elif x < y and y == z:
                # x different, y and z are the same: count[x] multiplied by nC2 for y
                count += freq[x] * (freq[y] * (freq[y] - 1) // 2)
            count %= MOD
    return count

# Example usage:
print(threeSumMulti([1,1,2,2,3,3,4,4,5,5], 8))
← Back to All Questions