Problem 985

Abstract / Summary

Given an array and a list of update operations add each value to an element and after all updates return the sum of even numbers.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
13 lines | 381 bytes | submitted September 23, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 68% (200k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Simulation
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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:

  1. If the current element is even, its contribution is removed from s.
if nums[q[1]] % 2 == 0:
    s -= nums[q[1]]
  1. The element is updated by adding the query’s value.
nums[q[1]] += q[0]
  1. 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 s unchanged. 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 nums contains only odd numbers initially, the initial sum s is 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 s always 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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 7.5 | μ = 7.23 | σ = 1.55

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
38 links | 22 authors | 10 languages

Videos

3 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

21 solutions   September 23, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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