Finding Pairs With a Certain Sum - Video Solutions

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.