Skip to main content
Talentd

Sum of Even Numbers After Queries - Solution & Explanation

MediumArraySimulation20 min readAsked at: Indeed
Practice this problem

Problem Statement

You are given an integer array nums and an array queries where queries[i] = [vali, indexi].

For each query i, first, apply nums[indexi] = nums[indexi] + vali, 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 1:

Input: nums = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation: 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]

 

Constraints:

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

Approach Overview

Problem Overview: You are given an integer array nums and a list of queries. Each query adds a value to an index in the array. After applying every query, you must return the sum of all even numbers in the updated array. The challenge is avoiding recomputation of the even sum after every modification.

Approach 1: Recompute Even Sum After Each Query (Time: O(n * q), Space: O(1))

The straightforward solution applies each query and then scans the entire array to recompute the sum of even numbers. After updating nums[index] += val, iterate through the array and add every even element to a running total. This uses simple iteration and works well for small inputs. The downside is performance: if there are q queries and n elements, you perform a full scan after every update, leading to O(n * q) time. This approach is useful as a baseline because it mirrors the literal problem statement and demonstrates the core array manipulation.

Approach 2: Incremental Update Approach (Time: O(n + q), Space: O(1))

The optimized solution maintains the current sum of even numbers and updates it incrementally as queries modify the array. Start by computing the initial even sum in O(n). For each query, check the element at the target index before modification. If it is even, subtract it from the running sum because the value will change. Apply the update nums[i] += val, then check the new value. If the updated number is even, add it back to the sum. Each query only performs a few constant-time checks and arithmetic operations, so processing all queries takes O(q) time. This pattern is common in simulation problems where you track a derived metric instead of recomputing it from scratch.

The key insight: only one element changes per query. Instead of recomputing the entire even sum, adjust the running total based on how that single element's parity changes. If the value transitions from even to odd, remove it. If it transitions from odd to even, add it. If parity stays the same, update accordingly.

Recommended for interviews: Interviewers expect the incremental update solution with O(n + q) time and O(1) space. Starting with the recomputation approach shows you understand the mechanics of the problem, but optimizing with a running even sum demonstrates awareness of state tracking and efficient array updates under repeated queries.

Approach 1: Incremental Update Approach

In this approach, we will maintain a running sum of even numbers. For each query, before updating the number at the given index, we check if it's even and subtract it from our running total if it is. After updating, we check if the new number is even and add it to the total if it is. This method avoids recalculating the sum of all even numbers from scratch after each query, thus optimizing the solution.

We first calculate the initial sum of even numbers. For each query, if the number at the query index in nums is even, we subtract it from the evenSum. We then apply the query change and check if the new number is even. If so, add it to the evenSum. This way, each query is processed in constant time.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), where n is the length of nums and m is the number of queries.
Space Complexity: O(1), as we use only constant extra space.

Try this approach in the editor →

Approach 2: Recompute Even Sum After Each Query

This approach calculates the sum of even numbers from scratch after each query. Though straightforward, it may not be the most efficient, as it recalculates the sum fully rather than in an incremental manner.

Each query is independently processed by updating the indicated index and recalculating the entire array's evenSum afterward. While direct, this method lacks the efficiency of the first approach as every query starts with a new sum computation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), as the even sum is recalculated n times for each query m.
Space Complexity: O(1), aside from the storage for results.

Try this approach in the editor →

Approach 3: Simulation

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

For each query (v, i), we first check if nums[i] is even. If nums[i] is even, we subtract nums[i] from s. Then, we add v to nums[i]. If nums[i] is even, we add nums[i] to s, and then add s to the answer array.

The time complexity is O(n + m), where n and m are the lengths of the arrays nums and queries, respectively. Ignoring the space consumption of the answer array, the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Incremental Update Approach

Time Complexity: O(n + m), where n is the length of nums and m is the number of queries.
Space Complexity: O(1), as we use only constant extra space.

Recompute Even Sum After Each Query

Time Complexity: O(n * m), as the even sum is recalculated n times for each query m.
Space Complexity: O(1), aside from the storage for results.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recompute Even Sum After Each QueryO(n * q)O(1)Useful as a baseline or when constraints are small and implementation simplicity matters
Incremental Update ApproachO(n + q)O(1)Best for large inputs where frequent updates occur and recomputation would be too slow

Video Solution

Sum of Even Numbers After Queries-(Asked in Indeed): Explanation ➕ Live Coding 🧑🏻‍💻👩🏻‍💻 • codestorywithMIK • 9,714 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sum of Even Numbers After Queries easy or hard?
The problem is rated Medium on LeetCode. The difficulty comes from recognizing that recomputing the even sum after every query is inefficient and that a running sum can be updated in constant time.
Sum of Even Numbers After Queries Python/Java solution
Both Python and Java implementations follow the same logic: compute the initial even sum, process each query, adjust the sum based on parity changes, and store the result after each query. The algorithm runs in O(n + q) time and O(1) extra space.
How to solve Sum of Even Numbers After Queries in O(n)?
Compute the initial sum of even numbers in O(n). For each query, check the current value at the index, subtract it from the even sum if it is even, apply the update, and add the new value if it becomes even. Each query takes constant time, making the total complexity O(n + q).
What is the best approach for Sum of Even Numbers After Queries?
The incremental update approach is the optimal solution. Instead of recomputing the sum after every query, maintain a running sum of even numbers. Before applying a query, remove the previous value from the sum if it was even, update the element, then add it back if the new value is even. This reduces the complexity to O(n + q).
Is Sum of Even Numbers After Queries asked at Google/Amazon/Meta?
Array update and running-sum problems similar to this appear in interviews at companies like Amazon, Google, and Meta. The problem tests whether you can maintain derived values efficiently instead of recomputing them after every operation.
What data structure is used in Sum of Even Numbers After Queries?
The primary data structure is a simple array. The optimization relies on maintaining a running integer variable that stores the current sum of even numbers. No additional complex data structures are required.
What is the time complexity of Sum of Even Numbers After Queries?
The optimal solution runs in O(n + q) time, where n is the array size and q is the number of queries. The initial even sum takes O(n), and each query update takes O(1) time. A naive approach that recomputes the even sum after every query would take O(n * q).

Ready to solve this problem?

Practice Sum of Even Numbers After Queries with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays