1865. Finding Pairs With a Certain Sum Solution

Q: Is Finding Pairs With a Certain Sum easy or hard?

The problem is rated Medium because it combines array processing with data structure design. The core logic is straightforward once you recognize that maintaining a frequency map allows efficient pair counting across repeated queries.

Q: Finding Pairs With a Certain Sum Python/Java solution

In Python, use a dictionary or collections.Counter to store frequencies of nums2. In Java, use a HashMap . Both implementations update frequencies during add operations and iterate through nums1 during count queries.

The problem

You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:

Add a positive integer to an element of a given index in the array nums2.
Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value (0 <= i < nums1.length and 0 <= j < nums2.length).

Implement the FindSumPairs class:

FindSumPairs(int[] nums1, int[] nums2) Initializes the FindSumPairs object with two integer arrays nums1 and nums2.
void add(int index, int val) Adds val to nums2[index], i.e., apply nums2[index] += val.
int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

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
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4
findSumPairs.add(3, 2); // now nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // return 2; pairs (5,2), (5,4) make 3 + 5
findSumPairs.count(4);  // return 1; pair (5,0) makes 3 + 1
findSumPairs.add(0, 1); // now nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // now nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4

Constraints:

1 <= nums1.length <= 1000
1 <= nums2.length <= 10⁵
1 <= nums1[i] <= 10⁹
1 <= nums2[i] <= 10⁵
0 <= index < nums2.length
1 <= val <= 10⁵
1 <= tot <= 10⁹
At most 1000 calls are made to add and count each.

Approach overview

Problem Overview: You maintain two integer arrays nums1 and nums2. The data structure must support two operations: add a value to an index in nums2, and count how many pairs (i, j) satisfy nums1[i] + nums2[j] == total. The challenge is answering repeated count queries efficiently while updates modify nums2.

Approach 1: HashMap Frequency Count (O(n) count, O(1) add)

Store a frequency map for values in nums2. During initialization, iterate through nums2 and record how many times each value appears using a hash map. For a count(total) query, iterate through every element x in nums1 and compute the complement total - x. A single hash lookup gives how many elements in nums2 complete the pair. For the add(index, val) operation, decrease the frequency of the old value in nums2[index], update the array, then increase the frequency of the new value. Each update takes constant time because it only adjusts two hash entries. The count query runs in O(n1) time with O(n2) space for the map. This approach relies on fast lookups from a hash table and works well because nums1 never changes.

Approach 2: Two-Pointer Technique (Alternative) (O(n log n) preprocessing, O(n) query)

If both arrays are kept sorted, you can count pairs using a classic two-pointer sweep. Start one pointer at the beginning of nums1 and another at the end of nums2. Move pointers based on whether the current sum is smaller or larger than the target. This finds all valid pairs in linear time after sorting. The downside appears when the add operation changes values in nums2. Maintaining sorted order requires reinserting the updated value or re-sorting, which can cost O(n) or O(n log n). Space complexity stays O(1) beyond the arrays. This method demonstrates how pair-sum problems can be solved efficiently with sorted data using techniques common in array and pointer manipulation problems.

Recommended for interviews: The HashMap frequency solution is the expected answer. It cleanly separates responsibilities: nums1 is scanned during queries, while nums2 updates only adjust counts. Interviewers want to see recognition that repeated pair queries benefit from a precomputed frequency structure. The two-pointer approach helps explain the pair-sum intuition, but the hash-based design demonstrates stronger understanding of data structure design and dynamic updates.

Approach 1: HashMap Frequency Count

In this approach, we utilize a hashmap (or dictionary) to store the frequency count of numbers in nums2. When we need to count pairs, for each number in nums1, we determine the complementary number needed from nums2 to reach the total. Using our hashmap, we can quickly get the count for how many such complements exist. Updates to nums2 only require adjusting counts in the hashmap, maintaining efficiency.

Python

from collections import defaultdict

class FindSumPairs:

    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums1 = nums1
        self.nums2 = nums2
        self.freq2 = defaultdict(int)
        for num in nums2:
            self.freq2[num] += 1

    def add(self, index: int, val: int) -> None:
        original_value = self.nums2[index]
        self.freq2[original_value] -= 1
        if self.freq2[original_value] == 0:
            del self.freq2[original_value]
        self.nums2[index] += val
        self.freq2[self.nums2[index]] += 1

    def count(self, tot: int) -> int:
        count = 0
        for num in self.nums1:
            complement = tot - num
            if complement in self.freq2:
                count += self.freq2[complement]
        return count

Java

import java.util.HashMap;

class FindSumPairs {
    private int[] nums1;
    private int[] nums2;
    private HashMap<Integer, Integer> freq2;

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        this.freq2 = new HashMap<>();
        for (int num : nums2) {
            this.freq2.put(num, this.freq2.getOrDefault(num, 0) + 1);
        }
    }

    public void add(int index, int val) {
        int originalValue = this.nums2[index];
        this.freq2.put(originalValue, this.freq2.get(originalValue) - 1);
        if (this.freq2.get(originalValue) == 0) {
            this.freq2.remove(originalValue);
        }
        this.nums2[index] += val;
        this.freq2.put(this.nums2[index], this.freq2.getOrDefault(this.nums2[index], 0) + 1);
    }

    public int count(int tot) {
        int count = 0;
        for (int num : nums1) {
            int complement = tot - num;
            if (this.freq2.containsKey(complement)) {
                count += this.freq2.get(complement);
            }
        }
        return count;
    }
}

C++

#include <unordered_map>
#include <vector>
using namespace std;

class FindSumPairs {
private:
    vector<int> nums1, nums2;
    unordered_map<int, int> freq2;

public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) : nums1(nums1), nums2(nums2) {
        for (int num : nums2) {
            freq2[num]++;
        }
    }

    void add(int index, int val) {
        int originalValue = nums2[index];
        freq2[originalValue]--;
        if (freq2[originalValue] == 0) {
            freq2.erase(originalValue);
        }
        nums2[index] += val;
        freq2[nums2[index]]++;
    }

    int count(int tot) {
        int count = 0;
        for (int num : nums1) {
            int complement = tot - num;
            if (freq2.find(complement) != freq2.end()) {
                count += freq2[complement];
            }
        }
        return count;
    }
};

JavaScript

class FindSumPairs {
    constructor(nums1, nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        this.freq2 = new Map();
        for (let num of nums2) {
            this.freq2.set(num, (this.freq2.get(num) || 0) + 1);
        }
    }

    add(index, val) {
        const originalValue = this.nums2[index];
        this.freq2.set(originalValue, this.freq2.get(originalValue) - 1);
        if (this.freq2.get(originalValue) === 0) {
            this.freq2.delete(originalValue);
        }
        this.nums2[index] += val;
        this.freq2.set(this.nums2[index], (this.freq2.get(this.nums2[index]) || 0) + 1);
    }

    count(tot) {
        let count = 0;
        for (let num of this.nums1) {
            const complement = tot - num;
            if (this.freq2.has(complement)) {
                count += this.freq2.get(complement);
            }
        }
        return count;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VAL 100000

typedef struct {
    int *nums1;
    size_t nums1Size;
    int *nums2;
    size_t nums2Size;
    int freq2[MAX_VAL + 1];
} FindSumPairs;

FindSumPairs* findSumPairsCreate(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    FindSumPairs* obj = malloc(sizeof(FindSumPairs));
    obj->nums1 = nums1;
    obj->nums1Size = nums1Size;
    obj->nums2 = nums2;
    obj->nums2Size = nums2Size;
    memset(obj->freq2, 0, sizeof(int) * (MAX_VAL + 1));
    for (int i = 0; i < nums2Size; ++i) {
        obj->freq2[nums2[i]]++;
    }
    return obj;
}

void findSumPairsAdd(FindSumPairs* obj, int index, int val) {
    int originalValue = obj->nums2[index];
    obj->freq2[originalValue]--;
    obj->nums2[index] += val;
    obj->freq2[obj->nums2[index]]++;
}

int findSumPairsCount(FindSumPairs* obj, int tot) {
    int count = 0;
    for (int i = 0; i < obj->nums1Size; ++i) {
        int complement = tot - obj->nums1[i];
        if (complement >= 0 && complement <= MAX_VAL) {
            count += obj->freq2[complement];
        }
    }
    return count;
}

void findSumPairsFree(FindSumPairs* obj) {
    free(obj);
}

using System.Collections.Generic;

public class FindSumPairs {
    private int[] nums1;
    private int[] nums2;
    private Dictionary<int, int> freq2;

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        this.freq2 = new Dictionary<int, int>();
        foreach (int num in nums2) {
            if (!this.freq2.ContainsKey(num)) {
                this.freq2[num] = 0;
            }
            this.freq2[num]++;
        }
    }

    public void Add(int index, int val) {
        int originalValue = this.nums2[index];
        this.freq2[originalValue]--;
        if (this.freq2[originalValue] == 0) {
            this.freq2.Remove(originalValue);
        }
        this.nums2[index] += val;
        if (!this.freq2.ContainsKey(this.nums2[index])) {
            this.freq2[this.nums2[index]] = 0;
        }
        this.freq2[this.nums2[index]]++;
    }

    public int Count(int tot) {
        int count = 0;
        foreach (int num in this.nums1) {
            int complement = tot - num;
            if (this.freq2.ContainsKey(complement)) {
                count += this.freq2[complement];
            }
        }
        return count;
    }
}

We use a defaultdict from the collections module to keep track of the frequencies of nums2 elements. The add method updates the frequencies accordingly. The count method calculates the number of valid pairs by iterating through nums1 while checking the frequency of the needed complementary value from nums2 using the hashmap.

Complexity

Time Complexity: O(n1 + q), where n1 is the length of nums1 and q is the number of queries. Each add operation takes O(1). Space Complexity: O(n2), where n2 is the length of nums2 due to storing frequencies.

Try this approach in the editor

Approach 2: Two-Pointer Technique (Alternative)

Here we consider a two-pointer technique by treating nums1 and nums2 as sorted arrays. Though this approach may require sorting initially, it can be beneficial when large datasets and specific queries are considered, but given nums1 and nums2 may not be sorted initially, this approach is less optimal without initial preprocessing.

Python

class FindSumPairs:

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

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

    def count(self, tot: int) -> int:
        i, j = 0, len(self.nums2) - 1
        count = 0
        while i < len(self.nums1) and j >= 0:
            if self.nums1[i] + self.nums2[j] == tot:
                count += 1
                j -= 1
            elif self.nums1[i] + self.nums2[j] < tot:
                i += 1
            else:
                j -= 1
        return count

Java

import java.util.Arrays;

class FindSumPairs {
    private int[] nums1;
    private int[] nums2;

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = Arrays.copyOf(nums1, nums1.length);
        this.nums2 = Arrays.copyOf(nums2, nums2.length);
        Arrays.sort(this.nums1);
        Arrays.sort(this.nums2);
    }

    public void add(int index, int val) {
        nums2[index] += val;
        Arrays.sort(nums2);
    }

    public int count(int tot) {
        int i = 0, j = nums2.length - 1, count = 0;
        while (i < nums1.length && j >= 0) {
            int sum = nums1[i] + nums2[j];
            if (sum == tot) {
                count++;
                j--;
            } else if (sum < tot) {
                i++;
            } else {
                j--;
            }
        }
        return count;
    }
}

With the two-pointer strategy, we use sorted lists to find sums that reach the desired total. The algorithm walks through the lists, adjusting pointers based on sum comparisons.

Complexity

Time Complexity: O(n2 log n2 + m + q(n1 + n2)) where m is the overall number of elements changed or checked. Space Complexity: O(1) besides input arrays.

Try this approach in the editor

Approach 3: Hash Table

We note that the length of the array nums1 does not exceed {10}^3, while the length of the array nums2 reaches {10}^5. Therefore, if we directly enumerate all index pairs (i, j) and check whether nums1[i] + nums2[j] equals the specified value tot, it will exceed the time limit.

Can we only enumerate the shorter array nums1? The answer is yes. We use a hash table cnt to count the occurrences of each element in the array nums2, then enumerate each element x in the array nums1 and calculate the sum of cnt[tot - x].

When calling the add method, we need to first decrement the value corresponding to nums2[index] in cnt by 1, then add val to the value of nums2[index], and finally increment the value corresponding to nums2[index] in cnt by 1.

When calling the count method, we only need to traverse the array nums1 and calculate the sum of cnt[tot - x] for each element x.

The time complexity is O(n times q), and the space complexity is O(m). Here, n and m are the lengths of the arrays nums1 and nums2, respectively, and q is the number of times the count method is called.

TypeScript

class FindSumPairs {
    private nums1: number[];
    private nums2: number[];
    private cnt: Map<number, number>;

    constructor(nums1: number[], nums2: number[]) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        this.cnt = new Map();
        for (const x of nums2) {
            this.cnt.set(x, (this.cnt.get(x) || 0) + 1);
        }
    }

    add(index: number, val: number): void {
        const old = this.nums2[index];
        this.cnt.set(old, this.cnt.get(old)! - 1);
        this.nums2[index] += val;
        const now = this.nums2[index];
        this.cnt.set(now, (this.cnt.get(now) || 0) + 1);
    }

    count(tot: number): number {
        return this.nums1.reduce((acc, x) => acc + (this.cnt.get(tot - x) || 0), 0);
    }
}

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

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

func Constructor(nums1 []int, nums2 []int) FindSumPairs {
	cnt := map[int]int{}
	for _, x := range nums2 {
		cnt[x]++
	}
	return FindSumPairs{nums1, nums2, cnt}
}

func (this *FindSumPairs) Add(index int, val int) {
	this.cnt[this.nums2[index]]--
	this.nums2[index] += val
	this.cnt[this.nums2[index]]++
}

func (this *FindSumPairs) Count(tot int) (ans int) {
	for _, x := range this.nums1 {
		ans += this.cnt[tot-x]
	}
	return
}

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

Rust

use std::collections::HashMap;

struct FindSumPairs {
    nums1: Vec<i32>,
    nums2: Vec<i32>,
    cnt: HashMap<i32, i32>,
}

impl FindSumPairs {
    fn new(nums1: Vec<i32>, nums2: Vec<i32>) -> Self {
        let mut cnt = HashMap::new();
        for &x in &nums2 {
            *cnt.entry(x).or_insert(0) += 1;
        }
        Self { nums1, nums2, cnt }
    }

    fn add(&mut self, index: i32, val: i32) {
        let i = index as usize;
        let old_val = self.nums2[i];
        *self.cnt.entry(old_val).or_insert(0) -= 1;
        if self.cnt[&old_val] == 0 {
            self.cnt.remove(&old_val);
        }

        self.nums2[i] += val;
        let new_val = self.nums2[i];
        *self.cnt.entry(new_val).or_insert(0) += 1;
    }

    fn count(&self, tot: i32) -> i32 {
        let mut ans = 0;
        for &x in &self.nums1 {
            let target = tot - x;
            if let Some(&c) = self.cnt.get(&target) {
                ans += c;
            }
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
HashMap Frequency Count	Time Complexity: O(n1 + q), where n1 is the length of nums1 and q is the number of queries. Each add operation takes O(1). Space Complexity: O(n2), where n2 is the length of nums2 due to storing frequencies.
Two-Pointer Technique (Alternative)	Time Complexity: O(n2 log n2 + m + q(n1 + n2)) where m is the overall number of elements changed or checked. Space Complexity: O(1) besides input arrays.
Hash Table	–

Complexity analysis

Approach	Time	Space	When to Use
HashMap Frequency Count	Add: O(1), Count: O(n1)	O(n2)	Best general solution when nums2 is frequently updated and many count queries are executed
Two-Pointer Technique (Sorted Arrays)	Query: O(n), Updates: O(n) or O(n log n)	O(1)	Works when arrays remain sorted or updates are rare

Frequently asked questions

Is Finding Pairs With a Certain Sum easy or hard?

The problem is rated Medium because it combines array processing with data structure design. The core logic is straightforward once you recognize that maintaining a frequency map allows efficient pair counting across repeated queries.

Finding Pairs With a Certain Sum Python/Java solution

In Python, use a dictionary or collections.Counter to store frequencies of nums2. In Java, use a HashMap<Integer, Integer>. Both implementations update frequencies during add operations and iterate through nums1 during count queries.

How to solve Finding Pairs With a Certain Sum in O(n)?

Each count query can be handled in O(n1) time using a frequency hash map. Iterate through nums1, compute the complement total - x, and retrieve how many times it appears in nums2 from the map. The add operation updates the map in constant time.

What is the best approach for Finding Pairs With a Certain Sum?

The HashMap frequency approach is the most efficient design. Store counts of every value in nums2, then for each element x in nums1 check how many times total - x appears using a hash lookup. Add operations update the frequency map in O(1), while count queries run in O(n1) time.

Is Finding Pairs With a Certain Sum asked at Google/Amazon/Meta?

Design-style problems that combine pair sums with dynamic updates appear frequently in interviews at companies like Amazon, Google, and Meta. They test knowledge of hash maps, frequency counting, and designing efficient query operations.

What data structure is used in Finding Pairs With a Certain Sum?

A hash table (HashMap or unordered_map) is the key data structure. It stores the frequency of each value in nums2, enabling constant-time lookups when searching for complements during pair counting.

What is the time complexity of Finding Pairs With a Certain Sum?

Using the optimal HashMap design, the add operation runs in O(1) time and the count operation runs in O(n1), where n1 is the size of nums1. Space complexity is O(n2) to store frequencies of values from nums2.

Finding Pairs With a Certain Sum solution and explanation

The problem

Approach overview

Approach 1: HashMap Frequency Count

Approach 2: Two-Pointer Technique (Alternative)

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Finding Pairs With a Certain Sum solution and explanation

The problem

Approach overview

Approach 1: HashMap Frequency Count

Approach 2: Two-Pointer Technique (Alternative)

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems