Finding Pairs With a Certain Sum
Medium
You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:
- Add a positive integer to an element of a given index in the array
nums2. - Count the number of pairs
(i, j)such thatnums1[i] + nums2[j]equals a given value (0 <= i < nums1.lengthand0 <= j < nums2.length).
Implement the FindSumPairs class:
FindSumPairs(int[] nums1, int[] nums2)Initializes theFindSumPairsobject with two integer arraysnums1andnums2.void add(int index, int val)Addsvaltonums2[index], i.e., applynums2[index] += val.int count(int tot)Returns the number of pairs(i, j)such thatnums1[i] + nums2[j] == tot.
Example:
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
What data structures and algorithms would you use to optimize the add and count methods for large input arrays? Consider the trade-offs between time and space complexity.
Solution
Find Sum Pairs Solution
This problem requires us to implement a data structure that efficiently handles two types of queries: adding a value to an element in an array and counting pairs with a given sum across two arrays. Let's explore different approaches to solve this.
1. Naive (Brute Force) Solution
Approach:
The simplest approach is to directly implement the given operations. The add operation updates the array element directly. The count operation iterates through all possible pairs of elements from nums1 and nums2 and checks if their sum equals the target value.
Code:
class FindSumPairs:
def __init__(self, nums1: List[int], nums2: List[int]):
self.nums1 = nums1
self.nums2 = nums2
def add(self, index: int, val: int) -> None:
self.nums2[index] += val
def count(self, tot: int) -> int:
count = 0
for i in range(len(self.nums1)):
for j in range(len(self.nums2)):
if self.nums1[i] + self.nums2[j] == tot:
count += 1
return count
Time Complexity:
__init__: O(1)add: O(1)count: O(N * M), where N is the length ofnums1and M is the length ofnums2.
Space Complexity:
- O(1) (excluding the space for storing the input arrays)
Edge Cases:
- Empty arrays.
- Very large arrays, making the
countoperation slow.
2. Optimal Solution
Approach:
To optimize the count operation, we can use a hash map (dictionary) to store the frequency of each number in nums2. This allows us to quickly determine how many elements in nums2 can form the target sum with elements in nums1.
Code:
from collections import Counter
class FindSumPairs:
def __init__(self, nums1: List[int], nums2: List[int]):
self.nums1 = nums1
self.nums2 = nums2
self.count_nums2 = Counter(nums2)
def add(self, index: int, val: int) -> None:
old_val = self.nums2[index]
self.count_nums2[old_val] -= 1
if self.count_nums2[old_val] == 0:
del self.count_nums2[old_val]
self.nums2[index] += val
self.count_nums2[self.nums2[index]] += 1
def count(self, tot: int) -> int:
count = 0
for num in self.nums1:
complement = tot - num
if complement in self.count_nums2:
count += self.count_nums2[complement]
return count
Time Complexity:
__init__: O(M), where M is the length ofnums2.add: O(1)count: O(N), where N is the length ofnums1.
Space Complexity:
- O(M), where M is the length of
nums2(for storing the frequency map).
Edge Cases:
- Empty arrays.
- Very large arrays, but the hash map makes the
countoperation significantly faster than the brute force approach.
Summary
The optimal solution uses a hash map to improve the time complexity of the count operation from O(N * M) to O(N), which is a significant improvement, especially for large arrays. The space complexity increases to O(M) to store the frequency map.
