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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Finding Pairs With a Certain Sum

Difficulty: Medium

Problem Description

You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:

  1. Add a positive integer to an element of a given index in the array nums2.
  2. Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value.

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.

Key Insights

  • Use a hash map to keep track of the frequency of elements in nums2 to efficiently count pairs.
  • When adding a value to an element in nums2, update the frequency map.
  • For counting pairs, iterate through nums1 and check for the required value in the frequency map.

Space and Time Complexity

Time Complexity:

  • add: O(1) for updating the value and the map.
  • count: O(n) where n is the length of nums1, as we need to check each element.

Space Complexity: O(m) where m is the maximum value in nums2 for storing the frequency.

Solution

To solve the problem, we can use a hash map (dictionary) to store the frequency of elements in nums2. When the add method is called, we simply update the value at the specified index and adjust the frequency in the map. For the count method, we iterate through each element in nums1, calculate the complement needed to reach the target sum, and check if this complement exists in the frequency map. The total count of pairs is the sum of the frequencies of these complements.

Code Solutions

class FindSumPairs:
    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums1 = nums1
        self.nums2 = nums2
        self.freq = Counter(nums2)  # Frequency map for nums2

    def add(self, index: int, val: int) -> None:
        # Update nums2 and frequency map
        self.freq[self.nums2[index]] -= 1  # Decrease count of old value
        self.nums2[index] += val  # Update the value
        self.freq[self.nums2[index]] += 1  # Increase count of new value

    def count(self, tot: int) -> int:
        count = 0
        for num in self.nums1:
            complement = tot - num
            count += self.freq[complement]  # Get count of pairs
        return count
← Back to All Questions