Count Alternating Subarrays

Medium
872.

Count Alternating Subarrays

Count Alternating Subarrays is a medium coding problem on arrays, dynamic programming and math, asked in Amazon, Microsoft, Zoho and Capital One interviews.

A binary subarray is alternating when no two adjacent elements in it are equal.

Return the number of alternating subarrays of nums.

Example 1

Input
nums = [0,1,1,1]
Output
5
Explanation
The four single elements plus [0,1].

Example 2

Input
nums = [1,0,1,0]
Output
10
Explanation
Every subarray alternates.

Example 3

Input
nums = [1,1]
Output
2

Constraints

  • 1 <= nums.length <= 50000
  • nums[i] is 0 or 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var countAlternatingSubarrays = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Alternating Subarrays — Solution in Python, Java & C++

Count Alternating Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Alternating Subarrays is a medium coding problem on arrays, dynamic programming and math, asked in Amazon, Microsoft, Zoho and Capital One interviews.

Problem statement

A binary subarray is alternating when no two adjacent elements in it are equal.

Return the number of alternating subarrays of nums.

Example 1

Input: nums = [0,1,1,1]
Output: 5
Explanation: The four single elements plus [0,1].

Example 2

Input: nums = [1,0,1,0]
Output: 10
Explanation: Every subarray alternates.

Example 3

Input: nums = [1,1]
Output: 2

Constraints

  • 1 <= nums.length <= 50000
  • nums[i] is 0 or 1

Hints for Count Alternating Subarrays

  1. Hint 1

    Count the alternating subarrays ending at each index and add them up.

  2. Hint 2

    If nums[i] != nums[i-1], every alternating subarray ending at i-1 extends by one, plus the single element nums[i].

  3. Hint 3

    If they are equal, the only one ending at i is nums[i] alone.

How to solve Count Alternating Subarrays

Let run be the number of alternating subarrays ending at the current index — equivalently the length of the longest alternating run ending there. It either grows by one or resets to one.

Approach

  1. Start with run = 1 and total = 1 for the first element.
  2. For each later index, set run = run + 1 when it differs from its predecessor, otherwise run = 1.
  3. Add run to the total at every step.

Why it works

A subarray ending at i alternates exactly when it lies inside the maximal alternating run ending at i, and there is one such subarray per starting point inside that run — so the count is the run's length. Summing over all right endpoints counts every alternating subarray once, since each has a unique right endpoint.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Forgetting the initial total = 1 for the first element loses one.
  • Resetting run to 0 instead of 1 drops the single-element subarray.
  • The total reaches about 1.25 · 10^9 at the stated size.

Reference solution

Python

from typing import List

def countAlternatingSubarrays(nums: List[int]) -> int:
    total = run = 1
    for i in range(1, len(nums)):
        run = run + 1 if nums[i] != nums[i - 1] else 1
        total += run
    return total

Java

public static int countAlternatingSubarrays(int[] nums) {
    long total = 1, run = 1;
    for (int i = 1; i < nums.length; i++) {
        run = (nums[i] != nums[i - 1]) ? run + 1 : 1;
        total += run;
    }
    return (int) total;
}

C++

int countAlternatingSubarrays(vector<int>& nums) {
    long long total = 1, run = 1;
    for (int i = 1; i < (int) nums.size(); i++) {
        run = (nums[i] != nums[i - 1]) ? run + 1 : 1;
        total += run;
    }
    return (int) total;
}

JavaScript

var countAlternatingSubarrays = function(nums) {
    var total = 1, run = 1;
    for (var i = 1; i < nums.length; i++) {
        if (nums[i] !== nums[i - 1]) run++; else run = 1;
        total += run;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming