Solution: 3Sum With Multiplicity
Tags: algorithms, javascript, java, python
Published: 2021-03-23 14:05:38

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/3sum-with-multiplicity/discuss/1123830).*

---

#### [Leetcode Problem #923 (*Medium*): 3Sum With Multiplicity](https://leetcode.com/problems/3sum-with-multiplicity/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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:||
|---:|---|
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]):<br>(1, 2, 5) occurs 8 times;<br>(1, 3, 4) occurs 8 times;<br>(2, 2, 4) occurs 2 times;<br>(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:<br>We choose one 1 from [1,1] in 2 ways,<br>and two 2s from [2,2,2,2] in 6 ways.

---

#### ***Constraints:***
>
 - 3 <= arr.length <= 3000
 - 0 <= arr[i] <= 100
 - 0 <= target <= 300

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The naive approach here would be to attempt all permutations, but that would run up to **2.7e10** attempts. The first important thing to notice is that the range of numbers is very small at **[0,100]**. With that few number options, any large input array (**A**) will have many duplicates, which means we're looking at a **combinatorics** solution.

In order to use the combinatorics shortcut, however, we'll first have to make a **frequency map** of the numbers in **A**. We could always use a standard map for this, but since the range of numbers is so small and **0-indexed**, it makes more sense to use an **array** instead.

After we've iterated through **A** and filled our number map (**nmap**) with the number frequencies, we can get down to the real work. The normal approach here would be to figure out the distinct numbers available and use nested loops to attempt every possible permutation. But rather than doing this, which would require many array calls, we can again take advantage of the fact that the number range is so small.

We can iterate through every possible permutation from **[0,100]**, regardless of wheter the numbers are in **A**. Since we've made a frequency map, those numbers will be represented as **0**'s, which will handily prevent anything from being added to our answer (**ans**) for permutations that we can't make, and by using simple math instead of many array calls, we can actually be more performant.

Still, there are ways to streamline this process. The basic approach will be to use a **2-pointer system** to find two of our values and then mathematically figure the third, before applying the proper permutation formula to the values.

It should be apparent that our largest value (**k**) can never go above the target (**T**), nor can it obviously go above the max value of **100**, so we can start it out at **min(T, 100)** and decrement from there. Also, since it will always represents the largest of the three values, it can never go below **T / 3**, because then the two smaller numbers would never be able to bring it up to **T**.

Moving down to the next value (**j**), we can see that it can never be larger than **k** by definition, nor can it be larger than the remaining amount of space (**rem**) left to **T**, so we should start it at **min(rem, k)**. Similar to **k**, **j** can also never go below **rem / 2**.

Once we have two of the three values, we can check for their frequencies. If any of them are **0**'s, then it will automatically make the result of its permutation check a **0** as well. We can also potentially save some processing by checking for **0**'s and **continuing** before applying the combinatorics formulas.

If **i == k**, then we know that **i == j == k** because **j** has to be between **i** and **k**, so we'll have to use the **n choose 3** formula. We should also check if any two other values are the same, then we should use **(n choose 2) * (n choose 1)**. Otherwise, we can just use the simple combinations formula.

Then it's important to remember to apply the **modulo** before **returning**.

---

#### ***Implementation:***

Javascript was actually faster with an approach that featured isolating the actual distinct elements, sorting them, and then running efficiently through the combinations, but the code was much longer and more complex. This method is much easier and nearly as fast. In either case, we should use a typed array here for the arraymap.

Java was oddly slower at the iteration shortcuts and actually ran faster without the added processes.

Java and C++ should use **long** for their **ans** (prior to returning it, at least), and even for **nmap**, otherwise we'll have to cast those values to **long** each time anyway.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var threeSumMulti = function(A, T) {
    let nmap = new Uint16Array(101), third = T / 3, ans = 0
    for (let i in A) nmap[A[i]]++
    for (let k = Math.min(T, 100); k >= third; k--) {
        let rem = T - k, half = rem / 2
        for (let j = Math.min(rem, k); j >= half; j--) {
            let i = rem - j, x = nmap[i], y = nmap[j], z = nmap[k], res
            if (i === k) res = x * (x-1) * (x-2) / 6
            else if (i === j) res = x * (x-1) / 2 * z
            else if (j === k) res = x * y * (y-1) / 2
            else res = x * y * z
            ans = (ans + res) % 1000000007
        }
    }
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def threeSumMulti(self, A, T):
        nmap, third, ans = [0 for _ in range(101)], ceil(T / 3) - 1, 0
        for num in A: nmap[num] += 1
        for k in range(min(T,100), third, -1):
            rem = T - k
            half = ceil(rem / 2) - 1
            for j in range(min(rem, k), half, -1):
                i = rem - j
                x, y, z = nmap[i], nmap[j], nmap[k]
                if i == k: ans += x * (x-1) * (x-2) // 6
                elif i == j: ans += x * (x-1) // 2 * z
                elif j == k: ans += x * y * (y-1) // 2
                else: ans += x * y * z
        return ans % 1000000007
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int threeSumMulti(int[] A, int T) {
        long[] nmap = new long[101];
        long ans = 0;
        for (int num : A) nmap[num]++;
        for (int k = 100; k >= 0; k--)
            for (int j = k; j >= 0; j--) {
                int i = T - k - j;
                if (i > j || i < 0) continue;
                long x = nmap[i], y = nmap[j], z = nmap[k], res = x * y * z;
                if (res == 0) continue;
                if (i == k) res = x * (x-1) * (x-2) / 6;
                else if (i == j) res = x * (x-1) / 2 * z;
                else if (j == k) res = x * y * (y-1) / 2;
                ans += res;
            }
        return (int)(ans % 1000000007);
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int threeSumMulti(vector<int>& A, int T) {
        long nmap[101] = {0}, ans = 0;
        double third = T / 3;
        for (int num : A) nmap[num]++;
        for (int k = min(T, 100); k >= third; k--) {
            int rem = T - k;
            double half = rem / 2;
            for (int j = min(rem, k); j >= half; j--) {
                int i = rem - j;
                if (i > j || i < 0) continue;
                long x = nmap[i], y = nmap[j], z = nmap[k], res = x * y * z;
                if (res == 0) continue;
                if (i == k) res = x * (x-1) * (x-2) / 6;
                else if (i == j) res = x * (x-1) / 2 * z;
                else if (j == k) res = x * y * (y-1) / 2;
                ans += res;
            }
        }
        return (int)(ans % 1000000007);
    }
};
```