Count Alternating Subarrays solution and explanation
9 more videos on this problem
3101. Count Alternating Subarrays | Easy | Array | Hash MapAryan Mittal · 8:22 · 2K views
Leetcode 3101: Count Alternating SubarraysAlgorithms Casts · 8:33 · 675 views
3101. Count Alternating Subarrays (Leetcode Medium)Programming Live with Larry · 6:09 · 423 views
Leetcode Weekly 391: Count Alternating Subarrays | Ranked 114 - Brute Force to OptimisationsBharat Khanna · 14:31 · 108 views
3101. Count Alternating Subarrays || Leetcode Weekly Contest 391Ashish Kumar · 7:14 · 98 views
Rust LeetCode 3101 Count Alternating SubarraysTheShortBlueDragon · 1:36 · 88 views
3101. Count Alternating Subarrays | Array traversalTech Courses · 7:11 · 67 views
Count Alternating Subarrays - Leetcode 3101 || Weekly Contest 391 || Problem - C || Leetcode MediumLevel up with Coding · 8:45 · 64 views
Count Alternating Subarrays | Leetcode 3101 | Approach + Code with explanation.Pirai's Academy · 8:54 · 52 views
3101 COUNT ALTERNATING SUBARRAYS LEETCODE CONTEST 31ST MARCHBEASTCODES · 7:12 · 32 views
The problem
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).
def count_alternating_subarrays(nums):
count = 0
length = 1
for i in range(1, len(nums)):
if nums[i] != nums[i - 1]:
length += 1
else:
length = 1
count += length
return count + len(nums)
nums = [0, 1, 1, 1]
print(count_alternating_subarrays(nums))public class AlternateSubarrays {
public static int countAlternatingSubarrays(int[] nums) {
int count = 0, length = 1;
for (int i = 1; i < nums.length; i++) {
length = (nums[i] != nums[i - 1]) ? length + 1 : 1;
count += length;
}
return count + nums.length;
}
public static void main(String[] args) {
int[] nums = {0, 1, 1, 1};
System.out.println(countAlternatingSubarrays(nums));
}
}#include <vector>
#include <iostream>
int countAlternatingSubarrays(std::vector<int>& nums) {
int count = 0, length = 1;
for (size_t i = 1; i < nums.size(); ++i) {
length = (nums[i] != nums[i - 1]) ? length + 1 : 1;
count += length;
}
return count + nums.size();
}
int main() {
std::vector<int> nums = {0, 1, 1, 1};
std::cout << countAlternatingSubarrays(nums);
return 0;
}function countAlternatingSubarrays(nums) {
let count = 0, length = 1;
for (let i = 1; i < nums.length; i++) {
length = (nums[i] !== nums[i - 1]) ? length + 1 : 1;
count += length;
}
return count + nums.length;
}
console.log(countAlternatingSubarrays([0, 1, 1, 1]));#include <stdio.h>
int countAlternatingSubarrays(int* nums, int numsSize) {
int count = 0, length = 1;
for (int i = 1; i < numsSize; i++) {
if (nums[i] != nums[i - 1]) {
length++;
} else {
length = 1;
}
count += length;
}
return count + numsSize; // includes all single element subarrays
}
int main() {
int nums[] = {0, 1, 1, 1};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d", countAlternatingSubarrays(nums, size));
return 0;
}using System;
namespace AlternateSubarrays {
class Program {
public static int CountAlternatingSubarrays(int[] nums) {
int count = 0, length = 1;
for (int i = 1; i < nums.Length; i++) {
length = (nums[i] != nums[i - 1]) ? length + 1 : 1;
count += length;
}
return count + nums.Length;
}
static void Main(string[] args) {
int[] nums = {0, 1, 1, 1};
Console.WriteLine(CountAlternatingSubarrays(nums));
}
}
}Python makes use of a for-loop to go through the list, recalculating the length of the alternating subarray when conditions are met, similar to other implementations.
Time Complexity: O(n)
Space Complexity: O(1)
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.
def count_alternating_subarrays(nums):
count, current_count = 0, 0
for i in range(len(nums)):
if i == 0 or nums[i] != nums[i - 1]:
current_count += 1
else:
current_count = 1
count += current_count
return count
nums = [1, 0, 1, 0]
print(count_alternating_subarrays(nums))public class AlternateSubarrays {
public static int countAlternatingSubarrays(int[] nums) {
int count = 0, currentCount = 0;
for (int i = 0; i < nums.length; i++) {
currentCount = (i == 0 || nums[i] != nums[i - 1]) ? currentCount + 1 : 1;
count += currentCount;
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 0, 1, 0};
System.out.println(countAlternatingSubarrays(nums));
}
}#include <vector>
#include <iostream>
int countAlternatingSubarrays(std::vector<int>& nums) {
int count = 0, currentCount = 0;
for (size_t i = 0; i < nums.size(); ++i) {
currentCount = (i == 0 || nums[i] != nums[i - 1]) ? currentCount + 1 : 1;
count += currentCount;
}
return count;
}
int main() {
std::vector<int> nums = {1, 0, 1, 0};
std::cout << countAlternatingSubarrays(nums);
return 0;
}function countAlternatingSubarrays(nums) {
let count = 0, currentCount = 0;
for (let i = 0; i < nums.length; i++) {
currentCount = (i === 0 || nums[i] !== nums[i - 1]) ? currentCount + 1 : 1;
count += currentCount;
}
return count;
}
console.log(countAlternatingSubarrays([1, 0, 1, 0]));#include <stdio.h>
int countAlternatingSubarrays(int* nums, int numsSize) {
int count = 0, currentCount = 0;
for (int i = 0; i < numsSize; i++) {
if (i == 0 || nums[i] != nums[i - 1]) {
currentCount = (i == 0) ? 1 : currentCount + 1;
} else {
currentCount = 1;
}
count += currentCount;
}
return count;
}
int main() {
int nums[] = {1, 0, 1, 0};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d", countAlternatingSubarrays(nums, size));
return 0;
}using System;
namespace AlternateSubarrays {
class Program {
public static int CountAlternatingSubarrays(int[] nums) {
int count = 0, currentCount = 0;
for (int i = 0; i < nums.Length; i++) {
currentCount = (i == 0 || nums[i] != nums[i - 1]) ? currentCount + 1 : 1;
count += currentCount;
}
return count;
}
static void Main(string[] args) {
int[] nums = {1, 0, 1, 0};
Console.WriteLine(CountAlternatingSubarrays(nums));
}
}
}In Python, implement using running variables to calculate alternating segments, instantly adding to the count of potential subarrays.
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).
function countAlternatingSubarrays(nums: number[]): number {
let [ans, s] = [1, 1];
for (let i = 1; i < nums.length; ++i) {
s = nums[i] !== nums[i - 1] ? s + 1 : 1;
ans += s;
}
return ans;
}func countAlternatingSubarrays(nums []int) int64 {
ans, s := int64(1), int64(1)
for i, x := range nums[1:] {
if x != nums[i] {
s++
} else {
s = 1
}
ans += s
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window | Time Complexity: O(n) |
| Direct Counting with Running Sum | Time Complexity: O(n) |
| Enumeration | – |
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. |
Frequently asked questions
Is Count Alternating Subarrays easy or hard?
The problem is rated Medium because the counting insight is not immediately obvious. Many developers initially think about checking every subarray, which leads to O(n^2) time. Recognizing that each alternating streak contributes multiple subarrays enables the optimal O(n) solution.
Count Alternating Subarrays Python/Java solution
In Python or Java, iterate through the array and maintain a variable representing the current alternating streak length. If the current value differs from the previous one, increment the streak; otherwise reset it to 1. Add the streak length to the answer after each step.
How to solve Count Alternating Subarrays in O(n)?
Traverse the array once while maintaining the length of the current alternating run. If nums[i] differs from nums[i-1], increment the run length; otherwise reset it to 1. Add the run length to the total at each step. This counts all subarrays ending at each position in linear time.
What is the best approach for Count Alternating Subarrays?
The best approach is the running count method that tracks the length of the current alternating streak. For each index, if the element differs from the previous one, extend the streak; otherwise reset it. Add the streak length to the answer. This achieves O(n) time and O(1) space.
Is Count Alternating Subarrays asked at Google/Amazon/Meta?
Alternating pattern and subarray counting problems commonly appear in interviews at companies like Amazon, Google, and Meta. Variants test understanding of sliding window patterns, prefix counting, and recognizing how contiguous sequences contribute multiple subarrays.
What data structure is used in Count Alternating Subarrays?
The problem mainly uses array traversal and simple integer counters. No complex data structures are required. The key technique is detecting alternating relationships between adjacent elements while maintaining the current streak length.
What is the time complexity of Count Alternating Subarrays?
The optimal solutions run in O(n) time because the array is scanned once. Each element is compared with its previous neighbor and contributes to the running count of alternating subarrays. Space complexity is O(1) since only a few counters are stored.