Algorithm

Problem Name: 923. 3Sum With Multiplicity

Problem Link: https://leetcode.com/problems/3sum-with-multiplicity/
 

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

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int threeSumMulti(int[] nums, int target) {
    Arrays.sort(nums);
    long answer = 0;
    for (int i = 0; i  <  nums.length; i++) {
      int updatedTarget = target - nums[i];
      int startIdx = i + 1;
      int endIdx = nums.length - 1;
      while (startIdx  <  endIdx) {
        if (nums[startIdx] + nums[endIdx] < updatedTarget) {
          startIdx++;
        } else if (nums[startIdx] + nums[endIdx] > updatedTarget) {
          endIdx--;
        } else if (nums[startIdx] != nums[endIdx]) {
          int leftIdx = 1;
          int rightIdx = 1;
          while (startIdx + 1  <  endIdx && nums[startIdx] == nums[startIdx + 1]) {
              leftIdx++;
              startIdx++;
          }
          while (endIdx - 1 > startIdx && nums[endIdx] == nums[endIdx - 1]) {
              rightIdx++;
              endIdx--;
          }

          answer = (answer + leftIdx * rightIdx) % 1000000007;
          startIdx++;
          endIdx--;
        } else {
          answer = (answer + ((endIdx - startIdx + 1) * (endIdx - startIdx) / 2)) % 1000000007;
          break;
        }
      }
    }
    return (int) answer;
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
arr = [1,1,2,2,3,3,4,4,5,5], target = 8

Output

x
–
+
cmd
20

#2 Code Example with Javascript Programming

Code - Javascript Programming


const threeSumMulti = function(A, target) {
  const d = {};
  let res = 0;
  const mod = Math.pow(10, 9) + 7;
  for (let i = 0; i  <  A.length; i++) {
    res += d[target - A[i]] >= 0 ? d[target - A[i]] : 0;
    res %= mod;
    for (let j = 0; j  <  i; j++) {
      d[A[i] + A[j]] = (d[A[i] + A[j]] || 0) + 1;
    }
  }
  return res % mod;
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
arr = [1,1,2,2,3,3,4,4,5,5], target = 8

Output

x
–
+
cmd
20

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def threeSumMulti(self, A, target):
        c = collections.Counter(A)
        res = 0
        for i, j in itertools.combinations_with_replacement(c, 2):
            k = target - i - j
            if i == j == k: res += c[i] * (c[i] - 1) * (c[i] - 2) // 6
            elif i == j != k: res += c[i] * (c[i] - 1) // 2 * c[k]
            elif k > i and k > j: res += c[i] * c[j] * c[k]
        return res % (10**9 + 7)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
arr = [1,1,2,2,2,2], target = 5

Output

x
–
+
cmd
12
Advertisements

Demonstration

Previous
#922 Leetcode Sort Array By Parity II Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#924 Leetcode Minimize Malware Spread Solution in C, C++, Java, JavaScript, Python, C# Leetcode