1865. Finding Pairs With a Certain Sum LeetCode Solution

In this guide, you will get 1865. Finding Pairs With a Certain Sum LeetCode Solution with the best time and space complexity. The solution to Finding Pairs With a Certain Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Finding Pairs With a Certain Sum solution in C++
Finding Pairs With a Certain Sum solution in Java
Finding Pairs With a Certain Sum solution in Python
Additional Resources

1865. Finding Pairs With a Certain Sum LeetCode Solution image

Problem Statement of Finding Pairs With a Certain Sum

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 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 <= 1000
1 <= nums2.length <= 105
1 <= nums1[i] <= 109
1 <= nums2[i] <= 105
0 <= index < nums2.length
1 <= val <= 105
1 <= tot <= 109
At most 1000 calls are made to add and count each.

Complexity Analysis

Time Complexity: O(|\texttt{nums1}|)
Space Complexity: O(|\texttt{nums2}|)

1865. Finding Pairs With a Certain Sum LeetCode Solution in C++

class FindSumPairs {
 public:
  FindSumPairs(vector<int>& nums1, vector<int>& nums2)
      : nums1(nums1), nums2(nums2) {
    for (const int num : nums2)
      ++count2[num];
  }

  void add(int index, int val) {
    --count2[nums2[index]];
    nums2[index] += val;
    ++count2[nums2[index]];
  }

  int count(int tot) {
    int ans = 0;
    for (const int num : nums1) {
      const int target = tot - num;
      if (const auto it = count2.find(target); it != count2.cend())
        ans += it->second;
    }
    return ans;
  }

 private:
  vector<int> nums1;
  vector<int> nums2;
  unordered_map<int, int> count2;
};
/* code provided by PROGIEZ */

1865. Finding Pairs With a Certain Sum LeetCode Solution in Java

class FindSumPairs {
  public FindSumPairs(int[] nums1, int[] nums2) {
    this.nums1 = nums1;
    this.nums2 = nums2;
    for (final int num : nums2)
      count2.merge(num, 1, Integer::sum);
  }

  public void add(int index, int val) {
    count2.merge(nums2[index], -1, Integer::sum);
    nums2[index] += val;
    count2.merge(nums2[index], 1, Integer::sum);
  }

  public int count(int tot) {
    int ans = 0;
    for (final int num : nums1)
      ans += count2.getOrDefault(tot - num, 0);
    return ans;
  }

  private int[] nums1;
  private int[] nums2;
  private Map<Integer, Integer> count2 = new HashMap<>();
}
// code provided by PROGIEZ

1865. Finding Pairs With a Certain Sum LeetCode Solution in Python

class FindSumPairs:
  def __init__(self, nums1: list[int], nums2: list[int]):
    self.nums1 = nums1
    self.nums2 = nums2
    self.count2 = collections.Counter(nums2)

  def add(self, index: int, val: int) -> None:
    self.count2[self.nums2[index]] -= 1
    self.nums2[index] += val
    self.count2[self.nums2[index]] += 1

  def count(self, tot: int) -> int:
    ans = 0
    for num in self.nums1:
      ans += self.count2[tot - num]
    return ans
 # code by PROGIEZ