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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

3Sum With Multiplicity

Difficulty: Medium

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. As the answer can be very large, return it modulo 10^9 + 7.

Key Insights

  • We need to count the number of unique triplets (i, j, k) that satisfy the sum condition.
  • The order of the triplets matters, meaning we need to ensure i < j < k.
  • Since the sum can be very large, we need to use modulo 10^9 + 7 for the final count.
  • We can utilize a counting approach based on the frequency of numbers in the array.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1) (excluding the input array)

Solution

To solve the problem, we can use a counting approach. First, we will count the frequency of each number in the input array, given the constraints that the numbers are between 0 and 100. We can then iterate over all possible pairs of numbers (a, b) and calculate the third number (c) needed to reach the target. Depending on the values of a, b, and c, we will calculate the number of valid combinations based on their counts using combinatorial counting.

Code Solutions

from collections import Counter

def threeSumMulti(arr, target):
    mod = 10**9 + 7
    count = Counter(arr)
    keys = sorted(count.keys())
    result = 0
    
    for i in range(len(keys)):
        for j in range(i, len(keys)):
            a = keys[i]
            b = keys[j]
            c = target - a - b
            
            if c in count:
                if a == b == c:
                    # all three numbers are the same
                    result += count[a] * (count[a] - 1) * (count[a] - 2) // 6
                elif a == b:
                    # a and b are the same, c is different
                    result += count[a] * (count[a] - 1) // 2 * count[c]
                elif b == c:
                    # b and c are the same, a is different
                    result += count[b] * (count[b] - 1) // 2 * count[a]
                elif a < b < c:
                    # all three numbers are different
                    result += count[a] * count[b] * count[c]
                    
    return result % mod
← Back to All Questions