Scale Engineer

Finding Pairs With a Certain Sum

Med
#1704Time: - **Constructor**: O(1) (or O(L1 + L2) if copying arrays). - **`add`**: O(1). - **`count`**: O(L1 * L2), where L1 and L2 are the lengths of `nums1` and `nums2` respectively. This is the bottleneck.Space: O(1), as we only store references to the input arrays. If we make copies, it would be O(L1 + L2).2 companies
Patterns
Design
Data structures
ArrayHash Table
Companies
DatabricksQuora

Prompt

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:

,5,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.

Approaches

2 approaches with complexity analysis and trade-offs.

This is the most straightforward approach where we directly translate the problem statement into code. We keep the original arrays and, for each count query, we iterate through all possible pairs from nums1 and nums2 to see how many of them sum up to the target value tot.

Algorithm

  • Constructor FindSumPairs(nums1, nums2): Store references to the input arrays nums1 and nums2.
  • add(index, val): Directly update the value in the nums2 array at the given index: nums2[index] += val.
  • count(tot):
    1. Initialize a counter pairCount to 0.
    2. Use nested loops to iterate through every possible pair of elements (nums1[i], nums2[j]).
    3. For each pair, check if their sum equals tot.
    4. If nums1[i] + nums2[j] == tot, increment pairCount.
    5. After checking all pairs, return pairCount.

Walkthrough

In this approach, the FindSumPairs class holds the two arrays. The add operation is very simple and efficient, as it only involves updating an element in nums2 at a specific index. The main drawback is the count method. It employs a nested loop structure: the outer loop goes through each element of nums1, and for each of these, the inner loop goes through every element of nums2. This exhaustive check of all pairs makes the count operation computationally expensive, especially with the given constraints where nums2 can be very large.

class FindSumPairs {    private int[] nums1;    private int[] nums2;     public FindSumPairs(int[] nums1, int[] nums2) {        this.nums1 = nums1;        this.nums2 = nums2;    }     public void add(int index, int val) {        nums2[index] += val;    }     public int count(int tot) {        int pairCount = 0;        for (int num1 : nums1) {            for (int num2 : nums2) {                if (num1 + num2 == tot) {                    pairCount++;                }            }        }        return pairCount;    }}

Complexity

Time

- **Constructor**: O(1) (or O(L1 + L2) if copying arrays). - **`add`**: O(1). - **`count`**: O(L1 * L2), where L1 and L2 are the lengths of `nums1` and `nums2` respectively. This is the bottleneck.

Space

O(1), as we only store references to the input arrays. If we make copies, it would be O(L1 + L2).

Trade-offs

Pros

  • Very simple to understand and implement.

  • The add operation is extremely fast, taking constant time.

  • Requires minimal extra space.

Cons

  • The count operation is extremely slow, with a time complexity of O(L1 * L2). Given the problem constraints (L1 up to 1000, L2 up to 10^5), this will result in a 'Time Limit Exceeded' error on most platforms.

Solutions

public class FindSumPairs { private int [] nums1 ; private int [] nums2 ; private Dictionary < int , int > cnt = new Dictionary < int , int >(); public FindSumPairs ( int [] nums1 , int [] nums2 ) { this . nums1 = nums1 ; this . nums2 = nums2 ; foreach ( int x in nums2 ) { if ( cnt . ContainsKey ( x )) { cnt [ x ]++; } else { cnt [ x ] = 1 ; } } } public void Add ( int index , int val ) { int oldVal = nums2 [ index ]; if ( cnt . TryGetValue ( oldVal , out int oldCount )) { if ( oldCount == 1 ) { cnt . Remove ( oldVal ); } else { cnt [ oldVal ] = oldCount - 1 ; } } nums2 [ index ] += val ; int newVal = nums2 [ index ]; if ( cnt . TryGetValue ( newVal , out int newCount )) { cnt [ newVal ] = newCount + 1 ; } else { cnt [ newVal ] = 1 ; } } public int Count ( int tot ) { int ans = 0 ; foreach ( int x in nums1 ) { int target = tot - x ; if ( cnt . TryGetValue ( target , out int count )) { ans += count ; } } return ans ; } } /** * Your FindSumPairs object will be instantiated and called as such: * FindSumPairs obj = new FindSumPairs(nums1, nums2); * obj.Add(index,val); * int param_2 = obj.Count(tot); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem