3Sum With Multiplicity

MEDIUM

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⁹ + 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

Approaches

Checkout 3 different approaches to solve 3Sum With Multiplicity. Click on different approaches to view the approach and algorithm in detail.

Brute Force

This is the most straightforward and intuitive approach. It involves checking every possible combination of three distinct elements from the array to see if they sum up to the target. We use three nested loops to generate all triplets of indices (i, j, k) with the condition i < j < k and sum the corresponding elements.

Algorithm

Initialize a long counter ans to 0 and MOD = 1_000_000_007.
Get the length of the array, n.
Use three nested loops to iterate through all possible triplets of indices (i, j, k) such that i < j < k.
- The outer loop for i runs from 0 to n - 3.
- The middle loop for j runs from i + 1 to n - 2.
- The inner loop for k runs from j + 1 to n - 1.
Inside the innermost loop, check if the sum of elements at these indices equals the target: arr[i] + arr[j] + arr[k] == target.
If the condition is true, increment the ans counter.
After the loops complete, return ans modulo MOD.

The algorithm iterates through every unique triplet of indices (i, j, k). For each triplet, it calculates the sum arr[i] + arr[j] + arr[k] and compares it with the target. If they are equal, a counter is incremented. This process guarantees that all valid combinations are found. However, its cubic time complexity makes it impractical for an array size of up to 3000.

class Solution {
    public int threeSumMulti(int[] arr, int target) {
        long ans = 0;
        int n = arr.length;
        int MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (arr[i] + arr[j] + arr[k] == target) {
                        ans++;
                    }
                }
            }
        }
        return (int)(ans % MOD);
    }
}

Complexity Analysis

Time Complexity: O(N³), where N is the length of the array `arr`. With N up to 3000, this is approximately 2.7 * 10¹⁰ operations, which is too slow.Space Complexity: O(1) - We only use a few variables for loops and the counter, so the space required is constant.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space.

Cons:

Extremely inefficient for the given constraints.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms.

Code Solutions

Checking out 3 solutions in different languages for 3Sum With Multiplicity. Click on different languages to view the code.

class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int threeSumMulti(int[] arr, int target) {
    int[] cnt = new int[101];
    for (int v : arr) {
      ++cnt[v];
    }
    long ans = 0;
    for (int j = 0; j < arr.length; ++j) {
      int b = arr[j];
      --cnt[b];
      for (int i = 0; i < j; ++i) {
        int a = arr[i];
        int c = target - a - b;
        if (c >= 0 && c <= 100) {
          ans = (ans + cnt[c]) % MOD;
        }
      }
    }
    return (int)ans;
  }
}

Video Solution

Watch the video walkthrough for 3Sum With Multiplicity

Algorithms:

Sorting

Patterns:

Two PointersCounting

Data Structures:

ArrayHash Table

Companies:

Quora |