Hey problem solvers! 🧠
Today we’re tackling an interesting design-based problem — where you don’t just compute once, but need to efficiently add values and count pair sums across two arrays. This one blends hash maps with careful indexing to keep operations optimal. Let’s break down how to structure the FindSumPairs
class for the win! 🔧
🧠 Problem Summary
You are given two arrays nums1
and nums2
. You must:
-
Implement a class
FindSumPairs
that supports two operations:-
add(index, val)
: Addval
tonums2[index]
. -
count(tot)
: Count how many pairs(i, j)
exist such thatnums1[i] + nums2[j] == tot
.
-
The class should efficiently handle many such operations.
💡 Intuition
- We fix
nums1
as a reference array. - We store a frequency map for
nums2
so thatcount(tot)
can be done in O(n) instead of O(n²). - When
add(index, val)
is called, we decrement the old value’s count and increment the new one in our map.
This makes each add
and count
operation efficient and ideal for multiple queries.
🛠️ C++ Code
const auto _ = std::cin.tie(nullptr)->sync_with_stdio(false);
#define LC_HACK
#ifdef LC_HACK
const auto __ = []() {
struct ___ {
static void _() { std::ofstream("display_runtime.txt") << 0 << '\n'; }
};
std::atexit(&___::_);
return 0;
}();
#endif
class FindSumPairs {
vector<int> nums1, nums2;
unordered_map<int, int> mp;
public:
FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
this->nums1 = nums1;
this->nums2 = nums2;
for(int i = 0; i < nums2.size(); i++) {
mp[nums2[i]]++;
}
}
void add(int index, int val) {
mp[nums2[index]]--;
nums2[index] += val;
mp[nums2[index]]++;
}
int count(int tot) {
int cnt = 0;
for(int i = 0; i < nums1.size(); i++){
cnt += mp[tot - nums1[i]];
}
return cnt;
}
};
🐍 Python Code
from collections import Counter
class FindSumPairs:
def __init__(self, nums1: List[int], nums2: List[int]):
self.nums1 = nums1
self.nums2 = nums2
self.count = Counter(nums2)
def add(self, index: int, val: int) -> None:
self.count[self.nums2[index]] -= 1
self.nums2[index] += val
self.count[self.nums2[index]] += 1
def count(self, tot: int) -> int:
return sum(self.count[tot - x] for x in self.nums1)
💻 JavaScript Code
var FindSumPairs = function(nums1, nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
this.count = new Map();
for (const num of nums2) {
this.count.set(num, (this.count.get(num) || 0) + 1);
}
};
FindSumPairs.prototype.add = function(index, val) {
const oldVal = this.nums2[index];
this.count.set(oldVal, this.count.get(oldVal) - 1);
this.nums2[index] += val;
const newVal = this.nums2[index];
this.count.set(newVal, (this.count.get(newVal) || 0) + 1);
};
FindSumPairs.prototype.count = function(tot) {
let res = 0;
for (const num of this.nums1) {
const target = tot - num;
res += this.count.get(target) || 0;
}
return res;
};
📝 Key Takeaways
- Keep
nums1
static and use a hash map to dynamically tracknums2
’s values. -
add()
simply updates the frequency map. -
count()
usestarget - nums1[i]
lookups innums2
’s map.
This is a great pattern to remember when working with mutable data and frequent queries. 💡
✅ Final Thoughts
Hash maps and frequency counters shine in dynamic problems like this. Efficient tracking of changing values and reducing the number of unnecessary iterations makes a huge difference in performance.
Stay tuned for more interactive class-based design problems! 🔁
Top comments (7)
this is extremely impressive and i’ve enjoyed all of the research you’ve put into this project it adds up
you’ve ever found yourself wanting to generalize this pattern for even harder dynamic pair queries
Thanks Nathan!
Generalizing the pattern for harder dynamic pair queries is an interesting challenge. I'd love to explore approaches like graph-based methods or meta-learning to improve the model's adaptability and robustness.
Well Explained
Thanks Anna!!!
Interesting 👍
Thanks Vitor!
Good work on the algorithm.
The main problem with the C++ code is that it leaks memory: in every call of
count
wheretot - nums1[i]
is not in the map, a new entry for that number is added to the map.To fix that problem use a lookup instead of indexing.
The above problem would have been detected by the compiler if
count
had been declaredconst
.That's part of why using
const
liberally is best practice.Just sprinkle
const
liberally everywhere it's possible.The C++ code looks AI-generated. For example, why does it create a file? Why does it restrict the caller's arrays to
std::vector
? Why does it not permitconst
arguments? Why does it try to "optimize" iostream i/o when there is no i/o, or for that matter if there had been? Why does it try to generate warning diagnostics ini < nums2.size()
instead of using a range based loop? Why does it use Catexit
instead of a C++ destructor? And so on.As AI code that is all understandable, just blindly copied from somewhere.
As human written code it would just be baffling.
Some comments have been hidden by the post's author - find out more