Abstract / Summary

Find the longest subsequence in an array where each element is at least double the previous one.

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 47% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

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 Solution.maximumLength method receives a list of integers and determines the greatest possible length of a subsequence that satisfies one of four simple parity patterns. By collapsing each integer to its least-significant bit, the algorithm reduces the problem to a binary sequence where only the values 0 (even) and 1 (odd) matter. It then evaluates two alternating patterns-starting with 0 or with 1-and two uniform patterns-entirely 0s or entirely 1s-returning the largest count among them.

Key Steps

The first operation normalizes the input list to a binary representation that captures the parity of each element.

size = len(nums)
for i in range(size):
    nums[i] &= 1

By applying the bitwise AND with 1, each entry is replaced by 0 for even numbers and 1 for odd numbers. This in-place transformation eliminates the need for an auxiliary array and keeps memory usage minimal.

The core of the alternating-parity evaluation is encapsulated in the nested odd function. It walks through the binary list, counting how many elements can be taken while flipping the expected target after each successful match.

def odd(target):
    best = 0
    for n in nums:
        if n == target:
            best   += 1
            target ^= 1
    return best

The variable target represents the parity that the next element of the subsequence must have. When a matching element is found, the count best is incremented and target is toggled using XOR with 1, thereby preparing for the opposite parity on the following iteration.

Two uniform-parity counts are derived directly from the transformed list.

even1 = sum(nums)            # count of 1s (odd numbers)
even0 = size - even1         # count of 0s (even numbers)

sum(nums) efficiently aggregates the number of 1s because the list now contains only 0s and 1s. Subtracting this total from the original size yields the count of 0s without a second pass.

Finally, the method selects the maximum length among the four candidate patterns.

return max(odd(0), odd(1), even0, even1)

Calling odd(0) evaluates the longest alternating sequence that begins with an even element, while odd(1) does the same for a sequence that starts with an odd element. The uniform counts even0 and even1 represent the lengths of subsequences consisting solely of evens or solely of odds, respectively.

Edge Cases Handled

When the input list is empty, size becomes 0. The loop that masks bits does not execute, even1 evaluates to 0, even0 also becomes 0, and both calls to odd return 0 because the inner loop has no elements to process. Consequently, max receives four zeros and returns 0, correctly indicating that no subsequence exists.

If the list contains a single element, the masking step reduces it to either 0 or 1. The odd function will count that element as a valid start of an alternating sequence, yielding a length of 1. The uniform counts will also be 1 for the matching parity and 0 for the opposite parity. The final max therefore returns 1, reflecting the fact that a single element forms the longest possible subsequence.

For a list composed entirely of evens (all 0s after masking), even0 equals the list length, even1 is 0, and both odd calls will produce a length of 1 because the alternating pattern can only pick the first element before the required parity flips to 1, which never appears. The max function thus selects the uniform even count, delivering the full length of the list.

Conversely, a list of all odds (all 1s) mirrors the previous case: even1 equals the list length, even0 is 0, and the alternating evaluations again yield 1. The method correctly returns the full length via the uniform odd count.

When the list already alternates perfectly, such as [0,1,0,1,…] or [1,0,1,0,…], the odd function starting with the appropriate target will traverse the entire list, incrementing best on each step and toggling target accordingly. The resulting length equals the list size, and the final max reflects this optimal alternating subsequence.

Performance Optimizations

The algorithm achieves high efficiency through several deliberate choices. The initial parity reduction modifies the original list in place, avoiding allocation of a secondary array and reducing memory pressure. Using a bitwise AND (&= 1) is a constant-time operation that directly extracts the needed information without conditional branching.

Counting the number of odd elements with sum(nums) leverages Python’s built-in aggregation, which is implemented in C and therefore faster than a manual Python loop. Deriving the even count by subtraction eliminates the need for a second traversal.

The odd function performs a single linear scan while maintaining only two integer variables (best and target). The XOR toggle (target ^= 1) is a compact, branch-free way to flip between 0 and 1, contributing to predictable execution flow.

Overall, the solution runs in linear time relative to the input size, with a constant amount of extra space beyond the input list itself. The combination of in-place transformation, built-in aggregation, and minimal state tracking yields a concise and performant implementation.

Imagine you have a long row of building blocks, and each block is either a zero or a one. The goal is to make the longest possible chain of blocks where the numbers alternate between zero and one, or where they all stay the same.

First, the code looks at every block and checks if it is odd or even. If a number is odd, it changes it to a one. If it is even, it changes it to a zero. This simplifies everything down to just two types of blocks.

After that, there are a few different ways to build a chain. One way is to start with a zero and look for a one, then a zero, then a one, and so on. Another way is to start with a one and look for a zero, then a one, then a zero. The code counts how long those perfect switching chains can be.

There are also two other simple ways to build a chain. You can pick out only the zeros and put them all together, or pick out only the ones and put them all together. These chains do not switch back and forth at all, they just stick to the same number.

Finally, the code compares all of these different chains to see which one has the most blocks, and then it shares the length of that longest chain.

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

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

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

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