[LeetCode] 3208. Alternating Groups II

Problem

https://leetcode.com/problems/alternating-groups-ii/description

Leetcode - Alternating Groups II

Type - Two pointers, Sliding Window

Difficulty - Medium

Approach & Solution

n * k solution will exceed time limit.

Instead, if we get alternating segment [l, r), we can get r - l - k + 1 groups.

data structure and variables:

• last: number of last index

• ans: total counts of alternating groups

With sliding window approach, increase right range as long as possible.

After increasing right range, [l, r) will be alternating segment.

Increase ans by r - l - k + 1 if r-l >= k.

Then, update l to r.

Complexity

Time Complexity: O(N) - Iterating 0 to n+k-1

Space Complexity: O(1) - No extra data structures.

Code (C++ | Go)

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    int numberOfAlternatingGroups(vector<int>& colors, int k) {
        int n = colors.size();

        int ans = 0;
        for(int i = 0; i < n+k-1; i++) {
            int last = colors[i%n];
            int j = i+1;
            while(j < n+k-1 && colors[j%n] != last) {
                last = colors[j%n];
                j++;
            } 

            if(j - i >= k) {
                ans += j-i-k+1;
            }
            i = j - 1;
        }

        return ans;
    }
};

func numberOfAlternatingGroups(colors []int, k int) int {
    ans := 0
    n := len(colors)

    for i := 0; i < n+k-1; i++ {
        last := colors[i%n]
        j := i+1
        for j < n+k-1 && colors[j%n] != last {
            last = colors[j%n] 
            j++
        }

        if j - i >= k {
            ans += j - i - k + 1;
        } 
        i = j-1;
    }

    return ans
}