You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:
nums2.(i, j) such that nums1[i] + nums2[j] equals a given value (0 <= i < nums1.length and 0 <= j < nums2.length).Implement the FindSumPairs class:
FindSumPairs(int[] nums1, int[] nums2) Initializes the FindSumPairs object with two integer arrays nums1 and nums2.void add(int index, int val) Adds val to nums2[index], i.e., apply nums2[index] += val.int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.
Example 1:
Input ["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"] [[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]] Output [null, 8, null, 2, 1, null, null, 11] Explanation FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]); findSumPairs.count(7); // return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4 findSumPairs.add(3, 2); // now nums2 = [1,4,5,4,5,4] findSumPairs.count(8); // return 2; pairs (5,2), (5,4) make 3 + 5 findSumPairs.count(4); // return 1; pair (5,0) makes 3 + 1 findSumPairs.add(0, 1); // now nums2 = [2,4,5,4,5,4] findSumPairs.add(1, 1); // now nums2 = [2,5,5,4,5,4] findSumPairs.count(7); // return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4
Constraints:
1 <= nums1.length <= 10001 <= nums2.length <= 1051 <= nums1[i] <= 1091 <= nums2[i] <= 1050 <= index < nums2.length1 <= val <= 1051 <= tot <= 1091000 calls are made to add and count each.Problem Overview: You maintain two integer arrays nums1 and nums2. The data structure must support two operations: add a value to an index in nums2, and count how many pairs (i, j) satisfy nums1[i] + nums2[j] == total. The challenge is answering repeated count queries efficiently while updates modify nums2.
Approach 1: HashMap Frequency Count (O(n) count, O(1) add)
Store a frequency map for values in nums2. During initialization, iterate through nums2 and record how many times each value appears using a hash map. For a count(total) query, iterate through every element x in nums1 and compute the complement total - x. A single hash lookup gives how many elements in nums2 complete the pair. For the add(index, val) operation, decrease the frequency of the old value in nums2[index], update the array, then increase the frequency of the new value. Each update takes constant time because it only adjusts two hash entries. The count query runs in O(n1) time with O(n2) space for the map. This approach relies on fast lookups from a hash table and works well because nums1 never changes.
Approach 2: Two-Pointer Technique (Alternative) (O(n log n) preprocessing, O(n) query)
If both arrays are kept sorted, you can count pairs using a classic two-pointer sweep. Start one pointer at the beginning of nums1 and another at the end of nums2. Move pointers based on whether the current sum is smaller or larger than the target. This finds all valid pairs in linear time after sorting. The downside appears when the add operation changes values in nums2. Maintaining sorted order requires reinserting the updated value or re-sorting, which can cost O(n) or O(n log n). Space complexity stays O(1) beyond the arrays. This method demonstrates how pair-sum problems can be solved efficiently with sorted data using techniques common in array and pointer manipulation problems.
Recommended for interviews: The HashMap frequency solution is the expected answer. It cleanly separates responsibilities: nums1 is scanned during queries, while nums2 updates only adjust counts. Interviewers want to see recognition that repeated pair queries benefit from a precomputed frequency structure. The two-pointer approach helps explain the pair-sum intuition, but the hash-based design demonstrates stronger understanding of data structure design and dynamic updates.
In this approach, we utilize a hashmap (or dictionary) to store the frequency count of numbers in nums2. When we need to count pairs, for each number in nums1, we determine the complementary number needed from nums2 to reach the total. Using our hashmap, we can quickly get the count for how many such complements exist. Updates to nums2 only require adjusting counts in the hashmap, maintaining efficiency.
We use a defaultdict from the collections module to keep track of the frequencies of nums2 elements. The add method updates the frequencies accordingly. The count method calculates the number of valid pairs by iterating through nums1 while checking the frequency of the needed complementary value from nums2 using the hashmap.
Time Complexity: O(n1 + q), where n1 is the length of nums1 and q is the number of queries. Each add operation takes O(1). Space Complexity: O(n2), where n2 is the length of nums2 due to storing frequencies.
Here we consider a two-pointer technique by treating nums1 and nums2 as sorted arrays. Though this approach may require sorting initially, it can be beneficial when large datasets and specific queries are considered, but given nums1 and nums2 may not be sorted initially, this approach is less optimal without initial preprocessing.
With the two-pointer strategy, we use sorted lists to find sums that reach the desired total. The algorithm walks through the lists, adjusting pointers based on sum comparisons.
Time Complexity: O(n2 log n2 + m + q(n1 + n2)) where m is the overall number of elements changed or checked. Space Complexity: O(1) besides input arrays.
We note that the length of the array nums1 does not exceed {10}^3, while the length of the array nums2 reaches {10}^5. Therefore, if we directly enumerate all index pairs (i, j) and check whether nums1[i] + nums2[j] equals the specified value tot, it will exceed the time limit.
Can we only enumerate the shorter array nums1? The answer is yes. We use a hash table cnt to count the occurrences of each element in the array nums2, then enumerate each element x in the array nums1 and calculate the sum of cnt[tot - x].
When calling the add method, we need to first decrement the value corresponding to nums2[index] in cnt by 1, then add val to the value of nums2[index], and finally increment the value corresponding to nums2[index] in cnt by 1.
When calling the count method, we only need to traverse the array nums1 and calculate the sum of cnt[tot - x] for each element x.
The time complexity is O(n times q), and the space complexity is O(m). Here, n and m are the lengths of the arrays nums1 and nums2, respectively, and q is the number of times the count method is called.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| HashMap Frequency Count | Time Complexity: O(n1 + q), where n1 is the length of nums1 and q is the number of queries. Each add operation takes O(1). Space Complexity: O(n2), where n2 is the length of nums2 due to storing frequencies. |
| Two-Pointer Technique (Alternative) | Time Complexity: O(n2 log n2 + m + q(n1 + n2)) where m is the overall number of elements changed or checked. Space Complexity: O(1) besides input arrays. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Frequency Count | Add: O(1), Count: O(n1) | O(n2) | Best general solution when nums2 is frequently updated and many count queries are executed |
| Two-Pointer Technique (Sorted Arrays) | Query: O(n), Updates: O(n) or O(n log n) | O(1) | Works when arrays remain sorted or updates are rare |
Finding Pairs With a Certain Sum | Simple Explanation | Leetcode 1865 | codestorywithMIK • codestorywithMIK • 7,135 views views
Watch 9 more video solutions →Practice Finding Pairs With a Certain Sum with our built-in code editor and test cases.
Practice on FleetCode