Finding Pairs With a Certain Sum - Practice Coding Problems

Finding Pairs With a Certain Sum - Problem

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

Add: Add a positive integer to an element at a given index in the array nums2.

Count: Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value (where 0 <= i < nums1.length and 0 <= j < nums2.length).

Implement the FindSumPairs class:

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

Input & Output

Example 1 — Basic Operations

$ Input: nums1 = [1,1,2,2,2,3], nums2 = [1,4,5,2,5,4], operations = [["count",7],["add",1,2],["count",8],["count",4],["add",2,1],["count",5]]

› Output: [8,2,1,1]

💡 Note: count(7): pairs (0,2),(0,4),(1,2),(1,4),(2,1),(2,3),(4,1),(4,3) = 8 pairs. add(1,2): nums2[1] = 4+2 = 6. count(8): pairs (2,1),(4,1) = 2 pairs. count(4): pair (2,0) = 1 pair.

Example 2 — Simple Case

$ Input: nums1 = [1,2], nums2 = [3,4], operations = [["count",5],["add",0,1],["count",6]]

› Output: [2,2]

💡 Note: count(5): pairs (0,1) and (1,0) where 1+4=5 and 2+3=5. add(0,1): nums2[0] = 3+1 = 4. count(6): pairs (0,1) and (1,0) where 1+5=6 and 2+4=6.

Example 3 — No Pairs Found

$ Input: nums1 = [1,2], nums2 = [5,6], operations = [["count",3],["add",0,2],["count",5]]

› Output: [0,0]

💡 Note: count(3): no pairs sum to 3. add(0,2): nums2[0] = 5+2 = 7. count(5): still no pairs sum to 5.

Constraints

1 ≤ nums1.length ≤ 1000
1 ≤ nums2.length ≤ 10⁵
1 ≤ nums1[i] ≤ 10⁹
1 ≤ nums2[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays and sequence of operations

Process

Count pairs that sum to target, update nums2 values

Output

Results from count operations only

Key Takeaway

🎯 Key Insight: Use frequency maps to avoid recounting - store nums1 frequencies once, update nums2 frequencies dynamically

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use frequency maps to avoid recounting identical elements. Store nums1 frequencies once, maintain nums2 frequencies that update on add operations. Best approach uses frequency counting for O(unique nums1 elements) count queries. Time: O(n) per count, Space: O(n+m)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs Every Time	O(n×m)	O(1)	For each count query, iterate through all possible pairs
Frequency Count Optimization	O(n)	O(n+m)	Use hash maps to store element frequencies for faster counting

Brute Force - Check All Pairs Every Time — Algorithm Steps

Store nums1 and nums2 as-is
For add: update nums2[index] directly
For count: double loop through both arrays

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Arrays

Keep nums1 and nums2 as-is

Count Query

Check every nums1[i] + nums2[j] against target

Add Operation

Update nums2[index] directly

Code -

solution.c — C

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

typedef struct {
    int* nums1;
    int nums1Size;
    int* nums2;
    int nums2Size;
} FindSumPairs;

FindSumPairs* findSumPairsCreate(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    FindSumPairs* obj = (FindSumPairs*)malloc(sizeof(FindSumPairs));
    obj->nums1 = nums1;
    obj->nums1Size = nums1Size;
    obj->nums2 = nums2;
    obj->nums2Size = nums2Size;
    return obj;
}

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

int findSumPairsCount(FindSumPairs* obj, int tot) {
    int count = 0;
    for (int i = 0; i < obj->nums1Size; i++) {
        for (int j = 0; j < obj->nums2Size; j++) {
            if (obj->nums1[i] + obj->nums2[j] == tot) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    // Simplified implementation
    int nums1[] = {1, 1, 2, 2, 2, 3};
    int nums2[] = {1, 4, 5, 2, 5, 4};
    
    FindSumPairs* obj = findSumPairsCreate(nums1, 6, nums2, 6);
    
    printf("[%d,", findSumPairsCount(obj, 7));
    findSumPairsAdd(obj, 1, 2);
    printf("%d,", findSumPairsCount(obj, 8));
    printf("%d]\n", findSumPairsCount(obj, 4));
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Each count query requires checking all n×m pairs

✓ Linear Growth

Space Complexity

O(1)

Only storing the input arrays, no extra data structures

✓ Linear Space

18.6K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs Every Time — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler