Problem Description

You are given an integer array nums and an array queries where each queries[i] = [val, index]. For each query, you are to add val to nums[index] and then record the sum of the even numbers in nums after the update.

Return an array of the answers to each query, in the same order as the queries.

• Each query is applied in order, modifying the array in-place.
• Your output should be an array where the i-th element is the sum of even numbers in nums after applying the i-th query.
• Constraints: The length of nums and queries can be up to 10⁴.

Key Points:

• After each query, immediately compute the sum of all even numbers in nums.
• Each query only modifies one element in nums.
• Efficient updating is important due to potentially large input size.

Thought Process

At first glance, we might think to process each query by updating the relevant element in nums and then scanning the entire array to sum the even numbers. However, this approach is inefficient because it would require O(n) time per query, leading to O(n*q) total time for n elements and q queries. With large inputs, this quickly becomes too slow.

To optimize, we notice that each query only changes one value in the array. The only way the sum of even numbers changes is if the updated value was even before, or becomes even after. This means we don't need to rescan the whole array; we can keep a running total of the sum of evens and update it intelligently after each query.

By focusing only on the changed element, we can make our solution much more efficient.

Solution Approach

We'll follow these steps:

1. Initialize: Compute the initial sum of even numbers in nums and store it in a variable, say even_sum.
2. Process Each Query: For each query [val, index]:
   • If nums[index] is even before the update, subtract it from even_sum (since it may change to odd after the update).
   • Add val to nums[index].
   • If nums[index] is even after the update, add it back to even_sum (it is now an even number contributing to the sum).
   • Append the current even_sum to the result array.
3. Return: After processing all queries, return the result array.

This approach ensures we only ever touch one element per query and keep the sum updated efficiently.

Example Walkthrough

Input:

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

Step-by-step:

1. Initial even sum: 2 + 4 = 6
2. Query 1: [1,0]
   Add 1 to nums[0] (1+1=2, which is even).
   nums becomes [2,2,3,4].
   Before: nums[0]=1 (odd), after: nums[0]=2 (even).
   Add 2 to even_sum: 6 + 2 = 8.
   Append 8 to result.
3. Query 2: [-3,1]
   Add -3 to nums[1] (2-3=-1, which is odd).
   nums becomes [2,-1,3,4].
   Before: nums[1]=2 (even), subtract 2 from even_sum: 8-2=6.
   After: nums[1]=-1 (odd), do nothing.
   Append 6 to result.
4. Query 3: [-4,0]
   Add -4 to nums[0] (2-4=-2, which is even).
   nums becomes [-2,-1,3,4].
   Before: nums[0]=2 (even), subtract 2 from even_sum: 6-2=4.
   After: nums[0]=-2 (even), add -2 to even_sum: 4+(-2)=2.
   Append 2 to result.
5. Query 4: [2,3]
   Add 2 to nums[3] (4+2=6, which is even).
   nums becomes [-2,-1,3,6].
   Before: nums[3]=4 (even), subtract 4 from even_sum: 2-4=-2.
   After: nums[3]=6 (even), add 6 to even_sum: -2+6=4.
   Append 4 to result.

Time and Space Complexity

Brute-force approach:

• For each query, scan the entire array to sum the even numbers.
• Time complexity: O(q * n), where q = number of queries, n = size of nums.
• Space complexity: O(1) extra (not counting output).

• Initial sum: O(n) to compute sum of even numbers in nums.
• Each query: O(1) time (constant work per query).
• Total time: O(n + q).
• Space complexity: O(1) extra (output array is required for the answer).

The optimized approach is much more efficient, especially for large inputs.

Summary

We tackled the "Sum of Even Numbers After Queries" problem by recognizing that only the changed element in each query can affect the sum of even numbers. By keeping a running total and updating it smartly based on whether the updated element is even or odd before and after the change, we reduced the time complexity from O(n*q) to O(n+q). This makes the solution efficient and elegant, suitable for large input sizes.

Code Implementation

class Solution:
    def sumEvenAfterQueries(self, nums, queries):
        even_sum = sum(x for x in nums if x % 2 == 0)
        result = []
        for val, idx in queries:
            if nums[idx] % 2 == 0:
                even_sum -= nums[idx]
            nums[idx] += val
            if nums[idx] % 2 == 0:
                even_sum += nums[idx]
            result.append(even_sum)
        return result
      

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        int even_sum = 0;
        for (int x : nums) {
            if (x % 2 == 0) even_sum += x;
        }
        vector<int> result;
        for (const auto& q : queries) {
            int val = q[0], idx = q[1];
            if (nums[idx] % 2 == 0) even_sum -= nums[idx];
            nums[idx] += val;
            if (nums[idx] % 2 == 0) even_sum += nums[idx];
            result.push_back(even_sum);
        }
        return result;
    }
};
      

class Solution {
    public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
        int evenSum = 0;
        for (int x : nums) {
            if (x % 2 == 0) evenSum += x;
        }
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int val = queries[i][0], idx = queries[i][1];
            if (nums[idx] % 2 == 0) evenSum -= nums[idx];
            nums[idx] += val;
            if (nums[idx] % 2 == 0) evenSum += nums[idx];
            result[i] = evenSum;
        }
        return result;
    }
}
      

var sumEvenAfterQueries = function(nums, queries) {
    let evenSum = nums.reduce((acc, x) => x % 2 === 0 ? acc + x : acc, 0);
    let result = [];
    for (let [val, idx] of queries) {
        if (nums[idx] % 2 === 0) evenSum -= nums[idx];
        nums[idx] += val;
        if (nums[idx] % 2 === 0) evenSum += nums[idx];
        result.push(evenSum);
    }
    return result;
};