LeetCode 3943 - Number of Pairs After Increment

Difficulty: 🔴 Hard
Topics: —

Solution

Problem Understanding

The problem gives two integer arrays nums1 and nums2 and a list of queries. Each query is either an increment operation on a subarray of nums2 or a pair-counting operation that asks for the number of pairs (j, k) such that nums1[j] + nums2[k] equals a target value tot.

The input arrays represent sequences of integers, with nums1 being very small (length up to 5) and nums2 potentially very large (up to 50,000 elements). Queries are mixed and can either update nums2 efficiently over a range or ask for the number of valid pairs. The output is an array of integers corresponding to each query of type 2.

Constraints hint at important considerations: nums1 is tiny, so iterating over it is cheap, whereas nums2 and the number of queries are large, so naive updates or pair-counting on the full array would be too slow. We must avoid iterating over nums2 for every query; instead, we need a structure that supports efficient range updates and frequency counting.

Important edge cases include queries that modify the entire array, queries with repeated sums, and the largest possible element values to ensure no integer overflow occurs.

Approaches

The brute-force approach simply executes each query literally: for type 1, iterate from x to y in nums2 and add val; for type 2, iterate over all elements of nums1 and nums2 and count pairs that sum to tot. This is correct but inefficient because updating or counting in nums2 is O(n) per query, leading to a potential O(q * n * m) runtime, where q is the number of queries, n = len(nums1), and m = len(nums2). With n small but m up to 50,000 and q up to 50,000, this approach is too slow.

The optimal approach exploits two key insights:

Frequency map for nums2: Instead of storing nums2 directly, maintain a frequency map of values. This allows counting pairs by checking tot - num1[j] in the map instead of iterating nums2.
Lazy range updates using a difference array: Since type 1 queries increment ranges in nums2, we can use a difference array to track increments lazily. Whenever we need the exact counts for a type 2 query, we apply the cumulative increment and count using the frequency map.

Because nums1 is very small, iterating over it in type 2 queries is negligible. The challenge is efficiently updating and maintaining the frequencies of nums2 as it is modified by the queries.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q * n * m)	O(m + n)	Update nums2 directly and count pairs each time, too slow for large nums2
Optimal	O(q * n + m + u)	O(m + u)	Use frequency map for nums2, difference array for range updates; `u` = unique elements in nums2 after increments

Algorithm Walkthrough

Initialize frequency map: Create a dictionary to store counts of each value in nums2. This allows quick lookups to count how many times a number occurs.
Prepare difference array: Create a difference array diff of length len(nums2) + 1 initialized to 0. This array allows range increments in O(1) per query.
Process each query: Iterate through all queries.

3.1. Type 1 query [1, x, y, val]: Increment diff[x] by val and decrement diff[y+1] by val. This encodes a lazy range addition.

3.2. Type 2 query [2, tot]: First, apply all pending increments from the difference array to nums2 and update the frequency map. Then, for each num in nums1, compute required = tot - num and sum freq_map.get(required, 0) to get the count of valid pairs. Append the total count to the answer list. 4. Update difference array efficiently: After processing type 2 query, reset difference array to zeros or keep track of cumulative additions, depending on implementation. 5. Return the answer array.

Why it works: The frequency map ensures that we can count the number of elements equal to a target in O(1) time per nums1 element. The difference array allows range updates without touching every element immediately, making range increments effectively O(1). Since nums1 is very small, iterating over it is cheap, guaranteeing efficiency.

Python Solution

class Solution:
    def numberOfPairs(self, nums1: list[int], nums2: list[int], queries: list[list[int]]) -> list[int]:
        from collections import Counter
        
        n2_count = Counter(nums2)
        diff = [0] * (len(nums2) + 1)
        answer = []
        
        for q in queries:
            if q[0] == 1:
                x, y, val = q[1], q[2], q[3]
                diff[x] += val
                if y + 1 < len(diff):
                    diff[y + 1] -= val
            else:
                tot = q[1]
                # Apply diff to nums2 and rebuild frequency map
                cum = 0
                n2_count.clear()
                for i in range(len(nums2)):
                    cum += diff[i]
                    nums2[i] += cum
                    n2_count[nums2[i]] += 1
                    diff[i] = 0
                diff[-1] = 0  # reset last element
                count = 0
                for num in nums1:
                    count += n2_count.get(tot - num, 0)
                answer.append(count)
        return answer

Implementation walkthrough: We maintain a Counter to track frequencies of nums2 values and a difference array diff to handle range increments lazily. For each type 2 query, we first apply all pending updates from the difference array to nums2 and rebuild the frequency map, ensuring accurate counts. Then, we compute valid pairs by checking for tot - num1[j] in the map for each element of nums1.

Go Solution

func numberOfPairs(nums1 []int, nums2 []int, queries [][]int) []int {
    answer := []int{}
    diff := make([]int, len(nums2)+1)
    freq := make(map[int]int)
    for _, num := range nums2 {
        freq[num]++
    }

    for _, q := range queries {
        if q[0] == 1 {
            x, y, val := q[1], q[2], q[3]
            diff[x] += val
            if y+1 < len(diff) {
                diff[y+1] -= val
            }
        } else {
            tot := q[1]
            cum := 0
            freq = make(map[int]int)
            for i := 0; i < len(nums2); i++ {
                cum += diff[i]
                nums2[i] += cum
                freq[nums2[i]]++
                diff[i] = 0
            }
            diff[len(diff)-1] = 0
            cnt := 0
            for _, num := range nums1 {
                cnt += freq[tot - num]
            }
            answer = append(answer, cnt)
        }
    }
    return answer
}

Go-specific notes: We use a map for frequencies similar to Python's Counter. The difference array and cumulative addition logic are identical. Slices in Go handle dynamic array access efficiently. Resetting diff ensures correctness for subsequent range updates.

Worked Examples

Example 1: nums1 = [1,2], nums2 = [3,4], queries = [[2,5],[1,0,0,2],[2,5]]

Step	Action	nums2	diff	freq_map	Count
0	Init	[3,4]	[0,0,0]	{3:1,4:1}	-
1	Query [2,5]	-	-	{3:1,4:1}	2
2	Query [1,0,0,2]	-	[2,0,0]	{3:1,4:1}	-
3	Query [2,5]	Apply diff -> [5,4]	[0,0,0]	{5:1,4:1}	1

Result: [2,1]

Example 2: nums1 = [1,1], nums2 = [2,2,3], queries = [[2,4],[1,0,1,1],[2,4]]

Step	Action	nums2	diff	freq_map	Count
0	Init	[2,2,3]	[0,0,0,