DEV Community

Cover image for ⛴️Beginner-Friendly Guide "Find Sum Pairs with Dynamic Count Updates" – LeetCode 1865 (C++ | Python | JavaScript)
Om Shree
Om Shree

Posted on

⛴️Beginner-Friendly Guide "Find Sum Pairs with Dynamic Count Updates" – LeetCode 1865 (C++ | Python | JavaScript)

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): Add val to nums2[index].
    • count(tot): Count how many pairs (i, j) exist such that nums1[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 that count(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;
    }
};
Enter fullscreen mode Exit fullscreen mode

🐍 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)
Enter fullscreen mode Exit fullscreen mode

💻 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;
};
Enter fullscreen mode Exit fullscreen mode

📝 Key Takeaways

  • Keep nums1 static and use a hash map to dynamically track nums2’s values.
  • add() simply updates the frequency map.
  • count() uses target - nums1[i] lookups in nums2’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)

Collapse
 
nathan_tarbert profile image
Nathan Tarbert

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

Collapse
 
om_shree_0709 profile image
Om Shree

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.

Collapse
 
thedeepseeker profile image
Anna kowoski

Well Explained

Collapse
 
om_shree_0709 profile image
Om Shree

Thanks Anna!!!

Collapse
 
vianavitordev profile image
Vitor Hugo Marques Viana • Edited

Interesting 👍

Collapse
 
om_shree_0709 profile image
Om Shree

Thanks Vitor!

Collapse
 
alfps profile image
Info Comment hidden by post author - thread only accessible via permalink
Alf P. Steinbach • Edited

Good work on the algorithm.

The main problem with the C++ code is that it leaks memory: in every call of count where tot - 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 declared const.

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 permit const 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 in i < nums2.size() instead of using a range based loop? Why does it use C atexit 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