DevExCode

Sign in to devexcode.com with google.com

To continue, google.com will share your name, email address, and profile picture with this site. See this site's privacy policy.

923. 3Sum With Multiplicity

ArrayHash TableTwo PointersSortingCounting

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:

  1. Initialize a hashmap to store the count of elements encountered.
  2. Initialize a variable count to store the final result.
  3. 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.
  4. 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.

:

View Leetcode Problem
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;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question