3Sum With Multiplicity

Problem Statement

In this problem, we are given an integer array arr and a target integer value target. Our task is to find the number of unique triplets (i, j, k) such that:

1. The indices meet the condition i < j < k which means each index must be strictly less than the one that follows.
2. The sum of elements at these indices equals the target value (arr[i] + arr[j] + arr[k] == target).

Given the constraints that the resulting count could be very large, the result should be provided modulo 10^9 + 7 to manage the size of the output.

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]): (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

Approach and Intuition

To tackle this problem, understanding the constraints and data presented in the examples will guide the selection of an appropriate algorithm. The examples demonstrate scenarios of varying array sizes and structures, making clear that the solution must handle:

• Duplicates within the array affecting the counting of valid combinations.
• Larger array lengths up to 3000, requiring a method faster than the naive O(n^3) approach.

Steps to Formulate a Solution:

1. Brute Force Approach:

   • You could start with a triple nested loop to check every possible tuple (i, j, k). While this directly implements the given condition (i < j < k and arr[i] + arr[j] + arr[k] == target), it is not efficient for large inputs due to O(n^3) time complexity.

2. Optimized Search with Sorting:

   • Sorting the array can help speed up the search for target sums using pointers or binary search. After sorting, you can use one loop to fix the first element and a two-pointer technique to find pairs that sum up with the fixed element to the target. This reduces the complexity to O(n^2).

3. Using a HashMap for Frequency Counting and Two-Sum Approach:

   • Count frequencies of elements first. For each unique pair (arr[i], arr[j]), calculate the required third element triad = target - arr[i] - arr[j]. Check if triad exists in the hash map.
   • Maintain a hash map during iteration to store potential complements while updating counts to avoid double counting and ensure i < j < k order is respected.

Given that our constraints allow a length up to 3000, the n^2 approach with careful management of counts and combinations could efficiently solve the problem within acceptable time limits. Moreover, considering modulo operations will be essential in each counting step to stay within the required limits.

Solutions

class Solution {
    public int threeSumCount(int[] nums, int targetSum) {
        int MODULO = 1_000_000_007;

        long[] frequency = new long[101];
        int uniqueCounts = 0;
        for (int num: nums) {
            frequency[num]++;
            if (frequency[num] == 1)
                uniqueCounts++;
        }

        int[] uniqueKeys = new int[uniqueCounts];
        int index = 0;
        for (int i = 0; i <= 100; ++i)
            if (frequency[i] > 0)
                uniqueKeys[index++] = i;

        long result = 0;

        for (int i = 0; i < uniqueKeys.length; ++i) {
            int x = uniqueKeys[i];
            int remainingSum = targetSum - x;
            int j = i, k = uniqueKeys.length - 1;
            while (j <= k) {
                int y = uniqueKeys[j], z = uniqueKeys[k];
                if (y + z < remainingSum) {
                    j++;
                } else if (y + z > remainingSum) {
                    k--;
                } else {
                    if (i < j && j < k) {
                        result += frequency[x] * frequency[y] * frequency[z];
                    } else if (i == j && j < k) {
                        result += frequency[x] * (frequency[x] - 1) / 2 * frequency[z];
                    } else if (i < j && j == k) {
                        result += frequency[x] * frequency[y] * (frequency[y] - 1) / 2;
                    } else {
                        result += frequency[x] * (frequency[x] - 1) * (frequency[x] - 2) / 6;
                    }

                    result %= MODULO;
                    j++;
                    k--;
                }
            }
        }

        return (int) result;
    }
}