LeetCode 985: Sum of Even Numbers After Queries

Problem Restatement

We are given an integer array nums and an array queries.

Each query has the form:

[val, index]

For each query, we update the array:

nums[index] = nums[index] + val

After that update, we need to record the sum of all even values in nums.

Return an array where each element is the even-number sum after the corresponding query.

Each query permanently changes nums. The next query uses the modified array. The problem statement defines each query as [val_i, index_i] and asks for the sum of even values after applying that update.

Input and Output

Function shape:

def sumEvenAfterQueries(nums: list[int], queries: list[list[int]]) -> list[int]:
    ...

Examples

Example 1:

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

Initial even values are:

2 + 4 = 6

Process each query:

Answer:

[8, 6, 2, 4]

First Thought: Recompute the Sum Each Time

The direct approach is simple.

For every query:

1. Update the target element.
2. Scan the full array.
3. Add up all even numbers.
4. Store the result.

class Solution:
    def sumEvenAfterQueries(
        self,
        nums: list[int],
        queries: list[list[int]],
    ) -> list[int]:
        answer = []

        for val, index in queries:
            nums[index] += val

            even_sum = 0
            for num in nums:
                if num % 2 == 0:
                    even_sum += num

            answer.append(even_sum)

        return answer

This is correct, but it repeats unnecessary work.

Problem With Recomputing

Each query changes only one element.

If nums has n elements and there are q queries, rescanning the whole array after every query costs:

O(n * q)

We can do better by maintaining the sum of even values as a running value.

Key Insight

Only one number changes per query.

So the even sum can only change because of that one number.

Before updating nums[index]:

• If it is even, remove its old value from the running sum.
• If it is odd, it contributes nothing.

Then apply the update.

After updating nums[index]:

• If it is even, add its new value to the running sum.
• If it is odd, it contributes nothing.

This gives O(1) work per query.

Algorithm

First compute:

even_sum = sum(num for num in nums if num % 2 == 0)

Then process each query [val, index].

For each query:

1. If nums[index] is even, subtract it from even_sum.
2. Add val to nums[index].
3. If the new nums[index] is even, add it to even_sum.
4. Append even_sum to the answer.

Correctness

At the start, even_sum is the sum of all even values in nums.

For each query, only nums[index] changes. All other elements keep the same parity and value, so their contribution to the even sum stays unchanged.

If the old value at nums[index] is even, the algorithm subtracts it before the update. This removes its old contribution. If the old value is odd, it contributed nothing, so no subtraction is needed.

After the update, if the new value is even, the algorithm adds it. This includes its new contribution. If the new value is odd, it contributes nothing.

Therefore, after each query, even_sum equals the sum of all even values in the updated array. The algorithm appends this value after every query, so the returned array is correct.

Complexity

Let n = len(nums) and q = len(queries).

Ignoring the output array, the extra space is O(1).

Implementation

class Solution:
    def sumEvenAfterQueries(
        self,
        nums: list[int],
        queries: list[list[int]],
    ) -> list[int]:
        even_sum = 0

        for num in nums:
            if num % 2 == 0:
                even_sum += num

        answer = []

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

            nums[index] += val

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

            answer.append(even_sum)

        return answer

Code Explanation

We first compute the sum of all even values:

even_sum = 0

for num in nums:
    if num % 2 == 0:
        even_sum += num

Then we process each query:

for val, index in queries:

Before changing the value, remove its old contribution if it is even:

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

Then apply the query:

nums[index] += val

After the update, add the new contribution if the value is even:

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

Finally, store the current even sum:

answer.append(even_sum)

Testing

def run_tests():
    s = Solution()

    assert s.sumEvenAfterQueries(
        [1, 2, 3, 4],
        [[1, 0], [-3, 1], [-4, 0], [2, 3]],
    ) == [8, 6, 2, 4]

    assert s.sumEvenAfterQueries(
        [1],
        [[4, 0]],
    ) == []

    assert s.sumEvenAfterQueries(
        [2],
        [[1, 0], [1, 0]],
    ) == [0, 4]

    assert s.sumEvenAfterQueries(
        [0, 0],
        [[1, 0], [2, 1], [-1, 0]],
    ) == [0, 2, 2]

    print("all tests passed")

run_tests()