Count Alternating Subarrays

MEDIUM

Description

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 <= 10⁵
nums[i] is either 0 or 1.

Approaches

Checkout 3 different approaches to solve Count Alternating Subarrays. Click on different approaches to view the approach and algorithm in detail.

Brute Force Enumeration

The most straightforward approach is to generate every possible subarray and then, for each one, check if it satisfies the 'alternating' property. An alternating subarray is one where no two adjacent elements are the same.

Algorithm

Initialize a counter count to 0.
Use a nested loop to generate all possible subarrays. The outer loop i runs from 0 to n-1 for the start index, and the inner loop j runs from i to n-1 for the end index.
For each subarray nums[i...j], use a third loop k from i+1 to j to check if it's alternating.
Inside the third loop, check if nums[k] == nums[k-1]. If they are equal, the subarray is not alternating. Set a flag and break the check.
If the check completes without finding any adjacent equal elements, the subarray is alternating. Increment count.
After all subarrays are checked, return count.

This method systematically considers every contiguous block of elements in the input array. It uses two nested loops to define the start (i) and end (j) indices of a subarray. For each generated subarray, a third loop is employed to traverse its elements and verify the alternating condition. If at any point nums[k] == nums[k-1], the subarray is not alternating. If the entire subarray is traversed without this condition being met, it is counted as a valid alternating subarray. While simple, this approach is computationally expensive because it repeatedly re-scans overlapping parts of the array.

class Solution {
    public long countAlternatingSubarrays(int[] nums) {
        long count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Check if subarray nums[i...j] is alternating
                boolean isAlternating = true;
                for (int k = i + 1; k <= j; k++) {
                    if (nums[k] == nums[k - 1]) {
                        isAlternating = false;
                        break;
                    }
                }
                if (isAlternating) {
                    count++;
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n³), where n is the number of elements in `nums`. There are O(n²) subarrays, and checking each one takes up to O(n) time.Space Complexity: O(1), as we only use a constant amount of extra space for loop variables and a counter.

Pros and Cons

Pros:

Easy to understand and implement.
Correct for small input sizes.

Cons:

Extremely inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' error for large inputs as specified in the problem constraints.

Code Solutions

Checking out 3 solutions in different languages for Count Alternating Subarrays. Click on different languages to view the code.

class Solution { public long countAlternatingSubarrays ( int [] nums ) { long ans = 1 , s = 1 ; for ( int i = 1 ; i < nums . length ; ++ i ) { s = nums [ i ] != nums [ i - 1 ] ? s + 1 : 1 ; ans += s ; } return ans ; } }

Video Solution

Watch the video walkthrough for Count Alternating Subarrays

Patterns:

Math

Data Structures:

Array

Companies:

Capital One |