LeetCode 1865 - Finding Pairs With a Certain Sum

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Design

Solution

Problem Understanding

This problem asks us to design a mutable data structure that supports two operations efficiently over two arrays, nums1 and nums2.

The first array, nums1, is fixed after initialization and never changes. The second array, nums2, is mutable, meaning its elements can be updated through add(index, val) operations.

The goal of the data structure is to answer repeated queries of the form:

How many index pairs (i, j) satisfy nums1[i] + nums2[j] == tot?

For every query, we need to count all valid combinations where one element comes from nums1 and another comes from nums2 such that their sum equals the requested target.

The class must support three operations:

FindSumPairs(nums1, nums2) initializes the structure.
add(index, val) modifies nums2[index] by adding val.
count(tot) returns the number of valid (i, j) pairs whose sum equals tot.

A key observation is that nums1 is relatively small, with at most 1000 elements, while nums2 can contain up to 100,000 elements. Also, there are at most 1000 calls each to add() and count().

This constraint strongly suggests that iterating over all pairs during every query would be prohibitively expensive. Since nums2 changes over time, we need a way to update information efficiently after each modification.

An important detail is that nums1[i] values can be very large, up to 10^9, meaning we cannot rely on array indexing or frequency arrays based on value ranges. A hash map is the natural choice for tracking frequencies.

Several edge cases deserve attention:

nums1 can contain duplicate values, which means multiple indices may contribute the same sum.
nums2 can also contain duplicates, and updates can increase existing values into repeated values already present elsewhere.
The same index in nums2 may be updated multiple times, requiring frequency bookkeeping to stay accurate.
Large integer values mean we must avoid approaches dependent on bounded numeric ranges.
Since nums2 is mutable, stale frequency counts can easily introduce bugs if updates are not handled carefully.

The problem guarantees valid indices for updates and positive update values, which simplifies correctness handling.

Approaches

Brute Force Approach

A straightforward solution is to explicitly compute the number of valid pairs every time count(tot) is called.

For each query:

Iterate through every element in nums1.
Iterate through every element in nums2.
Check whether their sum equals tot.
Increment the answer if it does.

The add() operation is trivial in this approach because we only modify nums2[index].

This solution is correct because it examines every possible pair (i, j) exactly once and counts all valid sums.

However, the performance is poor. Since nums1.length ≤ 1000 and nums2.length ≤ 100000, each count() operation may require up to:

$$1000 \times 100000 = 10^8$$

comparisons.

With up to 1000 count operations, this becomes far too expensive.

Key Insight for an Optimal Solution

The main observation is that nums1 is small and fixed, while nums2 is large but changes incrementally.

Instead of scanning all of nums2 for every query, we can maintain a frequency map of values in nums2.

Suppose we want to count pairs summing to tot.

For every value x in nums1, we need:

$$x + y = tot$$

Rearranging:

$$y = tot - x$$

So for each x in nums1, we only need to know how many times tot - x exists in nums2.

A hash map gives us this count in O(1) average time.

The challenge is keeping the frequency map updated after add() operations. We solve this by:

Decreasing the frequency of the old value.
Updating nums2[index].
Increasing the frequency of the new value.

This allows both updates and queries to remain efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	`O(n × m)` per count	`O(1)`	Checks every pair explicitly
Optimal	`O(m)` initialization, `O(1)` add, `O(n)` count	`O(m)`	Uses frequency map for `nums2`

Where:

n = len(nums1)
m = len(nums2)

Algorithm Walkthrough

Initialization

Store nums1 and nums2 inside the class.

We need direct access to nums2 because future updates modify it in place. 2. Build a frequency map for nums2.

For every value in nums2, store how many times it appears.

Example:

If:

nums2 = [1,4,5,2,5,4]

then:

frequency = {
    1: 1,
    2: 1,
    4: 2,
    5: 2
}

This structure allows constant time lookups during counting.

Add Operation

Retrieve the old value at nums2[index].

Since the frequency map currently reflects the old array state, we must remove its contribution. 2. Decrease the frequency of the old value.

If its frequency becomes zero, we may optionally remove it from the map. 3. Update nums2[index] += val. 4. Increase the frequency of the new value.

This keeps the map synchronized with the updated array.

Count Operation

Initialize result = 0.
Iterate through every value x in nums1.

Since nums1 is small, iterating over it is cheap. 3. Compute the complement:

needed = tot - x

Look up how many times needed exists in nums2.

Add that frequency to the result. 5. Return the accumulated result.

Why it works

The algorithm works because every valid pair must satisfy:

$$nums1[i] + nums2[j] = tot$$

For each fixed nums1[i] = x, the only possible matching value in nums2 is:

$$tot - x$$

The frequency map always accurately represents the current contents of nums2, because every update removes the old value count and adds the new one. Therefore, summing the frequencies of required complements counts every valid pair exactly once and never misses any valid combinations.

Python Solution

from collections import Counter
from typing import List

class FindSumPairs:

    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums1 = nums1
        self.nums2 = nums2
        self.frequency = Counter(nums2)

    def add(self, index: int, val: int) -> None:
        old_value = self.nums2[index]

        self.frequency[old_value] -= 1
        if self.frequency[old_value] == 0:
            del self.frequency[old_value]

        self.nums2[index] += val
        new_value = self.nums2[index]

        self.frequency[new_value] += 1

    def count(self, tot: int) -> int:
        pair_count = 0

        for num in self.nums1:
            needed = tot - num
            pair_count += self.frequency.get(needed, 0)

        return pair_count

# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index, val)
# param_2 = obj.count(tot)

The implementation closely follows the algorithm.

During initialization, we store both arrays and construct a Counter for nums2. This serves as our frequency map and enables constant time lookups.

The add() method first removes the contribution of the previous value from the frequency map. After updating nums2[index], it inserts the new value back into the frequency structure. This ensures consistency between nums2 and its frequency map at all times.

The count() method iterates through nums1. For each number, it computes the complement needed to reach tot and retrieves its occurrence count in nums2. Since duplicate values are naturally tracked by the frequency map, repeated valid pairs are counted automatically.

Go Solution

type FindSumPairs struct {
	nums1 []int
	nums2 []int
	freq  map[int]int
}

func Constructor(nums1 []int, nums2 []int) FindSumPairs {
	freq := make(map[int]int)

	for _, num := range nums2 {
		freq[num]++
	}

	return FindSumPairs{
		nums1: nums1,
		nums2: nums2,
		freq:  freq,
	}
}

func (this *FindSumPairs) Add(index int, val int) {
	oldValue := this.nums2[index]

	this.freq[oldValue]--
	if this.freq[oldValue] == 0 {
		delete(this.freq, oldValue)
	}

	this.nums2[index] += val
	newValue := this.nums2[index]

	this.freq[newValue]++
}

func (this *FindSumPairs) Count(tot int) int {
	pairCount := 0

	for _, num := range this.nums1 {
		needed := tot - num
		pairCount += this.freq[needed]
	}

	return pairCount
}

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * obj := Constructor(nums1, nums2);
 * obj.Add(index,val);
 * param_2 := obj.Count(tot);
 */

The Go implementation mirrors the Python solution closely.

Instead of Counter, Go uses map[int]int to track frequencies. Accessing a missing key automatically returns 0, which makes complement lookups straightforward.

The Add() method updates frequencies carefully by decrementing the old value before incrementing the new one. Removing keys whose count becomes zero is optional but keeps the map cleaner.

Integer overflow is not an issue here because values remain within standard 64-bit integer limits, and Go's int type safely accommodates the constraints.

Worked Examples

Example 1

Initial state:

nums1 = [1,1,2,2,2,3]
nums2 = [1,4,5,2,5,4]

Frequency map:

Value	Frequency
1	1
2	1
4	2
5	2

Operation 1: `count(7)`

We calculate complements for every value in nums1.

nums1 value	Needed value	Frequency in nums2	Added pairs
1	6	0	0
1	6	0	0
2	5	2	2
2	5	2	2
2	5	2	2
3	4	2	2

Total:

Operation 2: `add(3, 2)`

Before update:

nums2[3] = 2

Decrease frequency of 2:

2 -> 0

Updated array:

nums2 = [1,4,5,4,5,4]

Increase frequency of 4:

Value	Frequency
1	1
4	3
5	2

Operation 3: `count(8)`

nums1 value	Needed	Frequency	Contribution
1	7	0	0
1	7	0	0
2	6	0	0
2	6	0	0
2	6	0	0
3	5	2	2

Answer:

Operation 4: `count(4)`

nums1 value	Needed	Frequency	Contribution
1	3	0	0
1	3	0	0
2	2	0	0
2	2	0	0
2	2	0	0
3	1	1	1

Answer:

Operation 5: `add(0, 1)`

Updated:

nums2 = [2,4,5,4,5,4]

Frequency:

Value	Frequency
2	1
4	3
5	2

Operation 6: `add(1, 1)`

Updated:

nums2 = [2,5,5,4,5,4]

Frequency:

Value	Frequency
2	1
4	2
5	3

Operation 7: `count(7)`

nums1 value	Needed	Frequency	Contribution
1	6	0	0
1	6	0	0
2	5	3	3
2	5	3	3
2	5	3	3
3	4	2	2

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	`O(m)` initialization, `O(1)` add, `O(n)` count	Building the frequency map takes `O(m)`, updates are constant time, counting iterates through `nums1`
Space	`O(m)`	Frequency map stores occurrences of values from `nums2`

Here, n is the size of nums1 and m is the size of nums2.

The critical optimization comes from replacing repeated scans of nums2 with constant time hash map lookups. Since nums1 has at most 1000 elements, iterating through it during each count() operation is very efficient.

Test Cases

# Example from problem statement
obj = FindSumPairs(
    [1, 1, 2, 2, 2, 3],
    [1, 4, 5, 2, 5, 4]
)

assert obj.count(7) == 8  # Initial example query

obj.add(3, 2)
assert obj.count(8) == 2  # After updating index 3

assert obj.count(4) == 1  # Single valid pair

obj.add(0, 1)
obj.add(1, 1)

assert obj.count(7) == 11  # Final example result

# Minimum size arrays
obj = FindSumPairs([1], [1])
assert obj.count(2) == 1  # Single pair exists
assert obj.count(3) == 0  # No valid pair

# Duplicate handling
obj = FindSumPairs([2, 2, 2], [3, 3])
assert obj.count(5) == 6  # 3 * 2 valid combinations

# Multiple updates to same index
obj = FindSumPairs([1, 2], [2])
assert obj.count(3) == 1  # 1 + 2

obj.add(0, 1)
assert obj.count(3) == 1  # 2 + 1 no longer possible, 1 + 3 not valid

assert obj.count(4) == 1  # 1 + 3

# Large values
obj = FindSumPairs([10**9], [10**5])
assert obj.count(10**9 + 10**5) == 1  # Large numbers handled

# No matching pairs
obj = FindSumPairs([1, 2, 3], [10, 20])
assert obj.count(100) == 0  # Impossible target

# Frequency removal edge case
obj = FindSumPairs([1], [5])
obj.add(0, 5)  # 5 becomes 10
assert obj.count(6) == 0  # Old value removed
assert obj.count(11) == 1  # New value counted

Test	Why
Problem statement example	Validates correctness across mixed operations
Single element arrays	Tests smallest valid input
Duplicate values	Verifies multiplicity counting
Multiple updates to same index	Ensures frequency synchronization
Large values	Confirms hash map handles large numbers
No matching pairs	Tests zero-result behavior
Frequency removal	Verifies stale values are removed correctly

Edge Cases

Duplicate Values in Both Arrays

A common mistake is forgetting that the problem counts index pairs, not unique values. If nums1 = [2,2,2] and nums2 = [3,3], there are six valid pairs, not one.

The frequency map handles this naturally. When counting, every occurrence in nums1 contributes independently, and the stored count of matching values in nums2 automatically multiplies the result correctly.

Updating an Element Multiple Times

Repeated updates to the same index can easily break frequency tracking if the old value is not removed before adding the new value.

For example:

nums2 = [5]

After:

add(0, 5)

the value becomes 10.

If we forget to decrement the count for 5, future queries may incorrectly count both 5 and 10. The implementation explicitly removes the old contribution before inserting the new one, preventing stale frequencies.

Values Becoming Unique or Disappearing

When an update changes the last occurrence of a value, its frequency becomes zero.