We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Alternating Subarrays

Difficulty: Medium

Problem 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.

Key Insights

  • A single element subarray is always alternating.
  • For longer subarrays, elements must alternate between 0 and 1.
  • The length of the alternating subarrays can be determined by counting consecutive alternating elements.
  • The number of valid subarrays can be calculated from the length of each group of alternating elements.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use a single pass through the array to count the lengths of alternating segments. We maintain a count of the current length of alternating elements. For each segment of length k, the number of alternating subarrays can be computed using the formula k * (k + 1) / 2, since it includes all possible subarrays that can be formed from this segment. This approach ensures we only traverse the array once, making it efficient.

Code Solutions

def count_alternating_subarrays(nums):
    count = 0
    n = len(nums)
    current_length = 1

    for i in range(1, n):
        if nums[i] != nums[i - 1]:
            current_length += 1
        else:
            count += (current_length * (current_length + 1)) // 2
            current_length = 1
    
    count += (current_length * (current_length + 1)) // 2
    return count
← Back to All Questions