923. 3Sum With Multiplicity

Description

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.

Constraints

• 3 <= arr.length <= 3000

• 0 <= arr[i] <= 100

• 0 <= target <= 300

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

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.

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

// Time Limit Exceeded

class Solution {
    public int threeSumMulti(int[] arr, int target) {
        int n = arr.length;
        long result = 0;
        Arrays.sort(arr);
        
        for(int i = 0; i < n-2; i++) {
            int t = target - arr[i];
            int left = i + 1, right = n-1;
            while(left < right) {
                int sum = arr[left] + arr[right];
                if(sum < t) {
                    left++;
                } else if(sum  > t) {
                    right--;
                } else {
                    int tempRight = right;
                    while(left < right && arr[left] + arr[right] == t) {
                        result++;
                        right--;
                    }
                    right = tempRight;
                    left++;
                }
            }
        }
        return (int) (result%1000000007);
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private final int MOD = 1000000007;
    
    public int threeSumMulti(int[] arr, int target) {
        int result = 0;
        Map<Integer, Integer> map = new HashMap();
        
        for(int i = 0; i < arr.length; i++) {
            result = (result + map.getOrDefault(target-arr[i], 0)) % MOD;
            
            for(int j = 0; j < i; j++) {
                map.put(arr[i]+arr[j], map.getOrDefault(arr[i]+arr[j], 0) + 1);
            }
        }

        return result;
    }
}

Solution 3

/**
 * Time complexity : O(N^2), where N is the length of array.
 * Space complexity : O(N)
 */

class Solution {
    private final int MOD = 1000000007;
    
    public int threeSumMulti(int[] arr, int target) {
        int result = 0;
        for(int i = 0; i < arr.length; i++) {
            int[] count = new int[101];
            for(int j = i+1; j < arr.length; j++) {
                int k = target - arr[i] - arr[j];
                if(k >= 0 && k <= 100 && count[k] > 0) {
                    result = (result + count[k]) % MOD;
                }
                count[arr[j]]++;
            }
        }
        return result;
    }
}

Solution 4

/**
 * Time complexity : O(N + 100*100) => O(N)
 * Space complexity : O(100) => O(1)
 */
 
 class Solution {
    private final int MOD = 1_000_000_007;
    
    public int threeSumMulti(int[] arr, int target) {
        long result = 0;
        long[] count = new long[101];
        
        for(int val: arr) {
            count[val]++;
        }
        
        for(int i = 0; i <= 100; i++) {
            for(int j = i; j <= 100; j++) {
                int k = target - i - j;
                if(k < 0 || k > 100) {
                    continue;
                }
                if(i == j && j == k) {
                    result += (count[i] * (count[i]-1) * (count[i]-2) / 6);
                } else if(i == j && j != k) {
                    result += ((count[i] * (count[i]-1)/2) * count[k]);
                } else if(i < j && j < k) {
                    result += (count[i] * count[j] * count[k]);
                }
            }
        }
        return (int) (result%MOD);
    }
}

Follow up