985 - Sum of Even Numbers After Queries

Difficulty: Medium | Pattern: Running Sum | Company tags: Amazon, Google

Problem Statement

You have an integer array nums and an array queries where queries[i] = [val, index].

For each query i, first, apply nums[index] += val, then print the sum of the even values of nums.

Return an integer array answer where answer[i] is the answer to the ith query.

Example:

Input: nums = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]

Algorithm Flow

Approach: Maintain Running Even Sum — O(n + q), O(q)

Key insight: Instead of recomputing even sum each query, maintain a running even_sum. Per query:

1. If nums[index] is currently even, subtract it from even_sum.
2. Apply update.
3. If nums[index] is now even, add it to even_sum.

def sumEvenAfterQueries(nums: list[int], queries: list[list[int]]) -> list[int]:
    even_sum = sum(x for x in nums if x % 2 == 0)
    result = []
    
    for val, idx in queries:
        if nums[idx] % 2 == 0:
            even_sum -= nums[idx]  # remove old even value
        nums[idx] += val
        if nums[idx] % 2 == 0:
            even_sum += nums[idx]  # add new even value
        result.append(even_sum)
    
    return result

Dry Run

nums = [1,2,3,4], initial even_sum = 2+4 = 6

query	nums[idx] before	action	nums after	even_sum	result
[1,0]	1 (odd)	add 1, now 2(even) +2	[2,2,3,4]	8	8
[-3,1]	2 (even)	-2, add -3, now -1(odd)	[2,-1,3,4]	6	6
[-4,0]	2 (even)	-2, add -4, now -2(even) +(-2)	[-2,-1,3,4]	2	2
[2,3]	4 (even)	-4, add 2, now 6(even) +6	[-2,-1,3,6]	4	4

Result: [8,6,2,4] ✓

Complexity

• Time: O(n + q) — O(n) initial sum, O(1) per query
• Space: O(q) for result array

Key Terms

Term	Definition
Running sum	An aggregate maintained incrementally rather than recomputed from scratch each query.
Delta update	Adjusting an aggregate by removing the old contribution of a changed element before adding its new contribution.
Parity check	Testing x % 2 == 0 to classify a number as even or odd.
Online query processing	Answering each query immediately using current state, without needing future queries.
Amortized O(1) per operation	Each query does constant work because the aggregate is updated incrementally instead of rescanned.

FAQ

1. Can this be solved without extra space? The result array of size q is required by the problem's output; beyond that, only O(1) extra space (the running sum) is needed.
2. What if nums is empty? even_sum starts at 0, and any query would need a valid index — the problem guarantees indices are valid for the given array.
3. How would this change if we needed the sum of odd numbers instead? Flip the parity check in both the subtract and add steps — same delta-update pattern.
4. What if queries could target the same index many times? No change needed — the delta-update pattern naturally handles repeated updates to the same index correctly.
5. Could this be solved by recomputing the even sum every query? Yes, but that costs O(n) per query (O(n×q) total) versus O(1) per query with the running-sum approach — a significant difference for large inputs.

Quick Revision

• Precompute even_sum as the sum of all even numbers in nums.
• For each query (val, idx): if nums[idx] is currently even, subtract it from even_sum.
• Apply the update: nums[idx] += val.
• If nums[idx] is now even, add it back to even_sum.
• Append the current even_sum to the result list after each query.
• Avoids recomputation — each query is O(1) instead of O(n).
• Time O(n + q), space O(q) for the output.
• Pattern: maintain a running aggregate with incremental delta updates instead of full recomputation.

Related Problems

• 303 - Range Sum Query - Immutable
• 307 - Range Sum Query - Mutable
• 238 - Product of Array Except Self