Sum of Even Numbers After Queries solution and explanation
9 more videos on this problem
Sum of Even Numbers After Queries-(Asked in Indeed): Explanation ➕ Live Coding 🧑🏻💻👩🏻💻codestorywithMIK · 20:07 · 9K views
LeetCode Sum of Even Numbers After Queries Solution Explained - JavaNick White · 7:14 · 5K views
LeetCode 985. Sum of Even Numbers After Queries Solution Explained - JavaNick White · 7:13 · 3K views
Leetcode 985 Sum of Even Numbers After Queries | DP Coding Decoded SDE SheetCoding Decoded · 9:40 · 838 views
Daily Leetcode #904: Sep 21, 2022 - 985. Sum of Even Numbers After QueriesProgramming Live with Larry · 6:04 · 326 views
Sum of Even Numbers After Queries | LeetCode 985 | Explained with Example | @LearnOverflowLearn Overflow · 13:35 · 261 views
985. Sum of Even Numbers After Queries "python" | LeetcodeSugar Coat · 4:20 · 196 views
Realtime Solve Leetcode 985 | Sum of Even Numbers After QueriesJie Zhou · 6:13 · 165 views
985. Sum of Even Numbers After Queries || Leetcode Medium || Array Queries || CPPKomal Pal · 12:04 · 148 views
Leetcode 985: Sum of Even Numbers After QueriesAlgorithms Casts · 12:33 · 127 views
The problem
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
Approach overview
Problem 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 1: Incremental Update Approach
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.
from typing import List
def sumEvenAfterQueries(nums: List[int], queries: List[List[int]]) -> List[int]:
even_sum = sum(num for num in nums if num % 2 == 0)
result = []
for val, index in queries:
if nums[index] % 2 == 0:
even_sum -= nums[index]
nums[index] += val
if nums[index] % 2 == 0:
even_sum += nums[index]
result.append(even_sum)
return resultclass Solution {
public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
int evenSum = 0;
for (int num : nums) {
if (num % 2 == 0) evenSum += num;
}
int[] result = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int val = queries[i][0], index = queries[i][1];
if (nums[index] % 2 == 0) evenSum -= nums[index];
nums[index] += val;
if (nums[index] % 2 == 0) evenSum += nums[index];
result[i] = evenSum;
}
return result;
}
}#include <vector>
using namespace std;
vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
int evenSum = 0;
for (int num : nums) {
if (num % 2 == 0) evenSum += num;
}
vector<int> result;
for (const auto& query : queries) {
int val = query[0], index = query[1];
if (nums[index] % 2 == 0) evenSum -= nums[index];
nums[index] += val;
if (nums[index] % 2 == 0) evenSum += nums[index];
result.push_back(evenSum);
}
return result;
}var sumEvenAfterQueries = function(nums, queries) {
let evenSum = nums.reduce((sum, num) => num % 2 === 0 ? sum + num : sum, 0);
let result = [];
for (let [val, index] of queries) {
if (nums[index] % 2 === 0) evenSum -= nums[index];
nums[index] += val;
if (nums[index] % 2 === 0) evenSum += nums[index];
result.push(evenSum);
}
return result;
};#include <stdio.h>
#include <stdlib.h>
int* sumEvenAfterQueries(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){
int evenSum = 0;
for(int i = 0; i < numsSize; i++) {
if(nums[i] % 2 == 0) evenSum += nums[i];
}
int *answer = (int*) malloc(queriesSize * sizeof(int));
for(int i = 0; i < queriesSize; i++) {
int val = queries[i][0];
int index = queries[i][1];
if(nums[index] % 2 == 0) evenSum -= nums[index];
nums[index] += val;
if(nums[index] % 2 == 0) evenSum += nums[index];
answer[i] = evenSum;
}
*returnSize = queriesSize;
return answer;
}public class Solution {
public int[] SumEvenAfterQueries(int[] nums, int[][] queries) {
int evenSum = 0;
foreach (int num in nums) {
if (num % 2 == 0) evenSum += num;
}
int[] result = new int[queries.Length];
for (int i = 0; i < queries.Length; i++) {
int val = queries[i][0], index = queries[i][1];
if (nums[index] % 2 == 0) evenSum -= nums[index];
nums[index] += val;
if (nums[index] % 2 == 0) evenSum += nums[index];
result[i] = evenSum;
}
return result;
}
}We begin by determining the sum of even elements within nums. As each query could alter this sum, we first subtract the value from evenSum if it's initially even, apply the query change, and then add the new value if it's even. Each query is processed in constant time.
Time Complexity: O(n + m), where n represents the length of nums and m the number of queries.
Space Complexity: O(m) for the output list.
Approach 2: Recompute Even Sum After Each Query
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.
from typing import List
def recomputeEvenSumAfterQueries(nums: List[int], queries: List[List[int]]) -> List[int]:
result = []
for val, index in queries:
nums[index] += val
even_sum = sum(num for num in nums if num % 2 == 0)
result.append(even_sum)
return resultclass Solution {
public int[] recomputeEvenSumAfterQueries(int[] nums, int[][] queries) {
int[] result = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
nums[queries[i][1]] += queries[i][0];
int evenSum = 0;
for (int num : nums) {
if (num % 2 == 0) evenSum += num;
}
result[i] = evenSum;
}
return result;
}
}#include <vector>
using namespace std;
vector<int> recomputeEvenSumAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
vector<int> result;
for (const auto& query : queries) {
nums[query[1]] += query[0];
int evenSum = 0;
for (int num : nums) {
if (num % 2 == 0) evenSum += num;
}
result.push_back(evenSum);
}
return result;
}var recomputeEvenSumAfterQueries = function(nums, queries) {
const result = [];
for (let [val, index] of queries) {
nums[index] += val;
const evenSum = nums.reduce((sum, num) => num % 2 === 0 ? sum + num : sum, 0);
result.push(evenSum);
}
return result;
};#include <stdio.h>
#include <stdlib.h>
int* recomputeEvenSumAfterQueries(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){
int *answer = (int*) malloc(queriesSize * sizeof(int));
for(int i = 0; i < queriesSize; i++) {
int val = queries[i][0];
int index = queries[i][1];
nums[index] += val;
int evenSum = 0;
for(int j = 0; j < numsSize; j++) {
if(nums[j] % 2 == 0) evenSum += nums[j];
}
answer[i] = evenSum;
}
*returnSize = queriesSize;
return answer;
}public class Solution {
public int[] RecomputeEvenSumAfterQueries(int[] nums, int[][] queries) {
int[] result = new int[queries.Length];
for (int i = 0; i < queries.Length; i++) {
nums[queries[i][1]] += queries[i][0];
int evenSum = 0;
foreach (int num in nums) {
if (num % 2 == 0) evenSum += num;
}
result[i] = evenSum;
}
return result;
}
}Each query updates the indexed position and the re-evaluated sum of even numbers is computed again by iterating over nums. While functionally simple, this lacks efficiency compared to an incremental update approach.
Time Complexity: O(n * m), involving a recalculation loop of length n for m queries.
Space Complexity: O(m), from the list of results.
Approach 3: Simulation
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).
function sumEvenAfterQueries(nums: number[], queries: number[][]): number[] {
let s = nums.reduce((acc, x) => acc + (x % 2 === 0 ? x : 0), 0);
const ans: number[] = [];
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;
}func sumEvenAfterQueries(nums []int, queries [][]int) (ans []int) {
s := 0
for _, x := range nums {
if x%2 == 0 {
s += x
}
}
for _, q := range queries {
v, i := q[0], q[1]
if nums[i]%2 == 0 {
s -= nums[i]
}
nums[i] += v
if nums[i]%2 == 0 {
s += nums[i]
}
ans = append(ans, s)
}
return
}impl Solution {
pub fn sum_even_after_queries(mut nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
let mut s: i32 = nums.iter().filter(|&x| x % 2 == 0).sum();
let mut ans = Vec::with_capacity(queries.len());
for query in queries {
let (v, i) = (query[0], query[1] as usize);
if nums[i] % 2 == 0 {
s -= nums[i];
}
nums[i] += v;
if nums[i] % 2 == 0 {
s += nums[i];
}
ans.push(s);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Incremental Update Approach | Time Complexity: O(n + m), where n represents the length of nums and m the number of queries. |
| Recompute Even Sum After Each Query | Time Complexity: O(n * m), involving a recalculation loop of length n for m queries. |
| Simulation | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Sum of Even Numbers After Queries easy or hard?
The problem is rated Medium on LeetCode. The difficulty comes from recognizing that recomputing the even sum after every query is inefficient and that a running sum can be updated in constant time.
Sum of Even Numbers After Queries Python/Java solution
Both Python and Java implementations follow the same logic: compute the initial even sum, process each query, adjust the sum based on parity changes, and store the result after each query. The algorithm runs in O(n + q) time and O(1) extra space.
How to solve Sum of Even Numbers After Queries in O(n)?
Compute the initial sum of even numbers in O(n). For each query, check the current value at the index, subtract it from the even sum if it is even, apply the update, and add the new value if it becomes even. Each query takes constant time, making the total complexity O(n + q).
What is the best approach for Sum of Even Numbers After Queries?
The incremental update approach is the optimal solution. Instead of recomputing the sum after every query, maintain a running sum of even numbers. Before applying a query, remove the previous value from the sum if it was even, update the element, then add it back if the new value is even. This reduces the complexity to O(n + q).
Is Sum of Even Numbers After Queries asked at Google/Amazon/Meta?
Array update and running-sum problems similar to this appear in interviews at companies like Amazon, Google, and Meta. The problem tests whether you can maintain derived values efficiently instead of recomputing them after every operation.
What data structure is used in Sum of Even Numbers After Queries?
The primary data structure is a simple array. The optimization relies on maintaining a running integer variable that stores the current sum of even numbers. No additional complex data structures are required.
What is the time complexity of Sum of Even Numbers After Queries?
The optimal solution runs in O(n + q) time, where n is the array size and q is the number of queries. The initial even sum takes O(n), and each query update takes O(1) time. A naive approach that recomputes the even sum after every query would take O(n * q).