{x}
blog image

3Sum With Multiplicity

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 109 + 7.

 

Example 1:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: 
Enumerating by the values (arr[i], arr[j], arr[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

Example 2:

Input: arr = [1,1,2,2,2,2], target = 5
Output: 12
Explanation: 
arr[i] = 1, arr[j] = arr[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

Example 3:

Input: arr = [2,1,3], target = 6
Output: 1
Explanation: (1, 2, 3) occured one time in the array so we return 1.

 

Constraints:

  • 3 <= arr.length <= 3000
  • 0 <= arr[i] <= 100
  • 0 <= target <= 300

Solution Explanation: 3Sum With Multiplicity

This problem asks to find the number of triplets (i, j, k) in an array arr such that i < j < k and arr[i] + arr[j] + arr[k] == target. The solution presented uses a counting approach to efficiently handle potential duplicates within the array.

Approach:

  1. Counting Occurrences: First, we count the occurrences of each element in the input array arr. This is done efficiently using a hash map (or an array if the range of elements is known and relatively small, as in this case where elements are in the range [0, 100]). This step takes O(n) time, where n is the length of arr.

  2. Iterative Triplet Search: We iterate through the array arr. For each element arr[j], we do the following:

    • Decrement Count: We decrement the count of arr[j] in the counter. This is crucial because we're going to consider arr[j] as part of a potential triplet, and we want to avoid counting the same element multiple times within the triplet.

    • Inner Loop: We iterate through the elements before arr[j] (i.e., arr[i] where i < j). For each arr[i], we calculate c = target - arr[i] - arr[j]. c represents the third element needed to sum up to the target.

    • Check and Add: If c exists in the counter (i.e., it's a valid element in the array and its count is greater than 0), we add its count (cnt[c]) to the total count of triplets (ans). This implicitly considers all possible combinations with the chosen arr[i] and arr[j].

  3. Modulo Operation: We apply the modulo operation (% (10**9 + 7)) after each addition to prevent integer overflow, as the problem specifies.

  4. Return Result: Finally, we return the total count of triplets (ans).

Time and Space Complexity:

  • Time Complexity: O(n^2). The nested loops dominate the runtime. The initial counting step is O(n).

  • Space Complexity: O(C), where C is the range of elements in arr. In this problem, C = 101 (0 to 100). The space used is primarily for the counter. If the range of elements were unbounded, a hash map would be needed resulting in O(n) space complexity in the worst case.

Code Examples (Python):

from collections import Counter
 
class Solution:
    def threeSumMulti(self, arr: List[int], target: int) -> int:
        mod = 10**9 + 7
        cnt = Counter(arr)
        ans = 0
        for j, b in enumerate(arr):
            cnt[b] -= 1
            for i in range(j):
                a = arr[i]
                c = target - a - b
                if c >= 0 and c <= 100 and cnt[c] > 0:
                    ans = (ans + cnt[c]) % mod
        return ans

The code in other languages (Java, C++, Go, TypeScript) follows the same logic and algorithmic structure, differing only in syntax and standard library usage. The core idea of counting and iterative triplet search remains consistent across all implementations.