Finding Pairs With a Certain Sum — Problem & Solution
Finding Pairs With a Certain Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Finding Pairs With a Certain Sum is a medium coding problem on arrays and hash table.
- Difficulty: Medium
- Topics: Arrays, Hash Table
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two integer arrays, nums1 and nums2. The second one changes over time; the first never does.
Write the class FindSumPairs:
FindSumPairs(int[] nums1, int[] nums2)stores the two arrays.void add(int index, int value)addsvaluetonums2[index].int count(int tot)returns the number of index pairs(i, j)withnums1[i] + nums2[j] == tot.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.
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: Sums of 7: each of the three 2s pairs with both 5s (6 pairs) and the 3 pairs with both 4s (2 more), 8 in all. After add(3,2) nums2 is [1,4,5,4,5,4]: the 3 meets both 5s to make 8, and only 3 + 1 makes 4. Two more additions give [2,5,5,4,5,4], where 9 + 2 = 11 pairs make 7.
Example 2
Input: ["FindSumPairs","count","add","count"]
[[[5],[5,5]],[10],[1,100000],[10]]
Output: [null,2,null,1]
Explanation: 5 + 5 = 10 twice. After nums2[1] grows to 100005, only one pair is left.
Constraints
1 <= nums1.length <= 10001 <= nums2.length <= 10^51 <= nums1[i] <= 10^91 <= nums2[i] <= 10^50 <= index < nums2.length1 <= value <= 10^51 <= tot <= 10^9At most 1000 calls are made to add and to count each
Hints for Finding Pairs With a Certain Sum
Hint 1
Checking every pair costs |nums1| × |nums2| — up to 10^8 per count. The two arrays are very different in size; use that.
Hint 2
Keep a hash map counting how often each value occurs in
nums2. For a fixedxinnums1, the pairs it makes numberfreq[tot - x].Hint 3
addchanges one entry ofnums2: decrement the count of its old value and increment the count of its new one. Thencountis one loop over the small arraynums1.
How to solve Finding Pairs With a Certain Sum
Loop over the small array and look the complement up in a frequency map of the large one. Updates only move one element between two counts.
Approach
- Store
nums1, a copy ofnums2, andfreq: value → how many times it occurs innums2. add(index, value):freq[nums2[index]]--,nums2[index] += value,freq[nums2[index]]++.count(tot): return the sum offreq[tot - x]over everyxinnums1(a missing key counts 0).
Why it works
A pair (i, j) has nums2[j] = tot - nums1[i], so for each i the matching j are exactly the occurrences of tot - nums1[i] in nums2, which freq holds. add keeps freq equal to the true counts of the current nums2, so every query sees the array as it is.
Complexity
- Time —
O(n1 + n2) to build, O(1) per add, O(n1) per count - Space —
O(n2)
Pitfalls
- Looping over
nums2incountinstead ofnums1is up to 100 times slower — iterate the array of length ≤ 1000. addmust update the frequency map, not just the array, or later counts read stale values.- The answer can reach 10^8, which still fits a 32-bit int; the sum
tot - xmay be negative and simply finds nothing.
Reference solution
Python
from collections import Counter
class FindSumPairs:
def __init__(self, nums1: List[int], nums2: List[int]):
self.nums1 = nums1
self.nums2 = list(nums2)
self.freq = Counter(nums2)
def add(self, index: int, value: int) -> None:
self.freq[self.nums2[index]] -= 1
self.nums2[index] += value
self.freq[self.nums2[index]] += 1
def count(self, tot: int) -> int:
freq = self.freq
return sum(freq.get(tot - x, 0) for x in self.nums1) # loop over the short arrayJava
class FindSumPairs {
private int[] nums1, nums2;
private HashMap<Integer, Integer> freq = new HashMap<>();
public FindSumPairs(int[] nums1, int[] nums2) {
this.nums1 = nums1;
this.nums2 = nums2.clone();
for (int y : nums2) freq.merge(y, 1, Integer::sum);
}
public void add(int index, int value) {
freq.merge(nums2[index], -1, Integer::sum);
nums2[index] += value;
freq.merge(nums2[index], 1, Integer::sum);
}
public int count(int tot) {
int c = 0;
for (int x : nums1) c += freq.getOrDefault(tot - x, 0); // loop over the short array
return c;
}
}C++
class FindSumPairs {
vector<int> nums1, nums2;
unordered_map<int, int> freq;
public:
FindSumPairs(vector<int>& nums1, vector<int>& nums2) : nums1(nums1), nums2(nums2) {
for (int y : nums2) freq[y]++;
}
void add(int index, int value) {
freq[nums2[index]]--;
nums2[index] += value;
freq[nums2[index]]++;
}
int count(int tot) {
int c = 0;
for (int x : nums1) { // loop over the short array
auto it = freq.find(tot - x);
if (it != freq.end()) c += it->second;
}
return c;
}
};JavaScript
var FindSumPairs = function(nums1, nums2) {
this.nums1 = nums1;
this.nums2 = nums2.slice();
this.freq = new Map();
for (var i = 0; i < nums2.length; i++) this.freq.set(nums2[i], (this.freq.get(nums2[i]) || 0) + 1);
};
FindSumPairs.prototype.add = function(index, value) {
var old = this.nums2[index];
this.freq.set(old, this.freq.get(old) - 1);
this.nums2[index] = old + value;
this.freq.set(old + value, (this.freq.get(old + value) || 0) + 1);
};
FindSumPairs.prototype.count = function(tot) {
var c = 0;
for (var i = 0; i < this.nums1.length; i++) c += this.freq.get(tot - this.nums1[i]) || 0; // loop over the short array
return c;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets