Abstract / Summary

Given a list of integers, find the minimum number of changes needed to make the list special as defined by specific conditions.

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 46% (300k+ submissions).

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 defines a method that determines, for each query interval, whether the sub-array satisfies a specific parity condition. The condition requires that every element, when added to its index, shares the same parity across the interval. The solution builds a prefix structure that captures the parity of each element-index sum, then evaluates each query in constant time using that structure. The method returns a generator that yields a Boolean result for each query.

Core Logic

Building the Prefix Parity Array

The first phase constructs a running total of how many positions in the original array produce an odd result for (value + index).

prefix = [0]
for i, n in enumerate(nums):
    prefix.append(prefix[-1] + ((n + i) & 1))

• enumerate(nums) supplies both the index i and the element n.
• (n + i) & 1 extracts the least-significant bit, effectively computing the parity (odd = 1, even = 0) without invoking a modulo operation.
• Each new entry in prefix accumulates the count of odd parities up to the current position, so prefix[k] holds the number of odd results among the first k elements.

Evaluating Queries

For every pair [a, b] in queries, the method extracts the count of odd parities inside the interval [a, b] and compares it to the interval length.

for a, b in queries:
    parity = prefix[b + 1] - prefix[a]
    length = b + 1 - a
    yield parity == 0 or parity == length

• prefix[b + 1] - prefix[a] gives the exact number of odd results between indices a and b inclusive.
• length is the total number of elements in the interval.
• The expression parity == 0 or parity == length evaluates to True when either all summed values are even (parity == 0) or all are odd (parity == length). The generator yields this Boolean for each query.

Edge Cases Handled

When the input array nums is empty, the prefix list contains only the initial zero. Any query loop will simply not execute, resulting in an empty generator, which is a valid outcome.

If a query references a single element (a == b), the interval length is one. The parity count will be either zero or one, making the condition true regardless of the element’s value, which aligns with the definition that a one-element interval trivially satisfies the “all same parity” rule.

Queries that span the entire array are also covered because the prefix array was built with an extra leading zero, allowing the subtraction prefix[b + 1] - prefix[a] to correctly compute the total odd count from the start to the end.

The implementation assumes that each query provides valid indices (0 ≤ a ≤ b < len(nums)). Within those bounds, the arithmetic never accesses out-of-range positions thanks to the extra sentinel element in prefix.

Performance Optimizations

The solution leverages a prefix-sum technique, turning each query into a constant-time operation after a single linear pass over the input array. This eliminates the need for repeated scanning of sub-arrays.

Bitwise masking with & 1 replaces the more expensive modulo operator for parity checks, yielding faster execution on typical CPUs.

Using enumerate avoids an explicit index variable, streamlining the loop that builds the prefix array.

Finally, the method returns a generator via yield rather than constructing a list of Boolean results. This lazy evaluation reduces memory consumption, especially when the number of queries is large, because results are produced on demand.

Imagine a long row of numbered blocks, where some are odd and some are even. A special row is one where every neighbor is different from the one next to it. That means an even number must stand next to an odd number, and then an odd number must stand next to an even one, like a pattern of colors.

To check if a row is special, a list is built first for counting patterns. This list looks at each block and marks it based on whether its number matches its spot in line. By doing this, it becomes very easy to see if a section of the row keeps that perfect back and forth pattern. When a question is asked about a specific part of the row, the code looks at this list to see if the pattern stays unbroken from the start to the finish of that section. If the count of patterns matches, it means the whole section follows the rule, and that tells us the row is special.

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		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				C++
	Shamik07			Dart
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	C++
Shamik07	Dart

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