Count Alternating Subarrays

• Initialize a counter count to 0.
• Use a nested loop to generate all possible subarrays. The outer loop i runs from 0 to n-1 for the start index, and the inner loop j runs from i to n-1 for the end index.
• For each subarray nums[i...j], use a third loop k from i+1 to j to 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.

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.

1class Solution {2    public long countAlternatingSubarrays(int[] nums) {3        long count = 0;4        int n = nums.length;5        for (int i = 0; i < n; i++) {6            for (int j = i; j < n; j++) {7                // Check if subarray nums[i...j] is alternating8                boolean isAlternating = true;9                for (int k = i + 1; k <= j; k++) {10                    if (nums[k] == nums[k - 1]) {11                        isAlternating = false;12                        break;13                    }14                }15                if (isAlternating) {16                    count++;17                }18            }19        }20        return count;21    }22}

• Initialize a counter count to 0.
• Use an outer loop i from 0 to n-1 to iterate through all possible starting positions of a subarray.
• For each i, we know the subarray of length one, [nums[i]], is always alternating, so we add 1 to count.
• Start an inner loop j from i+1 to n-1 to extend the subarray.
• In each step of the inner loop, check if nums[j] != nums[j-1].
• If they are different, the subarray nums[i...j] is also alternating, so increment count.
• If they are the same, the alternating property is broken. Any longer subarray starting at i will also not be alternating, so we can break the inner loop and move to the next starting position i+1.
• Return the total count.

We iterate through each element of the array, considering it as a potential start of an alternating subarray. For each starting index i, we count the subarray [nums[i]] and then try to extend it to the right. We use a second loop with index j to move forward. As long as nums[j] is different from nums[j-1], the subarray nums[i...j] is alternating, and we add it to our count. The moment we find nums[j] == nums[j-1], we know that no further extension from i can form an alternating subarray, so we break the inner loop and proceed to the next starting index i+1. This optimization reduces the complexity from cubic to quadratic.

1class Solution {2    public long countAlternatingSubarrays(int[] nums) {3        long count = 0;4        int n = nums.length;5        for (int i = 0; i < n; i++) {6            count++; // For subarray [nums[i]]7            for (int j = i + 1; j < n; j++) {8                if (nums[j] != nums[j - 1]) {9                    count++;10                } else {11                    break;12                }13            }14        }15        return count;16    }17}

• Initialize totalCount = 0 and currentLength = 0.
• Iterate through the array nums from index i = 0 to n-1.
• At each index i, check if it's the first element (i == 0) or if nums[i] != nums[i-1].
• If the condition is true, it means the current alternating sequence continues or a new one starts that includes the previous element. We increment currentLength.
• If nums[i] == nums[i-1], the alternating sequence is broken. We must start a new one, so we reset currentLength to 1.
• The value of currentLength represents the number of alternating subarrays that end at the current index i. Add this currentLength to totalCount.
• After the loop finishes, totalCount will hold the total number of alternating subarrays.

We can observe that the number of alternating subarrays ending at index i depends on the element at i-1. Let currentLength be the length of the longest alternating subarray ending at the current index i.

• If nums[i] is different from nums[i-1], then nums[i] can be appended to all alternating subarrays ending at i-1. The length of the new longest alternating subarray ending at i will be currentLength at i-1 plus one.
• If nums[i] is the same as nums[i-1], the alternating sequence breaks. The only alternating subarray ending at i is [nums[i]] itself, so the length is 1.

An alternating subarray of length k contains k alternating subarrays that end at its last element. For example, [1,0,1] (length 3) has three alternating subarrays ending at the final 1: [1], [0,1], and [1,0,1]. Therefore, by tracking the length of the current alternating sequence (currentLength), we can add this length to our total count at each step. This allows us to calculate the result in one pass.

1class Solution {2    public long countAlternatingSubarrays(int[] nums) {3        long totalCount = 0;4        int n = nums.length;5        if (n == 0) {6            return 0;7        }8        9        int currentLength = 0;10        for (int i = 0; i < n; i++) {11            if (i > 0 && nums[i] != nums[i - 1]) {12                // The alternating sequence continues.13                currentLength++;14            } else {15                // A new alternating sequence starts.16                currentLength = 1;17            }18            // The number of alternating subarrays ending at index i is currentLength.19            totalCount += currentLength;20        }21        22        return totalCount;23    }24}