#985

Medium

LeetCode Problem Workspace

Sum of Even Numbers After Queries

Efficiently update an integer array based on queries and compute the sum of even numbers after each modification using simulation.

array simulation

Problem Statement

You are given an integer array nums and an array queries where each query is a pair [vali, indexi]. For each query, add vali to nums[indexi] and then determine the sum of all even numbers currently in nums.

Return an array of integers answer where answer[i] represents the sum of even numbers in nums after performing the i-th query. Ensure your solution handles large arrays efficiently without recalculating the sum from scratch for each query.

Examples

Example 1

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

Output: [8,6,2,4]

At the beginning, the array is [1,2,3,4]. After adding 1 to nums[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8. After adding -3 to nums[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6. After adding -4 to nums[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2. After adding 2 to nums[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

Example 2

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

Output: [0]

Example details omitted.

Constraints

1 <= nums.length <= 104
-104 <= nums[i] <= 104
1 <= queries.length <= 104
-104 <= vali <= 104
0 <= indexi < nums.length

Solution Approach

Initialize Even Sum

Compute the initial sum of even numbers in nums before processing any queries. This sets a baseline that can be incrementally updated.

Process Queries Incrementally

For each query, first remove the current value at nums[indexi] from the even sum if it is even. Then, update nums[indexi] by adding vali, and if the new value is even, add it back to the running even sum.

Record Results

After each query adjustment, append the current even sum to the result array. This ensures each step reflects the correct sum without full recomputation.

Complexity Analysis

Metric	Value
Time	O(N+Q)
Space	O(Q)

The algorithm visits each element once to compute the initial sum, then processes Q queries with constant-time updates per query, resulting in O(N + Q) time. The space for the result array is O(Q).

What Interviewers Usually Probe

Look for an approach that avoids recomputing the sum after each query.
Expect recognition of the Array plus Simulation pattern and its incremental nature.
Check for correct handling of negative numbers and zero when updating even sums.

Common Pitfalls or Variants

Common pitfalls

Recomputing the sum of even numbers from scratch after each query, causing TLE.
Failing to remove the old value from the sum before updating an element.
Not correctly identifying whether a value is even after the update, leading to wrong sums.

Follow-up variants

Sum of odd numbers after queries using the same incremental update technique.
Counting numbers divisible by k after each query instead of even numbers.
Tracking both even and odd sums simultaneously after each query for multi-condition updates.

FAQ

What is the key pattern to solve Sum of Even Numbers After Queries efficiently?

The problem follows the Array plus Simulation pattern, where incremental updates to a running even sum avoid full recomputation.

Why is recalculating the sum from scratch after each query inefficient?

Recomputing the sum for each query results in O(N*Q) time complexity, which exceeds limits for large arrays and queries.

How do negative numbers affect the sum updates?

Negative numbers can change an element from even to odd or vice versa, so the running sum must be adjusted carefully after each update.

Can this approach be adapted to other conditions besides even numbers?

Yes, the incremental update strategy works for any condition that can be checked per element, like odd numbers or multiples of k.

What is the space complexity of the solution?

The space complexity is O(Q) due to storing the result array of sums after each query, with minimal additional overhead.

terminal

Solution

Solution 1: Simulation

We use an integer variable $\textit{s}$ to record the sum of all even numbers in the array $\textit{nums}$. Initially, $\textit{s}$ is the sum of all even numbers in the array $\textit{nums}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def sumEvenAfterQueries(
        self, nums: List[int], queries: List[List[int]]
    ) -> List[int]:
        s = sum(x for x in nums if x % 2 == 0)
        ans = []
        for v, i in queries:
            if nums[i] % 2 == 0:
                s -= nums[i]
            nums[i] += v
            if nums[i] % 2 == 0:
                s += nums[i]
            ans.append(s)
        return ans

Continue Practicing

#999 available captures for rook #950 reveal cards in increasing order #946 validate stack sequences