Given an integer array and a list of queries, where each query contains a value and an index, update the array element at the specified index by adding the given value. After each update, return the sum of all even numbers present in the array.

Approach: A straightforward approach would recalculate the sum of all even numbers after every query, resulting in unnecessary repeated traversal of the array.

The optimized solution first computes the initial sum of all even numbers in the array. For each query, if the current value at the target index is even, it is removed from the sum before updating the element. After applying the update, if the new value becomes even, it is added back to the sum. The updated even sum is stored as the result for that query.

This approach avoids rescanning the entire array for every update and significantly improves performance.

Java Solution:

import java.util.Arrays;

public class SumOfEvenNumbersAfterQueries {

    public static int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
        int evenSum = 0;

        for (int number : nums) {
            if (number % 2 == 0) {
                evenSum += number;
            }
        }

        int[] result = new int[queries.length];

        for (int queryIndex = 0; queryIndex < queries.length; queryIndex++) {
            int valueToAdd = queries[queryIndex][0];
            int targetIndex = queries[queryIndex][1];

            if (nums[targetIndex] % 2 == 0) {
                evenSum -= nums[targetIndex];
            }

            nums[targetIndex] += valueToAdd;

            if (nums[targetIndex] % 2 == 0) {
                evenSum += nums[targetIndex];
            }

            result[queryIndex] = evenSum;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        int[][] queries = {
                {1, 0},
                {-3, 1},
                {-4, 0},
                {2, 3}
        };

        int[] result = sumEvenAfterQueries(nums, queries);

        System.out.println(Arrays.toString(result));
    }
}

Output: [8, 6, 2, 4]

Time Complexity: O(n + q), where n is the size of the array and q is the number of queries. The array is traversed once to calculate the initial even sum, and each query is processed in constant time.

Space Complexity: O(q), as an output array is required to store the even sum after each query.

Key Interview Points: • Recomputing the even sum after every query leads to O(n × q) complexity and is inefficient for large inputs. • Maintaining a running even sum allows each query to be processed in O(1) time. • This problem tests understanding of incremental updates and optimization techniques commonly used in real-world systems handling frequent data modifications.