We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Finding Pairs With a Certain Sum

Number: 1995

Difficulty: Medium

Paid? No

Companies: Databricks, Quora

Problem Description

We are given two integer arrays, nums1 and nums2. We need to design a data structure that supports two operations: (1) add a positive integer to an element at a specified index in nums2, and (2) count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given total.

Key Insights

  • Precompute and maintain a frequency map (hash table) for the elements in nums2.
  • Since nums1 is relatively small (at most 1000 elements), iterating through it for each count query is efficient.
  • For each add query, update the frequency map in O(1) time by decrementing the frequency of the old value and incrementing that of the new value.
  • For each count query, iterate through nums1 and use the frequency map to quickly find how many complementary values exist in nums2.

Space and Time Complexity

Time Complexity:

  • add: O(1)
  • count: O(n1) where n1 is the length of nums1

Space Complexity: O(n2) due to the frequency map for nums2

Solution

We use a hash table to maintain the frequency of each element in nums2. During initialization, we build this mapping. In the add method, we update the frequency map by first reducing the count for the current value at the given index, then updating the element, and finally incrementing the frequency for the new value. The count method iterates through nums1 and, for each element, calculates the needed complement such that the sum equals tot. The frequency map is then used to look up how many times this complement appears in nums2. This approach ensures that both operations are efficient given the problem constraints.

Code Solutions

class FindSumPairs:
    def __init__(self, nums1, nums2):
        # Store the initial arrays
        self.nums1 = nums1
        self.nums2 = nums2
        # Build a frequency map for nums2
        self.freqNums2 = {}
        for num in nums2:
            self.freqNums2[num] = self.freqNums2.get(num, 0) + 1
        
    def add(self, index, val):
        # Get the old value from nums2
        old_val = self.nums2[index]
        # Decrement the frequency for the old value
        self.freqNums2[old_val] -= 1
        # Update the nums2 element by adding the value
        self.nums2[index] += val
        new_val = self.nums2[index]
        # Increment the frequency for the new value
        self.freqNums2[new_val] = self.freqNums2.get(new_val, 0) + 1
        
    def count(self, tot):
        total_pairs = 0
        # For each number in nums1, find the complement needed in nums2
        for num in self.nums1:
            complement = tot - num
            total_pairs += self.freqNums2.get(complement, 0)
        return total_pairs
← Back to All Questions