Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6

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:

1
2
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

Method 1 – Counting with Hash Map

Intuition

The key idea is to count the frequency of each number in the array, then iterate over all possible combinations of three numbers (x, y, z) such that x + y + z == target and x <= y <= z. For each valid triplet, calculate the number of ways to pick indices with the required values using combinatorics.

Approach

  1. Count the frequency of each number in arr using a hash map or array (since 0 <= arr[i] <= 100).
  2. Iterate over all possible values of x, y, and z such that x <= y <= z and x + y + z == target.
  3. For each triplet:
  • If all numbers are the same (x == y == z), use combinations: count[x] choose 3.
  • If two numbers are the same (x == y != z or x != y == z), use combinations: count[x] choose 2 * count[z] or count[x] * count[y] choose 2.
  • If all numbers are different, multiply their counts: count[x] * count[y] * count[z].
  1. Sum up all valid combinations, taking modulo 10^9 + 7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
   public int threeSumMulti(int[] arr, int target) {
      long[] count = new long[101];
      for (int num : arr) count[num]++;
      long ans = 0, mod = 1_000_000_007;
      for (int x = 0; x <= 100; ++x) {
        if (count[x] == 0) continue;
        for (int y = x; y <= 100; ++y) {
           if (count[y] == 0) continue;
           int z = target - x - y;
           if (z < y || z > 100 || count[z] == 0) continue;
           if (x == y && y == z) {
              ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;
           } else if (x == y && y != z) {
              ans += count[x] * (count[x] - 1) / 2 * count[z];
           } else if (x < y && y == z) {
              ans += count[x] * count[y] * (count[y] - 1) / 2;
           } else if (x < y && y < z) {
              ans += count[x] * count[y] * count[z];
           }
           ans %= mod;
        }
      }
      return (int) ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
   def threeSumMulti(self, arr: List[int], target: int) -> int:
      from collections import Counter
      cnt = Counter(arr)
      ans = 0
      mod = 10**9 + 7
      for x in range(101):
        if cnt[x] == 0:
           continue
        for y in range(x, 101):
           if cnt[y] == 0:
              continue
           z = target - x - y
           if z < y or z > 100 or cnt[z] == 0:
              continue
           if x == y == z:
              ans += cnt[x] * (cnt[x] - 1) * (cnt[x] - 2) // 6
           elif x == y != z:
              ans += cnt[x] * (cnt[x] - 1) // 2 * cnt[z]
           elif x < y == z:
              ans += cnt[x] * cnt[y] * (cnt[y] - 1) // 2
           elif x < y < z:
              ans += cnt[x] * cnt[y] * cnt[z]
           ans %= mod
      return ans

Complexity

  • ⏰ Time complexity: O(101^2) (since we iterate over all pairs (x, y) with 0 <= x <= y <= 100)
  • 🧺 Space complexity: O(1) (since the count array is of fixed size)