LeetCode 985 - Sum of Even Numbers After Queries

LeetCode Problem 985

Difficulty: 🟡 Medium
Topics: Array, Simulation

Solution

Problem Understanding

The problem gives us an integer array nums and a list of update operations called queries. Each query contains two values:

• vali, the amount to add
• indexi, the position in the array to update

For every query, we must first update the array element:

nums[indexi] = nums[indexi] + vali

After applying the update, we must compute the sum of all even numbers currently present in the array. The result after each query is stored in the output array.

The important detail is that queries are processed sequentially. Each update permanently changes the array before the next query begins.

For example, if the array starts as:

[1,2,3,4]

the initial sum of even numbers is:

2 + 4 = 6

If a query changes nums[0] from 1 to 2, the even sum becomes:

2 + 2 + 4 = 8

The constraints tell us that both the array length and the number of queries can be as large as 10^4. A straightforward solution that recomputes the even sum from scratch after every query would require scanning the whole array each time, which could lead to roughly:

10^4 * 10^4 = 10^8

operations in the worst case. That is unnecessarily expensive for a problem that only changes one element per query.

Several edge cases are important:

• A number can change from odd to even
• A number can change from even to odd
• Negative even numbers still count toward the sum
• Adding zero still requires correct handling
• The array may contain only one element
• Queries may repeatedly modify the same index

The key observation is that each query affects only one array element, so we should update the even sum incrementally instead of recomputing it entirely.

Approaches

Brute Force Approach

The brute-force solution directly simulates the problem statement.

For each query:

1. Update the specified element.
2. Traverse the entire array.
3. Add up all even values.
4. Store the result.

This approach is easy to understand and guaranteed to produce the correct answer because it literally follows the problem definition after every update.

However, its performance is poor. If there are q queries and the array has length n, then every query requires scanning all n elements. The total complexity becomes O(n * q).

With both values potentially reaching 10^4, this can become too slow compared to a more optimized approach.

Optimal Incremental Update Approach

The important insight is that every query modifies only one element in the array.

Instead of recalculating the entire even sum after every update, we can maintain the current sum of even numbers dynamically.

The process works like this:

• Keep a running variable even_sum

• Before updating an element:

• If the old value is even, remove it from even_sum

• Apply the update

• After updating:

• If the new value is even, add it to even_sum

This works because only one number changes during each query. Every other array element remains unchanged, so their contribution to the even sum stays the same.

As a result, each query is processed in constant time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × q)	O(1)	Recomputes the even sum after every query
Optimal	O(n + q)	O(1) extra	Maintains the even sum incrementally

Algorithm Walkthrough

1. Start by computing the initial sum of all even numbers in nums.

This gives us a baseline that represents the current even-number contribution in the array. 2. Create an empty result array.

We will append the even sum after each query is processed. 3. Process each query one at a time.

Each query contains:

• value, the amount to add
• index, the array position to modify

4. Before modifying the element, check whether the current value is even.

If nums[index] is even, it currently contributes to the even sum. Since the value is about to change, we must remove its old contribution first. 5. Apply the update.

Update the array element using:

nums[index] += value

6. After the update, check whether the new value is even.

If the updated number is even, it now contributes to the even sum, so add it back. 7. Append the current even_sum to the answer array.

This represents the sum of all even numbers after processing the current query. 8. Continue until all queries are processed. 9. Return the answer array.

Why it works

The algorithm maintains an invariant:

even_sum always equals the sum of all even numbers currently in nums

Before each update, we remove the old value if it was contributing to the sum. After the update, we add the new value if it should contribute.

Since only one array element changes per query, updating the running total is sufficient to maintain correctness without rescanning the entire array.

Python Solution

from typing import List

class Solution:
    def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        even_sum = sum(num for num in nums if num % 2 == 0)

        answer = []

        for value, index in queries:
            # Remove old contribution if current value is even
            if nums[index] % 2 == 0:
                even_sum -= nums[index]

            # Apply the update
            nums[index] += value

            # Add new contribution if updated value is even
            if nums[index] % 2 == 0:
                even_sum += nums[index]

            answer.append(even_sum)

        return answer

The implementation begins by computing the initial sum of all even numbers in the array. This preprocessing step requires one pass through nums.

The variable even_sum is then maintained throughout the entire algorithm. Instead of recomputing the sum after every query, the code adjusts this value incrementally.

Inside the loop, the code first checks whether the current number at the target index is even. If it is, that number is currently contributing to the total even sum, so it must be removed before the update occurs.

The array element is then updated in place.

After the update, the code checks whether the new value is even. If so, it contributes to the running total and is added back into even_sum.

Finally, the updated even sum is appended to the result list.

This implementation exactly follows the invariant described earlier and processes every query in constant time.

Go Solution

func sumEvenAfterQueries(nums []int, queries [][]int) []int {
    evenSum := 0

    // Compute initial even sum
    for _, num := range nums {
        if num%2 == 0 {
            evenSum += num
        }
    }

    result := make([]int, 0, len(queries))

    for _, query := range queries {
        value := query[0]
        index := query[1]

        // Remove old contribution if current value is even
        if nums[index]%2 == 0 {
            evenSum -= nums[index]
        }

        // Apply update
        nums[index] += value

        // Add new contribution if updated value is even
        if nums[index]%2 == 0 {
            evenSum += nums[index]
        }

        result = append(result, evenSum)
    }

    return result
}

The Go implementation follows exactly the same logic as the Python version.

A slice named result is preallocated with capacity equal to the number of queries, which avoids unnecessary reallocations during appends.

Go integers are sufficient for the given constraints, so there is no overflow concern here. The algorithm uses direct slice indexing and in-place updates exactly like the Python solution.

Worked Examples

Example 1

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

Initial even numbers:

2 + 4 = 6

So:

even_sum = 6

Step	Query	Updated nums	even_sum	Output
Initial	-	[1,2,3,4]	6	-
1	[1,0]	[2,2,3,4]	8	8
2	[-3,1]	[2,-1,3,4]	6	6
3	[-4,0]	[-2,-1,3,4]	2	2
4	[2,3]	[-2,-1,3,6]	4	4

Final answer:

[8,6,2,4]

Example 2

Input:
nums = [1]
queries = [[4,0]]

Initial even sum:

0

Process the query:

Step	Query	Updated nums	even_sum	Output
Initial	-	[1]	0	-
1	[4,0]	[5]	0	0

Final answer:

[0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + q)	One pass to compute initial even sum, then O(1) work per query
Space	O(1) extra	Only a few variables are used besides the output array

The algorithm performs a single traversal of the input array to compute the initial even sum. After that, each query only updates one array element and adjusts the running total using constant-time operations.

No additional data structures proportional to input size are needed beyond the required output array.

Test Cases

from typing import List

class Solution:
    def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        even_sum = sum(num for num in nums if num % 2 == 0)

        answer = []

        for value, index in queries:
            if nums[index] % 2 == 0:
                even_sum -= nums[index]

            nums[index] += value

            if nums[index] % 2 == 0:
                even_sum += nums[index]

            answer.append(even_sum)

        return answer

sol = Solution()

# Example 1 from the problem statement
assert sol.sumEvenAfterQueries(
    [1,2,3,4],
    [[1,0],[-3,1],[-4,0],[2,3]]
) == [8,6,2,4]

# Example 2 from the problem statement
assert sol.sumEvenAfterQueries(
    [1],
    [[4,0]]
) == [0]

# Single even element becoming odd
assert sol.sumEvenAfterQueries(
    [2],
    [[1,0]]
) == [0]

# Single odd element becoming even
assert sol.sumEvenAfterQueries(
    [1],
    [[1,0]]
) == [2]

# Negative even numbers
assert sol.sumEvenAfterQueries(
    [-2,-4],
    [[1,0],[2,1]]
) == [-4,-2]

# Multiple updates to same index
assert sol.sumEvenAfterQueries(
    [2,2],
    [[1,0],[1,0],[2,0]]
) == [2,4,6]

# All numbers always odd
assert sol.sumEvenAfterQueries(
    [1,3,5],
    [[2,0],[2,1],[2,2]]
) == [3,8,15]

# No effective change
assert sol.sumEvenAfterQueries(
    [2,4],
    [[0,0],[0,1]]
) == [6,6]

# Large negative transition
assert sol.sumEvenAfterQueries(
    [10],
    [[-20,0]]
) == [-10]

Test	Why
[1,2,3,4] with mixed queries	Validates the main example and all parity transitions
[1] with [4,0]	Single-element edge case
[2] becoming odd	Ensures removal from even sum works
[1] becoming even	Ensures addition into even sum works
Negative even values	Confirms negative evens are included correctly
Repeated updates on same index	Tests state consistency across updates
All odd becoming even	Validates multiple odd-to-even transitions
Updates with zero	Ensures unchanged values are handled correctly
Large negative update	Confirms negative even sums are valid

Edge Cases

One important edge case occurs when a number changes from even to odd. This is easy to mishandle if the old value is not removed before the update. For example, if 4 becomes 5, the even sum must decrease by 4. The implementation handles this correctly by subtracting the old value before modifying the array.

Another important case occurs when a number changes from odd to even. In this situation, the updated value must be added into the running total after the update. The implementation explicitly checks the updated value and adds it if it is even.

Negative numbers can also introduce subtle bugs. Even though a number is negative, it still counts as even if divisible by 2. For example, -2 and -4 must both contribute to the sum. The implementation uses the modulo operation directly, so negative even values are processed correctly.

A final edge case is repeated updates to the same index. Since the array is modified in place, every query depends on the result of previous queries. The implementation correctly maintains the updated state of nums throughout the entire process, ensuring later operations use the latest values.