Count Alternating Subarrays

Count Alternating Subarrays

What is this problem about?

The Count Alternating Subarrays coding problem asks you to find the number of subarrays in a binary array (containing only 0s and 1s) where no two adjacent elements are the same. For example, [0, 1, 0] is alternating, but [0, 1, 1] is not. Every single element is considered an alternating subarray of length 1.

Why is this asked in interviews?

Meta and Capital One use the Count Alternating Subarrays interview question to evaluate your ability to apply a linear scan optimization. It’s a "Medium" problem that tests if you can move beyond O(N^2) (checking every subarray) to O(N) by using the property that an alternating sequence of length L contains L * (L + 1) / 2 alternating subarrays.

Algorithmic pattern used

This is a Sliding Window / Two Pointers problem, though it can be solved with a simple Linear Scan.

1. Maintain a variable current_length for the current alternating sequence.
2. Iterate through the array.
3. If nums[i] != nums[i-1], increment current_length.
4. If nums[i] == nums[i-1], reset current_length to 1.
5. Add current_length to your total count at each step. This works because adding an element to an alternating sequence of length L creates L+1 new alternating subarrays.

Example explanation

nums = [0, 1, 1, 0]

1. i=0: nums[0]=0. len=1. Total = 1.
2. i=1: nums[1]=1. 1 != 0. len=2. Total = 1 + 2 = 3. (Subarrays: [0], [1], [0,1])
3. i=2: nums[2]=1. 1 == 1. Reset len=1. Total = 3 + 1 = 4. (New subarray: [1])
4. i=3: nums[3]=0. 0 != 1. len=2. Total = 4 + 2 = 6. (New subarrays: [0], [1,0]) Result: 6.

Common mistakes candidates make

• Redundant Checks: Re-calculating alternating properties for every subarray from scratch.
• Integer Overflow: For very large arrays, the total count might exceed a 32-bit integer. Use a 64-bit integer (long) for the sum.
• Base Case: Forgetting that an array of length 1 is always alternating.

Interview preparation tip

This problem is a great example of "Contiguous sequence counting." The pattern "Add current length to total" is also used in problems like "Count Subarrays with Sum K" or "Longest Turbulent Subarray."