Sum of Even Numbers After Queries
MedPrompt
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.length
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. For each query, it first updates the element in the nums array and then iterates through the entire modified array to calculate the sum of all even numbers. This process is repeated for every single query.
Algorithm
- Initialize an integer array
answerwith the same length asqueries. - Iterate through each query
[val, index]fromi = 0toqueries.length - 1. - Update the
numsarray:nums[index] = nums[index] + val. - Initialize a variable
currentEvenSum = 0. - Iterate through each number
numin thenumsarray. - If
numis even (num % 2 == 0), add it tocurrentEvenSum. - After the inner loop, store the result:
answer[i] = currentEvenSum. - Return the
answerarray after the outer loop finishes.
Walkthrough
The core idea is to treat each query independently. We loop through the queries array. Inside the loop, for a given query [val, index], we first perform the update nums[index] += val. After the update, we initialize a temporary sum variable to zero. We then loop through all elements of the nums array. For each element, we check if it's even using the modulo operator (%). If it is, we add its value to our temporary sum. Once this inner loop is complete, the temporary sum holds the total sum of even numbers for the current state of the array, which we then store in our result array. This is straightforward but inefficient because we repeatedly scan the entire nums array.
class Solution { public int[] sumEvenAfterQueries(int[] nums, int[][] queries) { int[] answer = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int val = queries[i][0]; int index = queries[i][1]; // Apply the query nums[index] += val; // Calculate the sum of even numbers int currentEvenSum = 0; for (int num : nums) { if (num % 2 == 0) { currentEvenSum += num; } } // Store the result for this query answer[i] = currentEvenSum; } return answer; }}Complexity
Time
O(N * Q), where N is the length of `nums` and Q is the length of `queries`. For each of the Q queries, we iterate through all N elements of the `nums` array to calculate the sum.
Space
O(Q) or O(1). We need an array of size Q to store the answers. If the output array is not considered extra space, the space complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem statement.
Cons
Inefficient for large inputs, as it performs a lot of redundant calculations.
Likely to result in a 'Time Limit Exceeded' error on platforms with strict time limits.
A more efficient approach is to avoid recalculating the sum from scratch for each query. Instead, we can pre-calculate the initial sum of even numbers in the nums array. Then, for each query, we intelligently update this sum based on the change made to the array, which takes constant time.
Algorithm
- Initialize a variable
evenSum = 0. - Iterate through the initial
numsarray. If a number is even, add it toevenSum. - Initialize an integer array
answerwith the same length asqueries. - Iterate through each query
[val, index]fromi = 0toqueries.length - 1. - Store the original value:
oldVal = nums[index]. - If
oldValis even, subtract it fromevenSum:evenSum -= oldVal. - Calculate the new value:
newVal = oldVal + val. - Update the array:
nums[index] = newVal. - If
newValis even, add it toevenSum:evenSum += newVal. - Store the updated sum in the result array:
answer[i] = evenSum. - Return the
answerarray.
Walkthrough
First, we iterate through the initial nums array once to compute the sum of all its even numbers. Let's call this evenSum. Then, we process the queries one by one. For each query [val, index], we look at the value at nums[index] before the update. Let's call it oldVal.
If oldVal is even, it was part of our evenSum, so we subtract it.
Next, we calculate the new value, newVal = oldVal + val, and update the array: nums[index] = newVal.
Now, we check if this newVal is even. If it is, we add it to our evenSum.
After adjusting evenSum, we store its current value as the answer for this query. This way, each query is processed in constant time, leading to a much faster overall solution.
class Solution { public int[] sumEvenAfterQueries(int[] nums, int[][] queries) { int[] answer = new int[queries.length]; // 1. Calculate the initial sum of even numbers int evenSum = 0; for (int num : nums) { if (num % 2 == 0) { evenSum += num; } } // 2. Process each query for (int i = 0; i < queries.length; i++) { int val = queries[i][0]; int index = queries[i][1]; // Get the original value int oldVal = nums[index]; // If the original value was even, subtract it from the sum if (oldVal % 2 == 0) { evenSum -= oldVal; } // Update the number in the array int newVal = oldVal + val; nums[index] = newVal; // If the new value is even, add it to the sum if (newVal % 2 == 0) { evenSum += newVal; } // Store the current even sum as the answer for this query answer[i] = evenSum; } return answer; }}Complexity
Time
O(N + Q), where N is the length of `nums` and Q is the length of `queries`. The initial sum calculation takes O(N) time. Then, each of the Q queries is processed in O(1) constant time.
Space
O(Q) or O(1). We need an array of size Q to store the answers. If the output array is not considered extra space, the space complexity is O(1) as we only use a few extra variables.
Trade-offs
Pros
Highly efficient and optimal for the given constraints.
Avoids redundant computations by updating the sum incrementally.
Cons
Slightly more complex logic than the brute-force approach due to tracking the running sum.
Solutions
Solution
public class Solution { public int [] SumEvenAfterQueries ( int [] nums , int [][] queries ) { int s = nums . Where ( x => x % 2 == 0 ). Sum (); int [] ans = new int [ queries . Length ]; for ( int j = 0 ; j < queries . Length ; j ++) { int v = queries [ j ][ 0 ], i = queries [ j ][ 1 ]; if ( nums [ i ] % 2 == 0 ) { s -= nums [ i ]; } nums [ i ] += v ; if ( nums [ i ] % 2 == 0 ) { s += nums [ i ]; } ans [ j ] = s ; } return ans ; } }class Solution { public int [] sumEvenAfterQueries ( int [] nums , int [][] queries ) { int s = 0 ; for ( int x : nums ) { if ( x % 2 == 0 ) { s += x ; } } int m = queries . length ; int [] ans = new int [ m ]; int k = 0 ; for ( var q : queries ) { int v = q [ 0 ], i = q [ 1 ]; if ( nums [ i ] % 2 == 0 ) { s -= nums [ i ]; } nums [ i ] += v ; if ( nums [ i ] % 2 == 0 ) { s += nums [ i ]; } ans [ k ++] = s ; } return ans ; } }/** * @param {number[]} nums * @param {number[][]} queries * @return {number[]} */ var sumEvenAfterQueries = function (nums, queries) { let s = 0; for (const x of nums) { if (x % 2 === 0) { s += x; } } const ans = []; for (const [v, i] of queries) { if (nums[i] % 2 === 0) { s -= nums[i]; } nums[i] += v; if (nums[i] % 2 === 0) { s += nums[i]; } ans.push(s); } return ans; };class Solution { public: vector < int > sumEvenAfterQueries ( vector < int >& nums , vector < vector < int >>& queries ) { int s = 0 ; for ( int x : nums ) { if ( x % 2 == 0 ) { s += x ; } } vector < int > ans ; for ( auto & q : queries ) { int v = q [ 0 ], i = q [ 1 ]; if ( nums [ i ] % 2 == 0 ) { s -= nums [ i ]; } nums [ i ] += v ; if ( nums [ i ] % 2 == 0 ) { s += nums [ i ]; } ans . push_back ( s ); } return ans ; } };class Solution : def sumEvenAfterQueries ( self , nums : List [ int ], queries : List [ List [ int ]] ) -> List [ int ]: s = sum ( x for x in nums if x % 2 == 0 ) ans = [] for v , i in queries : if nums [ i ] % 2 == 0 : s -= nums [ i ] nums [ i ] += v if nums [ i ] % 2 == 0 : s += nums [ i ] ans . append ( s ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.