Description
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 <= 10001 <= nums2.length <= 1051 <= nums1[i] <= 1091 <= nums2[i] <= 1050 <= index < nums2.length1 <= val <= 1051 <= tot <= 109- At most
1000 calls are made to add and count each.
Solutions
Solution 1: Hash Table
We note that the length of the array nums1 does not exceed {10}3, while the length of the array nums2 reaches {10}5. Therefore, if we directly enumerate all index pairs (i, j) and check whether nums1[i] + nums2[j] equals the specified value tot, it will exceed the time limit.
Can we only enumerate the shorter array nums1? The answer is yes. We use a hash table cnt to count the occurrences of each element in the array nums2, then enumerate each element x in the array nums1 and calculate the sum of cnt[tot - x].
When calling the add method, we need to first decrement the value corresponding to nums2[index] in cnt by 1, then add val to the value of nums2[index], and finally increment the value corresponding to nums2[index] in cnt by 1.
When calling the count method, we only need to traverse the array nums1 and calculate the sum of cnt[tot - x] for each element x.
The time complexity is O(n × q), and the space complexity is O(m). Here, n and m are the lengths of the arrays nums1 and nums2, respectively, and q is the number of times the count method is called.
PythonJavaC++GoTypeScriptRustJavaScriptC#
class FindSumPairs:
def __init__(self, nums1: List[int], nums2: List[int]):
self.cnt = Counter(nums2)
self.nums1 = nums1
self.nums2 = nums2
def add(self, index: int, val: int) -> None:
self.cnt[self.nums2[index]] -= 1
self.nums2[index] += val
self.cnt[self.nums2[index]] += 1
def count(self, tot: int) -> int:
return sum(self.cnt[tot - x] for x in self.nums1)
# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index,val)
# param_2 = obj.count(tot)(code-box)
class FindSumPairs {
private int[] nums1;
private int[] nums2;
private Map<Integer, Integer> cnt = new HashMap<>();
public FindSumPairs(int[] nums1, int[] nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
for (int x : nums2) {
cnt.merge(x, 1, Integer::sum);
}
}
public void add(int index, int val) {
cnt.merge(nums2[index], -1, Integer::sum);
nums2[index] += val;
cnt.merge(nums2[index], 1, Integer::sum);
}
public int count(int tot) {
int ans = 0;
for (int x : nums1) {
ans += cnt.getOrDefault(tot - x, 0);
}
return ans;
}
}
/**
* Your FindSumPairs object will be instantiated and called as such:
* FindSumPairs obj = new FindSumPairs(nums1, nums2);
* obj.add(index,val);
* int param_2 = obj.count(tot);
*/(code-box)
class FindSumPairs {
public:
FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
this->nums1 = nums1;
this->nums2 = nums2;
for (int x : nums2) {
++cnt[x];
}
}
void add(int index, int val) {
--cnt[nums2[index]];
nums2[index] += val;
++cnt[nums2[index]];
}
int count(int tot) {
int ans = 0;
for (int x : nums1) {
ans += cnt[tot - x];
}
return ans;
}
private:
vector<int> nums1;
vector<int> nums2;
unordered_map<int, int> cnt;
};
/**
* Your FindSumPairs object will be instantiated and called as such:
* FindSumPairs* obj = new FindSumPairs(nums1, nums2);
* obj->add(index,val);
* int param_2 = obj->count(tot);
*/(code-box)
type FindSumPairs struct {
nums1 []int
nums2 []int
cnt map[int]int
}
func Constructor(nums1 []int, nums2 []int) FindSumPairs {
cnt := map[int]int{}
for _, x := range nums2 {
cnt[x]++
}
return FindSumPairs{nums1, nums2, cnt}
}
func (this *FindSumPairs) Add(index int, val int) {
this.cnt[this.nums2[index]]--
this.nums2[index] += val
this.cnt[this.nums2[index]]++
}
func (this *FindSumPairs) Count(tot int) (ans int) {
for _, x := range this.nums1 {
ans += this.cnt[tot-x]
}
return
}
/**
* Your FindSumPairs object will be instantiated and called as such:
* obj := Constructor(nums1, nums2);
* obj.Add(index,val);
* param_2 := obj.Count(tot);
*/(code-box)
class FindSumPairs {
private nums1: number[];
private nums2: number[];
private cnt: Map<number, number>;
constructor(nums1: number[], nums2: number[]) {
this.nums1 = nums1;
this.nums2 = nums2;
this.cnt = new Map();
for (const x of nums2) {
this.cnt.set(x, (this.cnt.get(x) || 0) + 1);
}
}
add(index: number, val: number): void {
const old = this.nums2[index];
this.cnt.set(old, this.cnt.get(old)! - 1);
this.nums2[index] += val;
const now = this.nums2[index];
this.cnt.set(now, (this.cnt.get(now) || 0) + 1);
}
count(tot: number): number {
return this.nums1.reduce((acc, x) => acc + (this.cnt.get(tot - x) || 0), 0);
}
}
/**
* Your FindSumPairs object will be instantiated and called as such:
* var obj = new FindSumPairs(nums1, nums2)
* obj.add(index,val)
* var param_2 = obj.count(tot)
*/(code-box)
use std::collections::HashMap;
struct FindSumPairs {
nums1: Vec<i32>,
nums2: Vec<i32>,
cnt: HashMap<i32, i32>,
}
impl FindSumPairs {
fn new(nums1: Vec<i32>, nums2: Vec<i32>) -> Self {
let mut cnt = HashMap::new();
for &x in &nums2 {
*cnt.entry(x).or_insert(0) += 1;
}
Self { nums1, nums2, cnt }
}
fn add(&mut self, index: i32, val: i32) {
let i = index as usize;
let old_val = self.nums2[i];
*self.cnt.entry(old_val).or_insert(0) -= 1;
if self.cnt[&old_val] == 0 {
self.cnt.remove(&old_val);
}
self.nums2[i] += val;
let new_val = self.nums2[i];
*self.cnt.entry(new_val).or_insert(0) += 1;
}
fn count(&self, tot: i32) -> i32 {
let mut ans = 0;
for &x in &self.nums1 {
let target = tot - x;
if let Some(&c) = self.cnt.get(&target) {
ans += c;
}
}
ans
}
}(code-box)
/**
* @param {number[]} nums1
* @param {number[]} nums2
*/
var FindSumPairs = function (nums1, nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
this.cnt = new Map();
for (const x of nums2) {
this.cnt.set(x, (this.cnt.get(x) || 0) + 1);
}
};
/**
* @param {number} index
* @param {number} val
* @return {void}
*/
FindSumPairs.prototype.add = function (index, val) {
const old = this.nums2[index];
this.cnt.set(old, this.cnt.get(old) - 1);
this.nums2[index] += val;
const now = this.nums2[index];
this.cnt.set(now, (this.cnt.get(now) || 0) + 1);
};
/**
* @param {number} tot
* @return {number}
*/
FindSumPairs.prototype.count = function (tot) {
return this.nums1.reduce((acc, x) => acc + (this.cnt.get(tot - x) || 0), 0);
};
/**
* Your FindSumPairs object will be instantiated and called as such:
* var obj = new FindSumPairs(nums1, nums2)
* obj.add(index,val)
* var param_2 = obj.count(tot)
*/(code-box)
public class FindSumPairs {
private int[] nums1;
private int[] nums2;
private Dictionary<int, int> cnt = new Dictionary<int, int>();
public FindSumPairs(int[] nums1, int[] nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
foreach (int x in nums2) {
if (cnt.ContainsKey(x)) {
cnt[x]++;
} else {
cnt[x] = 1;
}
}
}
public void Add(int index, int val) {
int oldVal = nums2[index];
if (cnt.TryGetValue(oldVal, out int oldCount)) {
if (oldCount == 1) {
cnt.Remove(oldVal);
} else {
cnt[oldVal] = oldCount - 1;
}
}
nums2[index] += val;
int newVal = nums2[index];
if (cnt.TryGetValue(newVal, out int newCount)) {
cnt[newVal] = newCount + 1;
} else {
cnt[newVal] = 1;
}
}
public int Count(int tot) {
int ans = 0;
foreach (int x in nums1) {
int target = tot - x;
if (cnt.TryGetValue(target, out int count)) {
ans += count;
}
}
return ans;
}
}
/**
* Your FindSumPairs object will be instantiated and called as such:
* FindSumPairs obj = new FindSumPairs(nums1, nums2);
* obj.Add(index,val);
* int param_2 = obj.Count(tot);
*/(code-box)
