Abstract / Summary

Find the longest subarray where the sum of even numbers minus sum of odd numbers is at least a given value.

Note

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

This problem is ranked as

and has an acceptance rate of about 32% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Sliding Window

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.

Overview

The provided implementation computes the length of the longest contiguous sub-array that satisfies two constraints: every element must be less than or equal to a given threshold and the parity of the elements must follow an alternating pattern starting with an even number. The algorithm iterates over possible left boundaries, expands each candidate sub-array to the right while the constraints hold, and keeps track of the maximum length found.

Key Steps

The outer loop selects each index as a potential start of a valid sub-array.

for left in range(len(nums)):
    if nums[left] > threshold or nums[left] % 2 != 0:
        continue

If the element at left violates either the threshold or the required even parity, the iteration skips to the next index because no alternating sub-array can begin there.

When a viable start is found, the inner logic initializes a length counter and a flag that indicates the expected parity for the next element.

length = 1
expect = 1   # expect odd next (pattern 0,1,0,1,…)

The inner loop walks forward from left + 1, checking each candidate element against the two constraints.

for right in range(left + 1, len(nums)):
    if nums[right] > threshold or nums[right] % 2 != expect:
        break
    length += 1
    expect ^= 1

If an element exceeds the threshold or does not match the expected parity, the expansion stops. Otherwise the length grows and the expected parity toggles using a bitwise XOR, which efficiently flips between 0 (even) and 1 (odd).

After the inner loop finishes, the current sub-array length is compared with the best result seen so far.

result = max(result, length)

Finally, the method returns the maximum length discovered.

return result

Edge Cases Handled

The code explicitly checks the first element of each candidate sub-array for both the threshold and parity condition, ensuring that sub-arrays that start with an odd number or a value above the threshold are never considered. This guards against cases where the input begins with an invalid element, such as [7, 2, 4] with a low threshold, or where a single element satisfies the constraints but the next element does not, e.g., [2, 5, 4]. The inner loop’s break condition stops the expansion precisely at the point where either constraint fails, so a sub-array that meets the criteria up to a certain index is correctly measured without including the violating element.

When the input list is empty, the outer loop does not execute and the initial result of 0 is returned, correctly representing that no valid sub-array exists. If all elements are valid and already alternate in parity, the inner loop will traverse the entire remainder of the list, yielding the full length as the result.

Performance Optimizations

The implementation uses a simple nested loop structure, but it incorporates a few micro-optimizations. The parity expectation is stored in a single integer variable expect and toggled with the XOR operator (expect ^= 1). This avoids conditional branches for parity checking and provides a fast, branch-free update. The early continue in the outer loop eliminates unnecessary inner-loop work for positions that cannot start a valid sub-array, reducing the number of expansions performed. The comment about adjusting the variable left hints at a possible skip-ahead technique, but even without it the current approach avoids redundant checks by breaking out of the inner loop as soon as a violation is detected, preventing further unnecessary comparisons for that start index. The use of max to update the result ensures a single comparison per outer iteration, keeping the overhead minimal.

Imagine a long line of numbered building blocks sitting on the floor. Some blocks are even numbers and some are odd numbers. There is a rule that says if a block is too big or it is an odd number, we cannot play with it at the start.

To begin, look at every block one by one to see if it is a good starting block. If a block is small and even, it is a perfect place to start a game. Once a block is picked, look at the next block in the line to see if it follows the pattern. The pattern is just bouncing back and forth between even and odd, so if the first block was even, the next one must be odd, then the next must be even again.

Keep looking at the next block as long as it is small enough and the pattern stays perfect. Every time a new block fits the pattern, the count of blocks being used grows bigger. If a block is too big or breaks the pattern of switching between even and odd, the game stops for that specific starting block. Keep track of the longest line of blocks found during the whole process. By the time every possible starting block has been checked, the biggest number recorded is the answer.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
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

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	Java			C++		Python	TS
	WalkCCC	Java			C++		Python
	leetcode.ca	Java			C++	Go	Python	TS
	Progiez	Java			C++		Python
github	charles-wangkai	Java
	everthis			JS
	fsq		Rust
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	Rust
varunu28	Java

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