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 <= 30000 <= arr[i] <= 1000 <= target <= 300This approach involves first sorting the array and then using a two-pointer method to efficiently count the valid tuples. After fixing the first element of the triplet, use two pointers to find complementary pairs that sum up to the required value.
The C solution begins by sorting the input array using Quick Sort. It then iterates over the array and for each element, uses the two-pointer technique to locate pairs that along with the current element add up to the target. Counts of repeated numbers are handled carefully to ensure all combinations are considered.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where n is the number of elements in the array.
Space Complexity: O(1) apart from the input data since the operation is done in-place.
In this approach, we utilize hashmaps/dictionaries to store the frequency of each number in the array. Then, iterate through unique pairs of numbers to check if the pair with any other number sums up to the target value. This approach makes use of combinatorial calculations without explicitly sorting the array.
This Python solution makes use of combinations evaluated through mathematical formulas counting indirect combinations by their frequency. It differentiates cases where numbers are equal or different and handles all scenarios precisely.
Java
Time Complexity: O(n^2), which comes from iterating over pairs and can be considered effectively O(n) for small arrays using fixed range.
Space Complexity: O(1), as the frequency dictionary can be considered a fixed size due to constraints.
| Approach | Complexity |
|---|---|
| Two Pointers Approach | Time Complexity: O(n^2), where n is the number of elements in the array. |
| HashMap Frequency Count | Time Complexity: O(n^2), which comes from iterating over pairs and can be considered effectively O(n) for small arrays using fixed range. |
3Sum - Leetcode 15 - Python • NeetCode • 980,205 views views
Watch 9 more video solutions →Practice 3Sum With Multiplicity with our built-in code editor and test cases.
Practice on FleetCode