LeetCode 923: 3Sum With Multiplicity Solution

Master LeetCode problem 923 (3Sum With Multiplicity), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

923. 3Sum With Multiplicity

Medium

Array Hash Table Two Pointers Sorting Counting

Problem Explanation

Explanation:

To solve this problem, we can use a combination of hashing and counting techniques. We iterate over all possible pairs of elements in the array and calculate the third element needed to reach the target sum. We use a hashmap to store the count of elements encountered so far. For each pair, we calculate the third element required and check if it exists in the hashmap. If it does, we increment the count by the product of counts of the two elements in the pair and the count of the required third element. Finally, we update the count of the current element in the hashmap.

Algorithm:

Initialize a hashmap to store the count of elements encountered.
Initialize a variable count to store the final result.
Iterate over all pairs of elements (i, j) in the array:
- Calculate the required third element k = target - arr[i] - arr[j].
- If k exists in the hashmap, increment count by count[k] * count[arr[i]] * count[arr[j]].
- Update the count of the current element arr[j] in the hashmap.
Return the final result count modulo 10^9 + 7.

Time Complexity: O(N^2), where N is the number of elements in the input array. Space Complexity: O(N) for the hashmap.

Solution Code

class Solution {
    public int threeSumMulti(int[] arr, int target) {
        long count = 0;
        int mod = 1000000007;
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int k = target - arr[i] - arr[j];
                if (map.containsKey(k)) {
                    count = (count + map.get(k)) % mod;
                }
                map.put(arr[j], (map.getOrDefault(arr[j], 0) + 1) % mod);
            }
            for (int j = 0; j < i; j++) {
                map.put(arr[j], (map.getOrDefault(arr[j], 0) + 1) % mod);
            }
        }
        
        return (int) count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 923 (3Sum With Multiplicity)?

This page provides optimized solutions for LeetCode problem 923 (3Sum With Multiplicity) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 923 (3Sum With Multiplicity)?

The time complexity for LeetCode 923 (3Sum With Multiplicity) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 923 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 923 in Java, C++, or Python.

Back to LeetCode Solutions