LeetCode Entry

3208. Alternating Groups II

09.03.2025 medium 2025 kotlin rust

Count cycling alterating k-subarrays pointers

3208. Alternating Groups II medium blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/920

Problem TLDR

Count cycling alterating k-subarrays #medium #two_pointers

Intuition

Two pointers solution:

  • the right pointer goes at k distance from the left
  • if next not alterating, stop, and move left = right
  • otherwise res++ and move both +1

The more simple solution is the counting:

  • move a single pointer
  • increase on alteratings or set back to 1
  • everything >= k is good

Approach

  • the cycle simpler handled with the current and next instead of previous
  • use xor to look cooler
  • in Rust slices are O(1) memory, concat the tail
  • golf in Kotlin costs O(n) memory

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\) or O(1)

Code


    fun numberOfAlternatingGroups(c: IntArray, k: Int) = {
        var f = 0; (c.asList() + c.take(k)).zipWithNext()
        .count { (a, b) -> f *= a xor b; ++f >= k }}()



    pub fn number_of_alternating_groups(c: Vec<i32>, k: i32) -> i32 {
        let mut f = 0; [&c[..], &c[..k as usize]].concat().windows(2)
        .map(|w| { f *= w[0] ^ w[1]; f += 1; (f >= k) as i32 }).sum()
    }



    int numberOfAlternatingGroups(vector<int>& c, int k) {
        int r = 0, f = 0, n = size(c), i = 0;
        for (; i < n + k - 1;) f *= c[i % n] ^ c[(i++ + 1) % n], r += k <= ++f;
        return r;
    }