#3101

Medium

LeetCode Problem Workspace

Count Alternating Subarrays

Count all alternating subarrays in a binary array efficiently using array patterns and simple mathematical reasoning.

Problem Statement

You are given a binary array nums consisting of 0s and 1s. A subarray is considered alternating if no two adjacent elements have the same value. Your task is to count all such alternating subarrays within nums.

Return an integer representing the total number of alternating subarrays. For example, in nums = [0,1,1,1], the subarrays [0], [1], [1], [1], and [0,1] are alternating, totaling 5. Ensure your solution works efficiently for arrays up to length 10^5.

Examples

Example 1

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

Output: 5

The following subarrays are alternating: [0] , [1] , [1] , [1] , and [0,1] .

Example 2

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

Output: 10

Every subarray of the array is alternating. There are 10 possible subarrays that we can choose.

Constraints

1 <= nums.length <= 105
nums[i] is either 0 or 1.

Solution Approach

Linear Traversal Counting

Traverse the array once while maintaining a count of the current alternating subarray length. Each time the alternation breaks, reset the length and add the accumulated counts to the result. This leverages the array pattern directly and avoids nested loops.

Dynamic Programming Optimization

Use a DP array where dp[i] represents the number of alternating subarrays ending at index i. For each element, if nums[i] differs from nums[i-1], dp[i] = dp[i-1] + 1; otherwise, dp[i] = 1. Sum all dp[i] to get the total, reducing repeated calculation of overlapping subarrays.

Mathematical Subarray Summation

Recognize that each alternating segment of length L contributes (L*(L+1))/2 subarrays. Identify continuous alternating segments and apply this formula to compute the total count efficiently, combining array detection with simple math.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for a single traversal or DP solution, where n is nums.length. Space complexity is O(n) for DP or O(1) for linear counting with a rolling variable.

What Interviewers Usually Probe

Ask for a solution that handles large arrays efficiently.
Check if the candidate recognizes overlapping subarrays and can optimize counting.
Probe understanding of array patterns and use of cumulative math formulas.

Common Pitfalls or Variants

Common pitfalls

Counting only subarrays of length 2 and missing longer alternating sequences.
Resetting counts incorrectly when consecutive elements are equal, undercounting subarrays.
Using nested loops, leading to timeouts for arrays near length 10^5.

Follow-up variants

Count alternating subarrays in ternary arrays instead of binary arrays.
Return the length of the longest alternating subarray instead of total count.
Count alternating subarrays that start with 1 only, skipping those starting with 0.

FAQ

What is an alternating subarray in this problem?

An alternating subarray has consecutive elements that differ, so no two adjacent numbers are the same.

Can this approach handle arrays of length 10^5?

Yes, using linear traversal or dynamic programming, the solution runs in O(n) time and is efficient for large arrays.

Why is dynamic programming useful here?

DP avoids recalculating overlapping alternating subarrays by storing counts for each index, summing them for the total.

Is there a formula for counting alternating subarrays in a segment?

Yes, a continuous alternating segment of length L contributes (L*(L+1))/2 subarrays to the total count.

Does this problem pattern differ from simple subarray counting?

Yes, it focuses on array plus math patterns, emphasizing alternation rather than any arbitrary subarray, requiring pattern recognition and cumulative counting.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

class Solution:
    def countAlternatingSubarrays(self, nums: List[int]) -> int:
        ans = s = 1
        for a, b in pairwise(nums):
            s = s + 1 if a != b else 1
            ans += s
        return ans

Continue Practicing

#3102 minimize manhattan distances #3115 maximum prime difference #3116 kth smallest amount with single denomination combination