Abstract / Summary

Count the number of contiguous subarrays where each pair of adjacent elements have opposite parity.

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 57% (80k+ submissions).

Typical patterns to solve this problem:

• Array
• Math

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 computes the total number of contiguous subarrays whose elements strictly alternate between two values. It processes the input list in a single forward pass, maintaining a running count of the length of the current alternating segment and aggregating the contribution of each position to the final answer.

Key Steps

Initialization

result = 1
length = 1

Two integer variables are created before the loop starts. result holds the cumulative number of alternating subarrays discovered so far, while length records the length of the most recent alternating segment that ends at the current element. Both start at one because a single element by itself always forms a valid alternating subarray.

Pairwise Traversal

for a, b in zip(nums, nums[1:]):

The loop iterates over adjacent pairs of elements from the input list. By zipping the original list with a slice that skips the first element, the code obtains each consecutive pair (a, b) without explicit index arithmetic. This approach reduces overhead and keeps the loop body concise.

Updating the Segment Length

length = 1 if a == b else length + 1

When the two elements of the current pair are equal, the alternating property breaks, and the length of the current segment is reset to one (the new element starts a fresh segment). If the elements differ, the alternating segment extends, and length is incremented by one.

Accumulating the Result

result += length

After adjusting length, its value is added to result. The intuition is that a segment of length k ending at the current position contributes exactly k new alternating subarrays: each subarray that ends at this position and starts anywhere within the segment.

Returning the Answer

return result

When the loop finishes, result contains the total count of alternating subarrays for the entire input list, and it is returned to the caller.

Edge Cases Handled

The algorithm naturally accommodates several boundary conditions:

• Single-element input - The initialization sets result and length to one, and the loop body is never entered, so the method correctly returns one, reflecting the sole subarray consisting of that element.

• All elements identical - Each pair comparison yields equality, causing length to be reset to one on every iteration. Consequently, result grows by exactly one for each additional element, which matches the fact that only the trivial one-element subarrays are alternating.

• Fully alternating sequence - When every adjacent pair differs, length increases monotonically. The cumulative addition of length yields the triangular number corresponding to the total number of alternating subarrays, which is the expected outcome for a perfectly alternating list.

• Empty list - Although the method assumes at least one element (as indicated by the initial result = 1), the use of zip on an empty list results in zero iterations, and the method would return one. In contexts where an empty input is considered valid, this behavior represents a defined outcome rather than an exception.

Performance Optimizations

The implementation exhibits several deliberate choices that enhance efficiency:

• Single linear scan - By processing each element exactly once and updating counters in constant time, the algorithm avoids any nested loops or repeated traversals.

• Constant auxiliary space - Only two integer variables are maintained regardless of input size, eliminating the need for additional data structures such as auxiliary arrays or stacks.

• Pairwise iteration via zip - Leveraging Python’s built-in zip to generate adjacent pairs sidesteps manual index management and reduces the overhead associated with repeated indexing operations.

• In-place arithmetic - The conditional expression that updates length combines the reset and increment logic into a single statement, minimizing branching and keeping the hot loop tight.

These characteristics collectively ensure that the method scales gracefully with the length of the input list while keeping memory consumption minimal.

Imagine a long row of colored bouncy balls in a line. Some are red and some are blue. This code looks at the row to see how many groups of balls have colors that switch back and forth like a zig-zag pattern.

First, the code says that every single ball by itself counts as a tiny pattern. It starts by looking at the whole line. The way it works is by sliding along the balls two at a time. It checks if the first ball and the next ball are different colors.

If the two balls are different, it means the zig-zag pattern continues, so the group gets bigger. Every time the group grows, the code adds that new length to the total count of patterns found so far. If the two balls are the same color, the old pattern stops and a brand new group starts fresh with just that one ball. It keeps doing this until it reaches the very end of the row, counting all the different zig-zag patterns it finds along the way.

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
	fsq		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++

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