Finding Pairs With a Certain Sum

Medium
2072.

Finding Pairs With a Certain Sum

MediumArrayHash TableDesign

Finding Pairs With a Certain Sum is a medium coding problem on arrays and hash table.

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) adds value to nums2[index].
  • int count(int tot) returns the number of index pairs (i, j) with nums1[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 <= 1000
  • 1 <= nums2.length <= 10^5
  • 1 <= nums1[i] <= 10^9
  • 1 <= nums2[i] <= 10^5
  • 0 <= index < nums2.length
  • 1 <= value <= 10^5
  • 1 <= tot <= 10^9
  • At most 1000 calls are made to add and to count each
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 */
var FindSumPairs = function(nums1, nums2) {
    
};

/**
 * @param {number} index
 * @param {number} value
 * @return {void}
 */
FindSumPairs.prototype.add = function(index, value) {
    
};

/**
 * @param {number} tot
 * @return {number}
 */
FindSumPairs.prototype.count = function(tot) {
    
};

Sign in to run your own test cases

Sign in

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) adds value to nums2[index].
  • int count(int tot) returns the number of index pairs (i, j) with nums1[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 <= 1000
  • 1 <= nums2.length <= 10^5
  • 1 <= nums1[i] <= 10^9
  • 1 <= nums2[i] <= 10^5
  • 0 <= index < nums2.length
  • 1 <= value <= 10^5
  • 1 <= tot <= 10^9
  • At most 1000 calls are made to add and to count each

Hints for Finding Pairs With a Certain Sum

  1. Hint 1

    Checking every pair costs |nums1| × |nums2| — up to 10^8 per count. The two arrays are very different in size; use that.

  2. Hint 2

    Keep a hash map counting how often each value occurs in nums2. For a fixed x in nums1, the pairs it makes number freq[tot - x].

  3. Hint 3

    add changes one entry of nums2: decrement the count of its old value and increment the count of its new one. Then count is one loop over the small array nums1.

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

  1. Store nums1, a copy of nums2, and freq: value → how many times it occurs in nums2.
  2. add(index, value): freq[nums2[index]]--, nums2[index] += value, freq[nums2[index]]++.
  3. count(tot): return the sum of freq[tot - x] over every x in nums1 (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 nums2 in count instead of nums1 is up to 100 times slower — iterate the array of length ≤ 1000.
  • add must 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 - x may 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 array

Java

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