Finding Pairs With a Certain Sum

June 5, 20265 min read

leetcodeproblemmediumarraysdesignhash-map

LeetCode Finding Pairs With a Certain Sum (problem 1865) asks you to design a class that counts pairs across two arrays whose values sum to a given target. The twist: one array gets modified over time, and you need to answer count queries efficiently after each update.

The problem

You are given two integer arrays nums1 and nums2. Implement a class FindSumPairs that supports three operations:

FindSumPairs(nums1, nums2) initializes the object with the two arrays.
add(index, val) adds val to nums2[index].
count(tot) returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

Example: nums1 = [1, 1, 2, 3], nums2 = [2, 4, 5, 2, 5]. Calling count(7) returns 8, because there are 8 valid (i, j) pairs where nums1[i] + nums2[j] = 7.

nums1 = [1, 1, 2, 3], nums2 = [2, 4, 5, 2, 5]. A frequency map of nums2 allows O(1) lookups when counting pairs that sum to a target.

Why this problem matters

This problem tests two skills at once: designing a data structure and picking the right algorithmic tradeoff. A brute-force approach that scans both arrays on every count() call would be too slow. You need to recognize that a frequency map lets you trade a small amount of bookkeeping during add() for a massive speedup during count().

The pattern of maintaining a frequency map that stays in sync with a mutable array shows up in many design problems. Once you internalize it, you can apply it to problems involving dynamic counting, rolling statistics, and stream processing.

The approach

The key observation is the asymmetry in the constraints. nums1 has at most 1,000 elements, while nums2 can have up to 100,000. The nums1 array never changes, but nums2 gets modified by add() calls.

This means you should iterate over nums1 (the small array) and do O(1) lookups against nums2 (the large array). To make those lookups O(1), maintain a frequency map of the current values in nums2.

For count(tot): loop through each nums1[i] and look up tot - nums1[i] in the frequency map. Sum up all the counts.

For add(index, val): decrement the count of the old value at nums2[index], update the value, then increment the count of the new value.

The solution

from collections import Counter

class FindSumPairs:
    def __init__(self, nums1, nums2):
        self.nums1 = nums1
        self.nums2 = nums2
        self.freq = Counter(nums2)

    def add(self, index, val):
        self.freq[self.nums2[index]] -= 1
        self.nums2[index] += val
        self.freq[self.nums2[index]] += 1

    def count(self, tot):
        result = 0
        for x in self.nums1:
            result += self.freq.get(tot - x, 0)
        return result

Practice this problem with spaced repetition

Step-by-step walkthrough

Step 1: Initialize with nums1 = [1, 1, 2, 3] and nums2 = [2, 4, 5, 2, 5]

Build a frequency map from nums2. Count how many times each value appears.

freq = {2: 2, 4: 1, 5: 2}. This map is the key data structure.

Step 2: Call add(2, 1) to update nums2[2]

nums2[2] was 5, now becomes 6. Decrement freq[5] and increment freq[6].

The freq map stays in sync with nums2 after every add() call.

Step 3: Call count(7) to find all pairs summing to 7

For each element in nums1, look up (7 - nums1[i]) in the frequency map.

Every element in nums1 found a matching complement. count(7) returns 4.

Result: count(7) = 4 pairs found. The freq map approach avoids scanning nums2 on every query.

The walkthrough shows the three phases clearly. First, build the frequency map from nums2 during initialization. Then, when add() is called, update the map in O(1) by adjusting two entries. Finally, when count() is called, iterate over the small nums1 array and sum up the frequency map lookups.

Notice that the add() method does not rebuild the map from scratch. It only touches two entries: one decrement and one increment. This is what keeps it O(1) regardless of how large nums2 is.

Complexity analysis

Approach	Init	add()	count()	Space
Brute force (scan both arrays)	O(1)	O(1)	O(m * n)	O(1)
Frequency map on nums2	O(n)	O(1)	O(m)	O(n)

Here m is the length of nums1 and n is the length of nums2. The frequency map approach makes count() depend only on m (at most 1,000), not on n (up to 100,000). That is a 100x improvement per query, and with up to 1,000 count() calls, it adds up fast.

The building blocks

Frequency map maintenance

The core technique here is keeping a frequency map in sync with a mutable array. Every time a value changes, you decrement the old count and increment the new count. This two-step update pattern appears in sliding window problems, LRU caches, and any scenario where you need running statistics over a changing collection.

Asymmetric iteration

When two collections have very different sizes, iterate over the smaller one and do lookups against the larger one. This is a general principle: if you can choose which side to scan and which side to index, always scan the smaller side. The same idea applies to database joins, search algorithms, and any two-collection problem.

When you see two arrays with different size constraints, that asymmetry is a hint. The problem is practically telling you which array to iterate and which to index.

Edge cases

Duplicate values in nums1. If nums1 = [3, 3, 3] and you call count(7), each 3 independently looks up freq[4]. Duplicates in nums1 multiply the pair count, and the algorithm handles this naturally.
add() with val = 0. Adding zero does not change the value, but the code still decrements and increments the same key. The net effect is zero, so correctness is maintained.
Target not reachable. If tot - nums1[i] never exists in the frequency map, every lookup returns 0 and the result is 0. No special handling needed.
Negative values after add(). The problem constraints allow val to be positive (between 1 and 1000), and initial values are positive. But the frequency map works with any integer key, so the approach generalizes even if values could become negative.
Repeated add() calls on the same index. Each call correctly adjusts the frequency map relative to the current value, not the original value. The map always reflects the actual state of nums2.

From understanding to recall

The insight behind this problem is not complicated once you see it: maintain a frequency map on the large, mutable array and iterate over the small, static array. The add() method touches exactly two map entries. The count() method does len(nums1) lookups.

What makes this tricky in an interview is recognizing the asymmetry quickly. If you start by iterating over nums2 in count(), you get O(n) per query instead of O(m), and that is the difference between passing and getting a time limit exceeded. Train yourself to check the constraints first. When one array is 100x smaller than the other, that is your starting point.

Practice rebuilding the frequency map update logic from memory. The two-step pattern (decrement old, increment new) is simple but easy to get wrong under pressure if you mix up the order or forget to update the actual array value.

Two Sum - Classic hash map pair finding
4Sum II - Hash map to count pair sums across arrays
Subarray Sum Equals K - Hash map counting technique

Build your pattern library with CodeBricks

Spaced repetition turns "I understood it once" into "I can solve it cold." The frequency map maintenance pattern in this problem is the same building block behind dozens of design questions. Practice it at increasing intervals, and you will reach for it automatically when an interview problem involves counting over mutable data.

Start mastering medium LeetCode patterns today