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] <= 1041 <= queries.length <= 104-104 <= vali <= 1040 <= indexi < nums.lengthProblem 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.
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.
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.
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.
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.
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).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Incremental Update Approach | Time Complexity: O(n + m), where n is the length of nums and m is the number of queries. |
| Recompute Even Sum After Each Query | Time Complexity: O(n * m), as the even sum is recalculated n times for each query m. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recompute Even Sum After Each Query | O(n * q) | O(1) | Useful as a baseline or when constraints are small and implementation simplicity matters |
| Incremental Update Approach | O(n + q) | O(1) | Best for large inputs where frequent updates occur and recomputation would be too slow |
Sum of Even Numbers After Queries-(Asked in Indeed): Explanation ➕ Live Coding 🧑🏻💻👩🏻💻 • codestorywithMIK • 8,636 views views
Watch 9 more video solutions →Practice Sum of Even Numbers After Queries with our built-in code editor and test cases.
Practice on FleetCode