Python 0985.py
class Solution:
def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]:
s = sum(n for n in nums if n % 2 == 0)
for q in queries:
if nums[q[1]] % 2 == 0:
s -= nums[q[1]]
nums[q[1]] += q[0]
if nums[q[1]] % 2 == 0:
s += nums[q[1]]
yield s
Difficulty
and has an acceptance rate of about 68% (200k+ submissions).
Typical patterns to solve this problem:
- Array
- Simulation
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a Solution class with a method sumEvenAfterQueries. The method receives an integer list nums and a list of query pairs queries. Each query consists of a value to add and an index in nums. After applying each query, the method yields the sum of all even numbers currently present in nums. The algorithm maintains this sum incrementally, avoiding a full recomputation after every update.
Core Logic
The first significant step computes the initial sum of even elements in nums.
s = sum(n for n in nums if n % 2 == 0)
By iterating once over the input list, the variable s holds the baseline even-sum that will be adjusted as queries are processed.
The method then iterates over each query in queries. For each query q, the code extracts the addition value q[0] and the target index q[1]. The handling of the element at the target index follows a three-phase pattern:
- If the current element is even, its contribution is removed from
s.
if nums[q[1]] % 2 == 0:
s -= nums[q[1]]
- The element is updated by adding the query’s value.
nums[q[1]] += q[0]
- If the updated element is even, its new value is added back to
s.
if nums[q[1]] % 2 == 0:
s += nums[q[1]]
Finally, the method yields the current even-sum after each query.
yield s
Because yield is used, the method returns a generator that produces a sequence of results lazily, which can be consumed by the caller as an iterator.
Edge-Case Handling
The algorithm gracefully handles several edge conditions without explicit branching:
-
When the target element is odd before the update, the first conditional block does nothing, leaving
sunchanged. The subsequent addition and parity check correctly decide whether the new value should be incorporated. -
When the addition value is zero, the element’s parity does not change, and the code correctly retains the previous contribution to
s. -
If the list
numscontains only odd numbers initially, the initial sumsis zero. The subsequent logic still correctly adds any newly created even numbers after updates. -
Queries that reference the same index multiple times are handled naturally; each iteration recomputes the contribution based on the element’s current state, ensuring that
salways reflects the latest even-sum.
Performance Optimizations
The primary optimization is the incremental maintenance of the even sum. By adjusting s only for the element that changes, the algorithm avoids recomputing the sum of the entire list after each query, which would be costly for large inputs.
The use of a generator (yield) further reduces memory overhead. Instead of constructing an intermediate list containing all results, the method produces each result on demand, allowing the caller to process the sequence without storing the entire output at once.
The parity checks (% 2 == 0) are inexpensive integer operations, and the conditional branches are executed only for the element affected by the current query, keeping the per-query work minimal.
Overall, the design achieves a tight loop where each query incurs a constant amount of work, leading to efficient execution even when the number of queries is large.
ELI5 - Simplified Explanation
Imagine a long row of numbered toy boxes. Some boxes have even numbers written on them, like two, four, or six, and others have odd numbers. First, all the even numbers are added together to find a special total sum.
There is a list of tasks to perform on these boxes. Each task has two parts. The first part tells how much to change the number inside one specific box, and the second part tells which box to pick. When a number inside a box changes, it might become even or it might become odd.
Before changing the number, the box is checked. If it was already an even number, that amount is taken away from the total sum because it is about to change. Then the number inside the box is updated by adding the new amount. After the number changes, the box is checked one more time. If the new number is even, it gets added back into the total sum. This makes sure the total sum always knows exactly what all the even numbers are, even as the boxes change one by one.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||
| www | AlgoMonster | C++ | Java | Python | TS | ||||||
| WalkCCC | C++ | Java | Python | ||||||||
| leetcode.ca | C++ | Java | Python | JS | C# | Go | Rust | TS | |||
| LeetcodeHelp | C++ | Java | Python | ||||||||
| Progiez | C++ | Java | Python | ||||||||
| github | BigEggStudy | C# | |||||||||
| black-shadows | C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JS | ||||||||||
| fartem | Ruby | ||||||||||
| fpdjsns | C++ | ||||||||||
| fsq | C++ | ||||||||||
| Garvit244 | Python | ||||||||||
| halfrost | Go | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JS | ||||||||||
| lkwq007 | Python | ||||||||||
| lzl124631x | C++ | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| vthwang | Java | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript | ||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JavaScript | ||||||||||
| fartem | Ruby | ||||||||||
| fpdjsns | C++ | ||||||||||
| fsq | C++ | ||||||||||
| Garvit244 | Python | ||||||||||
| halfrost | Go | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| lkwq007 | Python | ||||||||||
| lzl124631x | C++ | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| vthwang | Java |
Videos
Solved On The Same Day
- problem 680: Valid Palindrome II
- problem 478: Generate Random Point in a Circle
- problem 497: Random Point in Non-overlapping Rectangles
- problem 519: Random Flip Matrix
- problem 581: Shortest Unsorted Continuous Subarray
- problem 659: Split Array into Consecutive Subsequences
- problem 738: Monotone Increasing Digits
- problem 743: Network Delay Time
- problem 769: Max Chunks To Make Sorted
- problem 1048: Longest String Chain
- problem 1094: Car Pooling
- problem 1324: Print Words Vertically
- problem 1680: Concatenation of Consecutive Binary Numbers
- problem 1823: Find the Winner of the Circular Game
- problem 1860: Incremental Memory Leak
- problem 1922: Count Good Numbers
- problem 2487: Remove Nodes From Linked List
- problem 381: Insert Delete GetRandom O(1) - Duplicates allowed
- problem 517: Super Washing Machines
- problem 632: Smallest Range Covering Elements from K Lists
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality