Scale Engineer

3Sum With Multiplicity

Med
#0877Time: 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: O(1) - We only use a few variables for loops and the counter, so the space required is constant.1 company
Patterns
Two PointersCounting
Algorithms
Sorting
Data structures
ArrayHash Table
Companies
Quora

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

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

  1. Initialize a long counter ans to 0 and MOD = 1_000_000_007.
  2. Get the length of the array, n.
  3. 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.
  4. Inside the innermost loop, check if the sum of elements at these indices equals the target: arr[i] + arr[j] + arr[k] == target.
  5. If the condition is true, increment the ans counter.
  6. After the loops complete, return ans modulo MOD.

Walkthrough

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

Time

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

O(1) - We only use a few variables for loops and the counter, so the space required is constant.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem