Watch 8 video solutions for Count Alternating Subarrays, a medium level problem involving Array, Math. This walkthrough by Aryan Mittal has 2,558 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 either 0 or 1.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 | 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. |