923. 3Sum With Multiplicity

MediumArrayHash TableTwo PointersCountingSorting

Problem Description

The problem requires us to find the number of distinct triplets (i, j, k) in an integer array arr where the condition i < j < k is satisfied, and the sum of the elements at these indices is equal to a given target integer. Specifically, arr[i] + arr[j] + arr[k] == target should hold true for the counted triplets. Since the number of such triplets can be quite large, we are asked to return the answer modulo 10^9 + 7 to keep the output within integer value limits.

Intuition

The key to solving this problem is to consider how we can traverse the array to find all the valid triplets efficiently. We want to avoid checking all possible triplets due to the high time complexity that approach would imply.

The algorithm usually starts by counting the occurrences of each number in the array using a Counter, which is a special kind of dictionary in Python. This allows us to know how many times each number appears in the array without traversing it multiple times.

Once we have these counts, we iterate through the array for the second number of the triplet. For each possible second number b at index j, we decrease its count by 1 to ensure that we do not use the same instance of b when looking for the third number.

Next, we traverse the array again up to the second number's index j to find every possible first number a. With both a and b known, we calculate the required third number c by subtracting the sum of a and b from the target.

If c is present in our Counter (which means it's somewhere in the original array), we can form a triplet (a, b, c) that sums up to target. We then add the count of c from our Counter to our answer, since there are as many possibilities to form a triplet with a and b as the count of c. It's important to use modulo with 10^9 + 7 during each addition to keep the number within bounds.

The iteration is cleverly structured to ensure that each element is used according to its occurrence and that i < j < k always holds true by managing the index and counts carefully.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The solution uses a combination of a hashmap (in Python, a Counter) and a two-pointer approach to find the valid triplets.

The algorithm goes as follows:

A Counter (which is a specialized hashmap/dictionary in Python) is initialized to count the occurrences of the elements in the given arr. This data structure allows for O(1) access to the count of each element, which is essential for efficient computation of the number of triplets.
We define a variable ans to keep the running total of the number of valid triplets.
The mod variable is set to 10**9 + 7 to ensure that we perform all our arithmetic operations modulo this number.
We loop through each element b of the array using its index j. This element is considered the second element of our potential triplet.
Before starting the inner loop, we decrease the count of b in the Counter by one. This ensures that we don't count the same element b twice when looking for the third element of the triplet.
An inner loop runs through the array up to the current index j, selecting each element a as a candidate for the first element of the triplet. The index i is implicit in this loop.
We then calculate the required third element c of the triplet by subtracting the sum of a and b from the target, i.e., c = target - a - b.
The total count of valid triplets is then incremented by the count of c from the Counter if c is present. We use modulo mod to keep the answer within the range of valid integers.
Finally, we return ans as the result.

The algorithm ensures that no element is used more often than it appears in the array, and the i < j < k condition is naturally upheld by the two nested loops and the management of the Counter.

The use of the Counter and looping through the array only once per element significantly reduces the computational complexity compared to checking all possible triplets directly. This pattern is a common approach in problems involving counting specific arrangements or subsets in an array, especially when the array elements are bound to certain conditions.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example with arr = [1, 1, 2, 2, 3, 3] and target = 6. We want to find all unique triplets i, j, k (with i < j < k) such that arr[i] + arr[j] + arr[k] == target.

We begin by initializing a Counter to count the occurrences of each element in arr. The Counter will look like this: {1:2, 2:2, 3:2} which reflects that each number 1, 2, and 3 occurs twice in the array.
Set ans = 0 to keep track of the total number of valid triplets and mod = 10**9 + 7 for modulo operations.
We now look for the second number b for all triplets by iterating through arr. Consider j=2 where b = arr[j] = 2.
We decrement the count of b in Counter by 1. Now the Counter will look like this: {1:2, 2:1, 3:2}.
We start the inner loop to select a as the first element of the triplet. We iterate from start to j-1, in this case, from 0 to 1.
For a = arr[0] = 1 at i=0, we calculate the needed c = target - a - b = 6 - 1 - 2 = 3.
The count of c in the Counter is 2, which means we can form two triplets (1, 2, 3) with i=0, j=2. We increment ans by the count of c in Counter. So, ans = (ans + 2) % mod.
For a = arr[1] = 1 at i=1, we calculate c = 6 - 1 - 2 = 3 again. Since i < j, it's valid and we have not used the same a as before. ans is updated to ans = (ans + 2) % mod.
Continue this process for every j from 0 to len(arr), and you'll count all valid triplets.
After finishing, ans is the total number of valid triplets.

For this example, the possible triplets are two instances of (1, 2, 3) using the first 1 and first 2, two using the first 1 and second 2, two using the second 1 and first 2, and two using the second 1 and second 2. These are counted as four unique triplets because the pairs (1, 2) are distinct by their positions. There's no triplet using any two '3's because that would require i not to be less than j. Therefore, ans = 4.

Remember that in a real problem with a large arr, not all triples (a, b, c) will be unique because of duplicate values, and there will be a variable number of contributions to ans from each triplet depending on how many times each value occurs.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def threeSumMulti(self, arr: List[int], target: int) -> int:
5        # Create a counter to keep track of occurrences of each number in the array
6        count = Counter(arr)
7      
8        # Initialize answer to 0
9        answer = 0
10      
11        # Define the modulo value for large numbers to handle overflow
12        modulo = 10**9 + 7
13      
14        # Iterate over the array using index and value
15        for index, second_value in enumerate(arr):
16            # Decrement the count of the current element to avoid overcounting
17            count[second_value] -= 1
18          
19            # Iterate over the elements up to the current index
20            for i in range(index):
21                first_value = arr[i]  # Get the current first value
22              
23                # Calculate the third value that would make the triplet sum to the target
24                third_value = target - first_value - second_value
25              
26                # Add the number of occurrences of the third value to the answer
27                # Use modulo to avoid overflow
28                answer = (answer + count[third_value]) % modulo
29      
30        # Return the total number of triplets that sum up to the target
31        return answer
32```
33
34Here's a breakdown of the changes made:
35
361. Imported `List` from `typing` to use type hints for list parameters.
372. Replaced `cnt` with `count` for more clarity that this variable represents occurrences of numbers.
383. Replaced `j` and `i` with `index` and `i` respectively for better readability in loops.
394. Renamed `a` and `b` to `first_value` and `second_value`, while `c` to `third_value`, to clearly distinguish the triplet elements.
405. Added comments explaining each portion of the code, outlining what each section does and why certain operations are performed, such as the purpose of the modulo operation.
416. Ensured that the method names and the logic of the function remained unchanged. 
42
43To complete this snippet, you'll need to add the following import if not already at the top of your file:
44
45```python
46from typing import List
47

1class Solution {
2    // Define the modulo constant for taking modulus
3    private static final int MOD = 1_000_000_007; // 1e9 + 7 is represented as 1000000007
4
5    public int threeSumMulti(int[] arr, int target) {
6        int[] count = new int[101]; // Array to store count of each number, considering constraint 0 <= arr[i] <= 100
7        // Populate the count array with the frequency of each value in arr
8        for (int num : arr) {
9            ++count[num];
10        }
11        long ans = 0; // To store the result, using long to avoid integer overflow before taking the modulus
12
13        // Iterate through all elements in arr to find triplets
14        for (int j = 0; j < arr.length; ++j) {
15            int second = arr[j]; // The second element in the triplet
16            --count[second]; // Decrement count since this number is being used in the current triplet
17
18            // Iterate from the start of the array to the current index 'j'
19            for (int i = 0; i < j; ++i) {
20                int first = arr[i]; // The first element in the triplet
21                int third = target - first - second; // Calculate the third element
22
23                // Check if third element is within range and add the count to the answer
24                if (third >= 0 && third <= 100) {
25                    ans = (ans + count[third]) % MOD; // Use the modulo to avoid overflow and get the correct result
26                }
27            }
28        }
29        // Cast and return the final answer as an integer
30        return (int) ans;
31    }
32}
33

1class Solution {
2public:
3    // Modulo constant for the problem
4    const int MOD = 1e9 + 7;
5
6    // Function to calculate the number of triplets that sum up to the target
7    int threeSumMulti(vector<int>& arr, int target) {
8        // Array to store the count of each number in the range [0, 100]
9        int count[101] = {0};
10
11        // Populating the count array
12        for (int num : arr) {
13            ++count[num];
14        }
15
16        // Variable to store the result
17        long answer = 0;
18
19        // Iterate through each element in the array to use it as the second element of the triplet
20        for (int j = 0; j < arr.size(); ++j) {
21            // Select the current element as the second element of the triplet
22            int secondElement = arr[j];
23            // Decrement the count as this element is considering for pairing
24            --count[secondElement];
25
26            // Iterate through elements up to the current second element to find the first element
27            for (int i = 0; i < j; ++i) {
28                int firstElement = arr[i];
29                // Calculate the required third element to meet the target
30                int thirdElement = target - firstElement - secondElement;
31
32                // If the third element is within the valid range
33                if (thirdElement >= 0 && thirdElement <= 100) {
34                    // Add the count of the third element to the answer
35                    answer += count[thirdElement];
36                    // Ensure answer is within the MOD range
37                    answer %= MOD;
38                }
39            }
40        }
41
42        // Return the final answer
43        return answer;
44    }
45};
46

1// Constant for modulo operations
2const MOD: number = 1e9 + 7;
3
4// This function calculates the number of triplets in the array that sum up to the target value
5function threeSumMulti(arr: number[], target: number): number {
6    // Array to store the count of occurrence for each number within the range [0, 100]
7    let count: number[] = new Array(101).fill(0);
8
9    // Populate the count array with the number of occurrences of each element
10    for (let num of arr) {
11        count[num]++;
12    }
13
14    // Variable to store the result
15    let answer: number = 0;
16
17    // Iterate through each element in the array to use it as the second element of the triplet
18    for (let j = 0; j < arr.length; j++) {
19        // The current element is selected as the second element of the triplet
20        let secondElement: number = arr[j];
21        // Decrement the count for this element as it is being considered for pairing
22        count[secondElement]--;
23
24        // Iterate over all possible first elements up to the current second element
25        for (let i = 0; i < j; i++) {
26            let firstElement: number = arr[i];
27            // Calculate the required third element to meet the target sum
28            let thirdElement: number = target - firstElement - secondElement;
29
30            // Check if the third element is within the valid range [0, 100]
31            if (thirdElement >= 0 && thirdElement <= 100) {
32                // Add the count of the third element to the answer
33                answer += count[thirdElement];
34                // Ensure answer remains within the range specified by MOD
35                answer %= MOD;
36            }
37        }
38    }
39
40    // Return the final computed answer
41    return answer;
42}
43
44// Example usage of the function
45// let arrExample = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5];
46// let targetExample = 8;
47// let result = threeSumMulti(arrExample, targetExample);
48// console.log(result); // Output the result
49

Time and Space Complexity

The time complexity of the provided Python code snippet is O(n^2) where n is the number of elements in the input list arr. This complexity arises because there is a nested for-loop where the outer loop runs through the elements of arr (after decrementing the count of the current element), and the inner loop iterates up to the current index j of the outer loop. For each pair (a, b), the code looks up the count of the third element c that is needed to sum up to the target. Even though the lookup in the counter is O(1), the nested loops result in quadratic complexity.

The space complexity of the code is O(m) where m is the number of unique elements in the input list arr. This complexity is due to the use of a Counter to store frequencies of all unique elements in arr. The space taken by the counter will directly depend on the number of unique values.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don’t know