LeetCode 3101 - Count Alternating Subarrays

LeetCode Problem 3101

Difficulty: 🟡 Medium
Topics: Array, Math

Solution

Problem Understanding

The problem gives us a binary array nums, meaning every element is either 0 or 1. We need to count how many subarrays are alternating.

A subarray is considered alternating if no two adjacent elements inside that subarray are equal. In other words, every neighboring pair must contain different values.

For example, the subarray [0,1,0,1] is alternating because every adjacent pair differs:

• 0 != 1
• 1 != 0
• 0 != 1

However, [1,0,0] is not alternating because the last two elements are equal.

The task is to count all possible alternating subarrays and return the total count.

The constraints are important:

• 1 <= nums.length <= 10^5
• Each value is either 0 or 1

An array of size 10^5 is large enough that quadratic solutions will likely time out. This strongly suggests we need an O(n) solution.

Several edge cases are important to think about early:

• A single-element array is always alternating because there are no adjacent elements to violate the condition.
• An array where every value is the same, such as [1,1,1], only has valid subarrays of length 1.
• An array that perfectly alternates, such as [0,1,0,1], means every possible subarray is valid.
• Transitions between alternating and non-alternating regions can easily cause off-by-one mistakes if not handled carefully.

Approaches

Brute Force Approach

A straightforward solution is to generate every possible subarray and check whether it is alternating.

For every starting index i, we try every ending index j. For each subarray nums[i:j+1], we scan through its elements and verify that no adjacent pair is equal.

This approach is correct because it explicitly checks the definition of an alternating subarray for every possible candidate.

However, it is too slow for the given constraints. There are O(n^2) subarrays, and checking each one may take O(n) time in the worst case. This leads to O(n^3) complexity in the naive version. Even with optimization, a brute force solution still remains too expensive for n = 10^5.

Optimal Approach

The key observation is that we do not need to examine every subarray independently.

Suppose we process the array from left to right and track the length of the current alternating segment ending at index i.

If nums[i] != nums[i-1], then the alternating sequence continues, so we can extend the previous length.

If nums[i] == nums[i-1], then the alternating property breaks, and we must start a new alternating segment of length 1.

The important insight is this:

• If the current alternating length is k, then there are exactly k alternating subarrays ending at the current index.

For example:

• Alternating segment length 1 contributes:

• [x]

• Length 2 contributes:

• [a,b]

• [b]

• Length 3 contributes:

• [a,b,c]

• [b,c]

• [c]

So at each position, we add the current alternating length to the answer.

This gives a linear-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) to O(n³)	O(1)	Checks every subarray individually
Optimal	O(n)	O(1)	Tracks alternating length ending at each index

Algorithm Walkthrough

1. Initialize a variable current_length to 1.

Every single element by itself forms a valid alternating subarray, so the smallest valid length is always 1. 2. Initialize the answer variable total to 1.

The first element contributes one alternating subarray. 3. Traverse the array starting from index 1.

At each index, compare the current element with the previous element. 4. If nums[i] != nums[i-1], extend the alternating segment.

This means the current element continues the alternating pattern, so:

current_length += 1

5. Otherwise, reset the alternating segment.

Since two equal adjacent values break alternation:

current_length = 1

6. Add current_length to the total answer.

Every alternating subarray ending at index i corresponds to one suffix of the current alternating segment. 7. Continue until the end of the array. 8. Return the accumulated total.

Why it works

The algorithm maintains an invariant:

• current_length always equals the number of consecutive alternating elements ending at the current index.

Every suffix of this alternating segment is also alternating, so the number of alternating subarrays ending at the current index is exactly current_length.

By summing this value for every index, we count every alternating subarray exactly once.

Python Solution

from typing import List

class Solution:
    def countAlternatingSubarrays(self, nums: List[int]) -> int:
        current_length = 1
        total = 1

        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                current_length += 1
            else:
                current_length = 1

            total += current_length

        return total

The implementation directly follows the algorithm described earlier.

The variable current_length stores the length of the current alternating sequence ending at the current position.

When the current value differs from the previous value, we extend the sequence because the alternating condition still holds.

When the values are equal, the alternating sequence breaks, so we reset the length back to 1.

At every index, we add current_length to total because each suffix of the current alternating segment forms a valid alternating subarray ending at that index.

The algorithm uses only constant extra memory and processes the array in a single pass.

Go Solution

func countAlternatingSubarrays(nums []int) int64 {
    currentLength := int64(1)
    total := int64(1)

    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[i-1] {
            currentLength++
        } else {
            currentLength = 1
        }

        total += currentLength
    }

    return total
}

The Go implementation is almost identical to the Python version.

One important detail is the use of int64. The total number of subarrays can be as large as:

n * (n + 1) / 2

For n = 10^5, this value exceeds the safe range of a 32-bit integer, so int64 is necessary.

Go slices already handle empty and non-empty arrays naturally, and the constraints guarantee at least one element exists.

Worked Examples

Example 1

Input:

nums = [0,1,1,1]

We track:

• current_length
• total

Index	Value	Comparison	current_length	total
0	0	Start	1	1
1	1	1 != 0	2	3
2	1	1 == 1	1	4
3	1	1 == 1	1	5

Final answer:

5

The alternating subarrays are:

[0]
[1]
[1]
[1]
[0,1]

Example 2

Input:

nums = [1,0,1,0]

Index	Value	Comparison	current_length	total
0	1	Start	1	1
1	0	0 != 1	2	3
2	1	1 != 0	3	6
3	0	0 != 1	4	10

Final answer:

10

Every possible subarray is alternating.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array
Space	O(1)	Only a few variables are used

The algorithm processes each element exactly once. Every iteration performs constant-time work, so the total runtime is linear in the size of the array.

No auxiliary data structures proportional to the input size are used, so the extra space complexity remains constant.

Test Cases

from typing import List

class Solution:
    def countAlternatingSubarrays(self, nums: List[int]) -> int:
        current_length = 1
        total = 1

        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                current_length += 1
            else:
                current_length = 1

            total += current_length

        return total

sol = Solution()

assert sol.countAlternatingSubarrays([0,1,1,1]) == 5  # provided example
assert sol.countAlternatingSubarrays([1,0,1,0]) == 10  # fully alternating

assert sol.countAlternatingSubarrays([0]) == 1  # single element
assert sol.countAlternatingSubarrays([1]) == 1  # single element

assert sol.countAlternatingSubarrays([1,1,1]) == 3  # only single-element subarrays
assert sol.countAlternatingSubarrays([0,0,0,0]) == 4  # all equal values

assert sol.countAlternatingSubarrays([0,1]) == 3  # both singles plus pair
assert sol.countAlternatingSubarrays([1,0]) == 3  # reverse alternating pair

assert sol.countAlternatingSubarrays([0,1,0]) == 6  # every subarray valid
assert sol.countAlternatingSubarrays([1,0,1]) == 6  # every subarray valid

assert sol.countAlternatingSubarrays([0,1,1,0]) == 6  # alternating break in middle
assert sol.countAlternatingSubarrays([1,1,0,1]) == 6  # restart after equal pair

assert sol.countAlternatingSubarrays([0,1,0,1,0]) == 15  # fully alternating larger case
assert sol.countAlternatingSubarrays([1,1,1,1,1]) == 5  # no alternating pairs

print("All tests passed.")

Test	Why
[0,1,1,1]	Validates provided example
[1,0,1,0]	Validates fully alternating array
[0]	Smallest possible input
[1]	Single-element edge case
[1,1,1]	No alternating adjacent pairs
[0,0,0,0]	Larger non-alternating sequence
[0,1]	Small alternating pair
[1,0]	Alternating pair in reverse order
[0,1,0]	Every subarray alternating
[1,0,1]	Another fully alternating case
[0,1,1,0]	Alternation interrupted in middle
[1,1,0,1]	Reset and restart behavior
[0,1,0,1,0]	Larger fully alternating array
[1,1,1,1,1]	Worst-case minimal contribution

Edge Cases

A very important edge case is a single-element array. Since there are no adjacent elements, every single-element subarray is automatically alternating. It is easy to accidentally initialize counters incorrectly and return 0 instead of 1. This implementation correctly initializes both current_length and total to 1.

Another important case is when all elements are identical, such as [1,1,1,1]. In this situation, every adjacent pair breaks the alternating condition. The only valid subarrays are the individual elements themselves. The implementation handles this by resetting current_length to 1 whenever two adjacent values are equal.

A third important edge case is a fully alternating array like [0,1,0,1,0]. Here, every possible subarray is valid. This can expose bugs where the algorithm fails to accumulate counts correctly. The implementation correctly increases current_length at every step, producing the triangular number total:

1 + 2 + 3 + 4 + 5

which equals the total number of subarrays.