Finding Pairs With a Certain Sum
Problem
Design FindSumPairs(nums1, nums2) supporting two operations. add(index, val) does nums2[index] += val. count(tot) returns the number of pairs (i, j) with nums1[i] + nums2[j] == tot. Since nums1 is short but nums2 is long, keep a frequency map of nums2's values: then count sums freq[tot − nums1[i]] over the small array, and add just patches two map entries.
nums1 = [1,1,2,2,2,3], nums2 = [1,4,5,2,5,4]; count(7)8class FindSumPairs:
def __init__(self, nums1, nums2):
self.nums1 = nums1
self.nums2 = nums2
self.freq = Counter(nums2) # value -> how many times it appears
def add(self, index, val):
old = self.nums2[index]
self.freq[old] -= 1 # remove the old value
self.nums2[index] += val # nums2[index] += val
self.freq[self.nums2[index]] += 1 # add the new value
def count(self, tot):
res = 0
for a in self.nums1: # nums1 is short, iterate it
res += self.freq[tot - a] # how many nums2[j] equal tot - a
return resclass FindSumPairs {
constructor(nums1, nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
this.freq = new Map(); // value -> count
for (const v of nums2) this.freq.set(v, (this.freq.get(v) || 0) + 1);
}
add(index, val) {
const old = this.nums2[index];
this.freq.set(old, this.freq.get(old) - 1); // remove old value
this.nums2[index] += val; // nums2[index] += val
const nv = this.nums2[index];
this.freq.set(nv, (this.freq.get(nv) || 0) + 1); // add new value
}
count(tot) {
let res = 0;
for (const a of this.nums1) // iterate short nums1
res += this.freq.get(tot - a) || 0; // count of tot - a
return res;
}
}class FindSumPairs {
int[] nums1, nums2;
Map<Integer, Integer> freq = new HashMap<>(); // value -> count
public FindSumPairs(int[] nums1, int[] nums2) {
this.nums1 = nums1; this.nums2 = nums2;
for (int v : nums2) freq.merge(v, 1, Integer::sum);
}
public void add(int index, int val) {
int old = nums2[index];
freq.merge(old, -1, Integer::sum); // remove old value
nums2[index] += val; // nums2[index] += val
freq.merge(nums2[index], 1, Integer::sum); // add new value
}
public int count(int tot) {
int res = 0;
for (int a : nums1) // iterate short nums1
res += freq.getOrDefault(tot - a, 0); // count of tot - a
return res;
}
}class FindSumPairs {
vector<int> nums1, nums2;
unordered_map<int,int> freq; // value -> count
public:
FindSumPairs(vector<int>& a, vector<int>& b) : nums1(a), nums2(b) {
for (int v : nums2) freq[v]++;
}
void add(int index, int val) {
int old = nums2[index];
freq[old]--; // remove old value
nums2[index] += val; // nums2[index] += val
freq[nums2[index]]++; // add new value
}
int count(int tot) {
int res = 0;
for (int a : nums1) // iterate short nums1
res += freq.count(tot - a) ? freq[tot - a] : 0; // count of tot - a
return res;
}
};Explanation
The brute-force answer to count(tot) is to try every pair (i, j) — that is O(n1 · n2) per query, and with n2 up to 105 and up to 1000 queries it is far too slow.
The key observation (the hint) is that nums1 is tiny (≤ 1000) while nums2 is huge. So we precompute a frequency map freq that says, for each distinct value v, how many indices j have nums2[j] == v.
Now count(tot) only loops over the short nums1. For each value a = nums1[i], the partner we need on the nums2 side is exactly tot − a, and freq[tot − a] tells us how many such partners exist. Summing those counts gives the total number of valid pairs in O(n1) time.
add(index, val) changes a single element of nums2. We keep the map consistent by decrementing the count of the old value, applying nums2[index] += val, then incrementing the count of the new value — an O(1) patch. We never rebuild the map.
Worked example: nums2 = [1,4,5,2,5,4] gives freq = {1:1, 2:1, 4:2, 5:2}. For count(7) we walk nums1 = [1,1,2,2,2,3]: the three 2s each add freq[5] = 2, the 3 adds freq[4] = 2, the 1s add freq[6] = 0. Total 2+2+2+2 = 8.