Skip to main content
Talentd

Finding Pairs With a Certain Sum - Solution & Explanation

MediumArrayHash TableDesign24 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

Problem Statement

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

  1. Add a positive integer to an element of a given index in the array nums2.
  2. 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 <= 105
  • 1 <= nums1[i] <= 109
  • 1 <= nums2[i] <= 105
  • 0 <= index < nums2.length
  • 1 <= val <= 105
  • 1 <= tot <= 109
  • 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.

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.

Code

PythonJavaC++CJavaScriptC#

Python

Java

C++

C

JavaScript

C#

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.

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.

Code

PythonJava

Python

Java

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.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap Frequency CountAdd: 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

Video Solution

Finding Pairs With a Certain Sum | Simple Explanation | Leetcode 1865 | codestorywithMIK • codestorywithMIK • 7,368 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Finding Pairs With a Certain Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Number of Pairs With Absolute Difference K

Next

Count the Number of Fair Pairs