Count Alternating Subarrays - Practice Coding Problems

Count Alternating Subarrays - Problem

Array Math Medium

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.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Fully Alternating

$ Input: nums = [0,1,0,1]

› Output: 10

💡 Note: All subarrays are alternating: [0], [1], [0], [1], [0,1], [1,0], [0,1], [0,1,0], [1,0,1], [0,1,0,1]. Total = 10.

Example 2 — Mixed Pattern

$ Input: nums = [0,1,1,0]

› Output: 5

💡 Note: Alternating subarrays: [0], [1], [1], [0], [0,1]. The segment [1,1] breaks alternation, so [0,1,1] and longer are not valid.

Example 3 — All Same

$ Input: nums = [1,1,1]

› Output: 3

💡 Note: Only single-element subarrays are alternating: [1], [1], [1]. No multi-element alternating subarrays exist.

Constraints

1 ≤ nums.length ≤ 10⁵
nums[i] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

Binary array with 0s and 1s

Process

Find all subarrays with no adjacent equal elements

Output

Total count of valid alternating subarrays

Key Takeaway

🎯 Key Insight: Each alternating segment of length n contributes exactly n*(n+1)/2 subarrays to the total count

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is that each alternating segment of length n contributes n*(n+1)/2 subarrays. Best approach uses sliding window to identify segments in O(n) time. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window Optimization	O(n)	O(1)	Expand alternating segments and calculate contribution efficiently
Brute Force	O(n³)	O(1)	Check every possible subarray to see if it's alternating

Sliding Window Optimization — Algorithm Steps

Scan array to find alternating segments
For each segment of length n, add n*(n+1)/2 to result
Reset segment length when pattern breaks

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Segments

Identify continuous alternating segments

Calculate

Apply formula n*(n+1)/2 for each segment

Sum Total

Add all segment contributions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    
    int count = 0;
    int length = 1; // Current alternating segment length
    
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] != nums[i-1]) {
            length++;
        } else {
            // End of alternating segment, add its contribution
            count += length * (length + 1) / 2;
            length = 1; // Reset for new segment
        }
    }
    
    // Add contribution of final segment
    count += length * (length + 1) / 2;
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler