Welcome to Subscribe On Youtube

3101. Count Alternating Subarrays

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

Solutions

Solution 1: Enumeration

We can enumerate the subarrays ending at each position, calculate the number of subarrays that meet the conditions, and sum up the number of subarrays that meet the conditions at all positions.

Specifically, we define a variable $s$ to represent the number of subarrays that meet the conditions and end with the element $nums[i]$. Initially, we set $s$ to $1$, which means the number of subarrays that meet the conditions and end with the first element is $1$.

Next, we start to traverse the array from the second element. For each position $i$, we update the value of $s$ based on the relationship between $nums[i]$ and $nums[i-1]$:

  • If $nums[i] \neq nums[i-1]$, the value of $s$ increases by $1$, that is, $s = s + 1$;
  • If $nums[i] = nums[i-1]$, the value of $s$ is reset to $1$, that is, $s = 1$.

Then, we add the value of $s$ to the answer and continue to traverse the next position of the array until the entire array is traversed.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

  • 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;
    }
}

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

  • class Solution:
    def countAlternatingSubarrays(self, nums: List[int]) -> int:
        ans = s = 1
        for a, b in pairwise(nums):
            s = s + 1 if a != b else 1
            ans += s
        return ans


  • func countAlternatingSubarrays(nums []int) int64 {
	ans, s := int64(1), int64(1)
	for i, x := range nums[1:] {
		if x != nums[i] {
			s++
		} else {
			s = 1
		}
		ans += s
	}
	return ans
}

  • function countAlternatingSubarrays(nums: number[]): number {
    let [ans, s] = [1, 1];
    for (let i = 1; i < nums.length; ++i) {
        s = nums[i] !== nums[i - 1] ? s + 1 : 1;
        ans += s;
    }
    return ans;
}

All Problems

All Solutions