Count Alternating Subarrays
MedPrompt
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 <= 105nums[i]is either0or1.
Approaches
3 approaches with complexity analysis and trade-offs.
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
countto 0. - Use a nested loop to generate all possible subarrays. The outer loop
iruns from0ton-1for the start index, and the inner loopjruns fromiton-1for the end index. - For each subarray
nums[i...j], use a third loopkfromi+1tojto 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.
Walkthrough
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
Time
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
O(1), as we only use a constant amount of extra space for loop variables and a counter.
Trade-offs
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.
Solutions
Solution
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 walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.