Watch 10 video solutions for Sum of Even Numbers After Queries, a medium level problem involving Array, Simulation. This walkthrough by codestorywithMIK has 8,636 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |