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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Alternating Subarrays

Number: 3374

Difficulty: Medium

Paid? No

Companies: Meta, Capital One

Problem Description

Given a binary array nums, we define an alternating subarray as a subarray where no two adjacent elements are the same. The task is to count the number of alternating subarrays present in nums. Note that every individual element forms an alternating subarray on its own.

Key Insights

  • Every single element is an alternating subarray.
  • For consecutive elements that form an alternating pattern, if the length of the segment is L, then the number of subarrays in that segment is: L*(L+1)/2.
  • When two consecutive elements are the same, the current alternating segment ends and a new one begins.

Space and Time Complexity

Time Complexity: O(n), where n is the length of nums (we make a single pass through the array).
Space Complexity: O(1), as only a few counters are used.

Solution

We traverse the array and use a counter to keep track of the current streak of alternating elements. If the current element is different from the previous element, we increment the streak counter; otherwise, we calculate the number of alternating subarrays formed by the streak using the formula (streak*(streak + 1))/2 and reset the streak counter to 1 for the current element. Finally, we add the count from the last streak after the loop.
The key data structures used are basic variables (counters) and the approach is a single-pass greedy method. This ensures a very efficient counting of the required subarrays.

Code Solutions

# Python solution for counting alternating subarrays

def countAlternatingSubarrays(nums):
    # total will hold the sum of alternating subarrays counts
    total = 0
    # current_count holds the current streak length of alternating subarray segment
    current_count = 1  # every element starts a new subarray by itself

    # Traverse through the array starting from the second element
    for i in range(1, len(nums)):
        # If the current element is different from previous, increment the streak
        if nums[i] != nums[i-1]:
            current_count += 1
        else:
            # Otherwise, add the count of subarrays for the segment and reset streak count
            total += current_count * (current_count + 1) // 2
            current_count = 1  # reset with current element as a new segment

    # Add the subarrays count of the final streak
    total += current_count * (current_count + 1) // 2
    return total

# Example usage:
print(countAlternatingSubarrays([0,1,1,1]))  # Expected output: 5
print(countAlternatingSubarrays([1,0,1,0]))  # Expected output: 10
← Back to All Questions