Count Alternating Subarrays - Solution & Explanation
Problem Statement
You are given a binary array nums.
We call a subarray alternating if no two adjacent elements in the subarray have the same value.
Return the number of alternating subarrays in nums.
Example 1:
Input: nums = [0,1,1,1]
Output: 5
Explanation:
The following subarrays are alternating: [0], [1], [1], [1], and [0,1].
Example 2:
Input: nums = [1,0,1,0]
Output: 10
Explanation:
Every subarray of the array is alternating. There are 10 possible subarrays that we can choose.
Constraints:
1 <= nums.length <= 105nums[i]is either0or1.
Approach Overview
Problem Overview: You are given a binary array. A subarray is considered alternating if every pair of adjacent elements is different (0 followed by 1 or 1 followed by 0). The task is to count how many subarrays satisfy this alternating pattern.
Approach 1: Sliding Window (O(n) time, O(1) space)
This method treats every maximal alternating segment as a window. Iterate through the array while expanding the right boundary as long as nums[i] != nums[i-1]. Once the alternating pattern breaks, reset the window start. For each position, the number of valid alternating subarrays ending at that index equals the current window length. Accumulate this value into the answer. This approach works because any prefix of a valid alternating window is also alternating. It relies on simple comparisons and sequential traversal, making it a natural fit for problems involving contiguous patterns in an array using a sliding window style scan.
Approach 2: Direct Counting with Running Sum (O(n) time, O(1) space)
This approach removes the explicit window and keeps a running length of the current alternating streak. Start with length = 1 because every single element forms a valid subarray. While iterating, check if the current element differs from the previous one. If it does, increment the streak; otherwise reset it to 1. Add the current streak length to the total count at each step. The key insight: if an alternating run has length k, it contributes exactly k subarrays ending at that position. This converts the problem into simple arithmetic accumulation, which is why the solution often appears under both array and math reasoning categories.
The running-count approach is effectively a compressed form of the sliding window technique. Instead of maintaining explicit boundaries, it tracks only the length of the valid segment. The logic remains identical: extend the sequence when the alternating property holds and reset when it breaks.
Recommended for interviews: The running sum approach is typically what interviewers expect. It achieves optimal O(n) time and constant memory while demonstrating that you recognize the combinational contribution of each alternating segment. Explaining the sliding window first can still help show reasoning about contiguous constraints, but the compact counting solution shows stronger problem insight.
Approach 1: Sliding Window
The sliding window approach is used to efficiently calculate and count the alternating subarrays. The main idea is to use a variable to maintain the length of the current alternating subarray and extend this subarray as far as possible to find all valid subarrays.
We keep track of the current alternating subarray length and increment our result with it. If two adjacent numbers are the same, we reset the length to 1 (because each element itself is an alternating subarray).
In C, we iterate over the binary array while maintaining a length counter for the current alternating subarray. Whenever two consecutive elements differ, we increase our current length and add it to our count. If they are the same, we reset the current length to 1 because a single element is always a valid subarray.
Complexity
Time Complexity: O(n), where n is the length of the array. We only traverse the array once.
Space Complexity: O(1), as we only use a constant amount of extra space.
Approach 2: Direct Counting with Running Sum
This approach involves iterating through the array while recording the length of alternating subarrays with a running sum for alternating subarray counts. Each time a new subarray stretch is identified, contribute to the ongoing subarray count for faster computation.
This can be perceived as adding additional subarrays at every extension of alternating elements.
In this C implementation, we traverse the array with variables keeping track of ongoing alternating subarray counts. Each time we establish a new alternating segment, it increases the current additional subarray count.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Enumeration
We can enumerate the subarrays ending at each position, calculate the number of subarrays that meet the conditions, and sum up the number of subarrays that meet the conditions at all positions.
Specifically, we define a variable s to represent the number of subarrays that meet the conditions and end with the element nums[i]. Initially, we set s to 1, which means the number of subarrays that meet the conditions and end with the first element is 1.
Next, we start to traverse the array from the second element. For each position i, we update the value of s based on the relationship between nums[i] and nums[i-1]:
- If
nums[i] neq nums[i-1], the value ofsincreases by1, that is,s = s + 1; - If
nums[i] = nums[i-1], the value ofsis reset to1, that is,s = 1.
Then, we add the value of s to the answer and continue to traverse the next position of the array until the entire array is traversed.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window | Time Complexity: O(n), where n is the length of the array. We only traverse the array once. |
| Direct Counting with Running Sum | Time Complexity: O(n) |
| Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Good when reasoning about contiguous segments or explaining window expansion and reset logic in interviews. |
| Direct Counting with Running Sum | O(n) | O(1) | Best general solution. Minimal state, simple implementation, and optimal performance. |
Video Solution
3101. Count Alternating Subarrays | Easy | Array | Hash Map • Aryan Mittal • 2,598 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Alternating Subarrays easy or hard?
Count Alternating Subarrays Python/Java solution
How to solve Count Alternating Subarrays in O(n)?
What is the best approach for Count Alternating Subarrays?
Is Count Alternating Subarrays asked at Google/Amazon/Meta?
What data structure is used in Count Alternating Subarrays?
What is the time complexity of Count Alternating Subarrays?
Ready to solve this problem?
Practice Count Alternating Subarrays with our built-in code editor and test cases.
Practice on FleetCode