Finding Pairs With a Certain Sum

Problem

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 (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.

Examples

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

Solution

Method 1 – Hash Map Frequency Tracking

Intuition

To efficiently support both add and count operations, we use a hash map to track the frequency of each value in nums2. This allows us to quickly update counts when nums2 changes and to efficiently count valid pairs for any given sum.

Approach

1. Store nums1 as-is (since it is small, up to 1000 elements).
2. For nums2, maintain a frequency map (hash map) of value to count.
3. For add(index, val):
   • Decrement the count of the old value at nums2[index] in the frequency map.
   • Update nums2[index] by adding val.
   • Increment the count of the new value in the frequency map.
4. For count(tot):
   • For each value x in nums1, compute y = tot - x.
   • Add the frequency of y in nums2 to the answer.

Code

C++

class FindSumPairs {
    vector<int> a, b;
    unordered_map<int, int> freq;
public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) : a(nums1), b(nums2) {
        for (int x : b) freq[x]++;
    }
    void add(int idx, int val) {
        freq[b[idx]]--;
        b[idx] += val;
        freq[b[idx]]++;
    }
    int count(int tot) {
        int ans = 0;
        for (int x : a) {
            ans += freq[tot - x];
        }
        return ans;
    }
};

Go

// No class needed in Go, use struct

type FindSumPairs struct {
    a []int
    b []int
    freq map[int]int
}

func Constructor(nums1 []int, nums2 []int) FindSumPairs {
    freq := make(map[int]int)
    for _, x := range nums2 {
        freq[x]++
    }
    return FindSumPairs{a: nums1, b: nums2, freq: freq}
}

func (f *FindSumPairs) Add(idx int, val int) {
    f.freq[f.b[idx]]--
    f.b[idx] += val
    f.freq[f.b[idx]]++
}

func (f *FindSumPairs) Count(tot int) int {
    ans := 0
    for _, x := range f.a {
        ans += f.freq[tot-x]
    }
    return ans
}

Java

class FindSumPairs {
    int[] a, b;
    Map<Integer, Integer> freq;
    public FindSumPairs(int[] nums1, int[] nums2) {
        a = nums1;
        b = nums2;
        freq = new HashMap<>();
        for (int x : b) freq.put(x, freq.getOrDefault(x, 0) + 1);
    }
    public void add(int idx, int val) {
        freq.put(b[idx], freq.get(b[idx]) - 1);
        b[idx] += val;
        freq.put(b[idx], freq.getOrDefault(b[idx], 0) + 1);
    }
    public int count(int tot) {
        int ans = 0;
        for (int x : a) ans += freq.getOrDefault(tot - x, 0);
        return ans;
    }
}

Kotlin

class FindSumPairs(nums1: IntArray, nums2: IntArray) {
    private val a = nums1
    private val b = nums2
    private val freq = mutableMapOf<Int, Int>()
    init {
        for (x in b) freq[x] = freq.getOrDefault(x, 0) + 1
    }
    fun add(idx: Int, v: Int) {
        freq[b[idx]] = freq[b[idx]]!! - 1
        b[idx] += v
        freq[b[idx]] = freq.getOrDefault(b[idx], 0) + 1
    }
    fun count(tot: Int): Int {
        var ans = 0
        for (x in a) ans += freq.getOrDefault(tot - x, 0)
        return ans
    }
}

Python

class FindSumPairs:
    def __init__(self, nums1: list[int], nums2: list[int]):
        self.a = nums1
        self.b = nums2
        self.freq: dict[int, int] = {}
        for x in self.b:
            self.freq[x] = self.freq.get(x, 0) + 1
    def add(self, idx: int, val: int) -> None:
        self.freq[self.b[idx]] -= 1
        self.b[idx] += val
        self.freq[self.b[idx]] = self.freq.get(self.b[idx], 0) + 1
    def count(self, tot: int) -> int:
        ans = 0
        for x in self.a:
            ans += self.freq.get(tot - x, 0)
        return ans

Rust

use std::collections::HashMap;

struct FindSumPairs {
    a: Vec<i32>,
    b: Vec<i32>,
    freq: HashMap<i32, i32>,
}

impl FindSumPairs {
    fn new(nums1: Vec<i32>, nums2: Vec<i32>) -> Self {
        let mut freq = HashMap::new();
        for &x in &nums2 {
            *freq.entry(x).or_insert(0) += 1;
        }
        Self { a: nums1, b: nums2, freq }
    }
    fn add(&mut self, idx: usize, val: i32) {
        *self.freq.get_mut(&self.b[idx]).unwrap() -= 1;
        self.b[idx] += val;
        *self.freq.entry(self.b[idx]).or_insert(0) += 1;
    }
    fn count(&self, tot: i32) -> i32 {
        let mut ans = 0;
        for &x in &self.a {
            ans += *self.freq.get(&(tot - x)).unwrap_or(&0);
        }
        ans
    }
}

TypeScript

class FindSumPairs {
    private a: number[];
    private b: number[];
    private freq: Map<number, number>;
    constructor(nums1: number[], nums2: number[]) {
        this.a = nums1;
        this.b = nums2;
        this.freq = new Map();
        for (const x of this.b) {
            this.freq.set(x, (this.freq.get(x) || 0) + 1);
        }
    }
    add(idx: number, val: number): void {
        this.freq.set(this.b[idx], this.freq.get(this.b[idx])! - 1);
        this.b[idx] += val;
        this.freq.set(this.b[idx], (this.freq.get(this.b[idx]) || 0) + 1);
    }
    count(tot: number): number {
        let ans = 0;
        for (const x of this.a) {
            ans += this.freq.get(tot - x) || 0;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n1 + q * n1) where n1 = len(nums1), q = number of count queries. Each count is O(n1), add is O(1).
• 🧺 Space complexity: O(n2) for the frequency map of nums2 values.