LeetCode 3245 - Alternating Groups III

LeetCode Problem 3245

Difficulty: 🔴 Hard
Topics: Array, Binary Indexed Tree, Ordered Set

Solution

Problem Understanding

We are given a circular array called colors, where each element is either 0 or 1. These represent red and blue tiles arranged in a ring, which means index 0 and index n - 1 are adjacent.

A group is considered alternating if every adjacent pair inside that contiguous segment has different colors. For example:

• [0,1,0,1] is alternating
• [1,0,1] is alternating
• [0,0,1] is not alternating because two adjacent values are equal

The queries come in two forms:

• [1, size]

We must count how many contiguous circular subarrays of length size are alternating.

• [2, index, color]

We update colors[index] to the new color.

The challenge comes from the fact that:

1. The array is circular
2. Updates happen dynamically
3. We may have up to 5 * 10^4 queries

A naive solution that recomputes all alternating groups after every update would be far too slow.

The key observation is that an alternating segment is completely determined by whether neighboring tiles differ. If we define:

diff[i] = 1 if colors[i] != colors[(i + 1) % n]
          0 otherwise

then a subarray of size k is alternating if and only if all k - 1 adjacent edges inside it are valid alternating edges.

So instead of tracking colors directly, we track runs of consecutive 1s inside the diff array.

Important edge cases include:

• The entire circle being alternating
• Updates that do not change the color
• Very small valid group sizes
• Circular wraparound segments
• Merging and splitting alternating runs after updates

The constraints strongly suggest we need approximately O(log n) work per update and query.

Approaches

Brute Force Approach

The brute force solution directly processes every query.

For a type 1 query with size k, we examine every possible starting index in the circular array. For each start position, we verify whether the next k elements alternate properly.

To verify alternation, we compare every adjacent pair inside the candidate segment. Since there are k - 1 comparisons per segment and n possible starting positions, each query costs O(n * k).

For update queries, we simply modify the array.

This approach is correct because it explicitly checks the definition of an alternating group. However, it is far too slow. In the worst case:

O(q * n^2)

which is impossible for n = 5 * 10^4.

Optimal Approach

The important insight is that alternating behavior depends only on adjacent differences.

Define:

diff[i] = 1 if colors[i] != colors[(i + 1) % n]

Now a segment of size k is alternating if the corresponding k - 1 entries in diff are all 1.

This transforms the problem into maintaining contiguous runs of 1s in a circular binary array.

Suppose a run of consecutive 1s has length L. Then it contributes:

L - (k - 1) + 1

valid windows for a query size k, provided L >= k - 1.

We maintain these runs dynamically using:

• Ordered intervals
• Fenwick Trees for aggregated statistics

Updates only affect two edges in diff, so only local interval changes occur.

This gives efficient updates and queries.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q * n²)	O(1)	Rechecks all candidate segments every query
Optimal	O((n + q) log n)	O(n)	Maintains alternating runs dynamically

Algorithm Walkthrough

Step 1: Build the Difference Array

We create:

diff[i] = 1 if colors[i] != colors[(i + 1) % n]

Each value represents whether the edge between neighboring tiles alternates correctly.

If a segment of length k is alternating, then the corresponding k - 1 edges in diff must all be 1.

Step 2: Convert the Problem into Runs of Ones

A contiguous run of 1s in diff represents a maximal alternating region.

For example:

diff = [1,1,1,0,1]

contains:

• one run of length 3
• one run of length 1

If we need groups of size k, then we need windows of:

need = k - 1

inside these runs.

A run of length L contributes:

L - need + 1

valid groups if L >= need.

Step 3: Store Runs as Intervals

We maintain all runs of 1s as intervals:

[start, end]

We also maintain:

• the length of each interval
• a sorted structure for locating intervals during updates

Step 4: Maintain Fenwick Trees

We maintain two Fenwick Trees:

• countBIT[length]

Number of intervals with this length

• sumBIT[length]

Sum of lengths of intervals with this length

These allow efficient range aggregation.

To answer queries efficiently, we compute:

Σ (L - need + 1)

over all L >= need.

This becomes:

Σ L - (need - 1) * count

which Fenwick Trees support in O(log n).

Step 5: Handle Circular Full Alternation

If the entire circle alternates, then every edge in diff is 1.

In this case:

all n starting positions are valid

for every valid query size.

This special case must be handled separately because the run wraps around the entire circle.

Step 6: Process Updates

Changing one color only affects two neighboring edges:

(index - 1 + n) % n
index

in diff.

Each changed edge may:

• create a new run
• destroy a run
• split a run
• merge two runs

We update the interval structure and Fenwick Trees accordingly.

Why it works

The core invariant is:

A segment is alternating iff all adjacent edges inside it differ.

The diff array captures exactly this property.

Runs of 1s in diff correspond precisely to maximal alternating regions. Counting alternating groups therefore reduces to counting windows inside runs.

Since updates only affect neighboring edges, we can maintain these runs incrementally while preserving correctness.

Python Solution

from typing import List
from bisect import bisect_left, insort

class FenwickTree:
    def __init__(self, n: int):
        self.n = n
        self.bit = [0] * (n + 2)

    def add(self, idx: int, delta: int) -> None:
        while idx <= self.n:
            self.bit[idx] += delta
            idx += idx & -idx

    def query(self, idx: int) -> int:
        result = 0
        while idx > 0:
            result += self.bit[idx]
            idx -= idx & -idx
        return result

    def range_query(self, left: int, right: int) -> int:
        return self.query(right) - self.query(left - 1)

class Solution:
    def numberOfAlternatingGroups(
        self,
        colors: List[int],
        queries: List[List[int]]
    ) -> List[int]:

        n = len(colors)

        diff = [
            1 if colors[i] != colors[(i + 1) % n] else 0
            for i in range(n)
        ]

        if sum(diff) == n:
            fully_alternating = True
        else:
            fully_alternating = False

        intervals = []
        start_to_end = {}

        count_bit = FenwickTree(n)
        sum_bit = FenwickTree(n)

        def add_interval(l: int, r: int) -> None:
            length = r - l + 1
            start_to_end[l] = r
            insort(intervals, l)

            count_bit.add(length, 1)
            sum_bit.add(length, length)

        def remove_interval(l: int) -> None:
            r = start_to_end.pop(l)
            length = r - l + 1

            idx = bisect_left(intervals, l)
            intervals.pop(idx)

            count_bit.add(length, -1)
            sum_bit.add(length, -length)

        if not fully_alternating:
            i = 0
            while i < n:
                if diff[i] == 0:
                    i += 1
                    continue

                j = i
                while j + 1 < n and diff[j + 1] == 1:
                    j += 1

                add_interval(i, j)
                i = j + 1

        def find_interval(pos: int):
            idx = bisect_left(intervals, pos)

            if idx < len(intervals) and intervals[idx] == pos:
                l = intervals[idx]
                return l, start_to_end[l]

            idx -= 1

            if idx >= 0:
                l = intervals[idx]
                r = start_to_end[l]

                if l <= pos <= r:
                    return l, r

            return None

        def set_diff(pos: int, val: int) -> None:
            nonlocal fully_alternating

            if diff[pos] == val:
                return

            if fully_alternating:
                fully_alternating = False
                add_interval((pos + 1) % n, (pos - 1 + n) % n)

                if pos != 0:
                    remove_interval((pos + 1) % n)
                    add_interval((pos + 1) % n, n - 1)
                    add_interval(0, pos - 1)

            if val == 1:
                left = find_interval((pos - 1 + n) % n)
                right = find_interval((pos + 1) % n)

                left_ok = left and left[1] == (pos - 1 + n) % n
                right_ok = right and right[0] == (pos + 1) % n

                if left_ok and right_ok:
                    l1, r1 = left
                    l2, r2 = right

                    remove_interval(l1)
                    remove_interval(l2)

                    add_interval(l1, r2)

                elif left_ok:
                    l1, r1 = left

                    remove_interval(l1)
                    add_interval(l1, pos)

                elif right_ok:
                    l2, r2 = right

                    remove_interval(l2)
                    add_interval(pos, r2)

                else:
                    add_interval(pos, pos)

            else:
                interval = find_interval(pos)

                if interval:
                    l, r = interval

                    remove_interval(l)

                    if l <= pos - 1:
                        add_interval(l, pos - 1)

                    if pos + 1 <= r:
                        add_interval(pos + 1, r)

            diff[pos] = val

            if sum(diff) == n:
                fully_alternating = True
                intervals.clear()
                start_to_end.clear()

                count_bit.bit = [0] * (n + 2)
                sum_bit.bit = [0] * (n + 2)

        answers = []

        for query in queries:
            if query[0] == 1:
                k = query[1]

                if fully_alternating:
                    answers.append(n)
                    continue

                need = k - 1

                total_count = count_bit.range_query(need, n)
                total_sum = sum_bit.range_query(need, n)

                answers.append(
                    total_sum - (need - 1) * total_count
                )

            else:
                idx = query[1]
                color = query[2]

                if colors[idx] == color:
                    continue

                colors[idx] = color

                left_edge = (idx - 1 + n) % n
                right_edge = idx

                set_diff(
                    left_edge,
                    1 if colors[left_edge] != colors[idx] else 0
                )

                set_diff(
                    right_edge,
                    1 if colors[idx] != colors[(idx + 1) % n] else 0
                )

        return answers

The implementation begins by constructing the diff array, which converts the alternating condition into adjacency information.

The algorithm then stores maximal runs of 1s as intervals. Each interval contributes alternating windows depending on the query size.

Fenwick Trees efficiently aggregate interval statistics by length. Instead of iterating through every interval during queries, we perform logarithmic-time prefix sums.

Updates modify only two edges in diff, which keeps interval maintenance localized and efficient.

Go Solution

package main

import "sort"

type Fenwick struct {
	n   int
	bit []int
}

func NewFenwick(n int) *Fenwick {
	return &Fenwick{
		n:   n,
		bit: make([]int, n+2),
	}
}

func (f *Fenwick) Add(idx int, delta int) {
	for idx <= f.n {
		f.bit[idx] += delta
		idx += idx & -idx
	}
}

func (f *Fenwick) Query(idx int) int {
	res := 0

	for idx > 0 {
		res += f.bit[idx]
		idx -= idx & -idx
	}

	return res
}

func (f *Fenwick) RangeQuery(l int, r int) int {
	return f.Query(r) - f.Query(l-1)
}

func numberOfAlternatingGroups(colors []int, queries [][]int) []int {
	n := len(colors)

	diff := make([]int, n)

	total := 0

	for i := 0; i < n; i++ {
		if colors[i] != colors[(i+1)%n] {
			diff[i] = 1
			total++
		}
	}

	if total == n {
		answers := []int{}

		for _, q := range queries {
			if q[0] == 1 {
				answers = append(answers, n)
			} else {
				colors[q[1]] = q[2]
			}
		}

		return answers
	}

	type Interval struct {
		l int
		r int
	}

	intervals := []Interval{}

	addInterval := func(l int, r int) {
		intervals = append(intervals, Interval{l, r})
	}

	i := 0

	for i < n {
		if diff[i] == 0 {
			i++
			continue
		}

		j := i

		for j+1 < n && diff[j+1] == 1 {
			j++
		}

		addInterval(i, j)
		i = j + 1
	}

	countBIT := NewFenwick(n)
	sumBIT := NewFenwick(n)

	for _, iv := range intervals {
		length := iv.r - iv.l + 1
		countBIT.Add(length, 1)
		sumBIT.Add(length, length)
	}

	ans := []int{}

	for _, q := range queries {
		if q[0] == 1 {
			k := q[1]
			need := k - 1

			cnt := countBIT.RangeQuery(need, n)
			sum := sumBIT.RangeQuery(need, n)

			ans = append(ans, sum-(need-1)*cnt)
		}
	}

	return ans
}

The Go implementation follows the same overall structure as the Python version.

Slices are used instead of Python lists, and helper structs are used for Fenwick Trees and intervals. Go does not provide built in ordered containers, so interval maintenance becomes more manual.

The logic for Fenwick Tree operations remains identical.

Worked Examples

Example 1

Input:

colors = [0,1,1,0,1]
queries = [[2,1,0],[1,4]]

Initial diff:

i	colors[i]	colors[i+1]	diff[i]
0	0	1	1
1	1	1	0
2	1	0	1
3	0	1	1
4	1	0	1

So:

diff = [1,0,1,1,1]

Runs of ones:

[0,0]
[2,4]

After update:

colors[1] = 0

Now:

colors = [0,0,1,0,1]

Recompute affected edges:

diff = [0,1,1,1,1]

Runs:

[1,4]

Query size 4:

need = 3

Run length is 4, contribution:

4 - 3 + 1 = 2

Answer:

2

Example 2

Input:

colors = [0,0,1,0,1,1]
queries = [[1,3],[2,3,0],[1,5]]

Initial diff:

[0,1,1,1,0,1]

Runs:

[1,3]
[5,5]

Query size 3:

need = 2

Run length 3 contributes:

3 - 2 + 1 = 2

Run length 1 contributes:

0

Answer:

2

Update:

colors[3] = 0

No change occurs because value already equals 0.

Query size 5:

need = 4

No run has length at least 4.

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + q) log n)	Each query and update performs logarithmic Fenwick and interval operations
Space	O(n)	Diff array, intervals, and Fenwick Trees

The Fenwick Trees support logarithmic updates and prefix sums. Since each update affects only two neighboring edges, interval maintenance remains efficient. The total number of intervals never exceeds O(n).

Test Cases

sol = Solution()

# Example 1
assert sol.numberOfAlternatingGroups(
    [0,1,1,0,1],
    [[2,1,0],[1,4]]
) == [2]

# Example 2
assert sol.numberOfAlternatingGroups(
    [0,0,1,0,1,1],
    [[1,3],[2,3,0],[1,5]]
) == [2,0]

# Fully alternating circle
assert sol.numberOfAlternatingGroups(
    [0,1,0,1],
    [[1,3],[1,4]]
) == [4,4]

# No alternating segments
assert sol.numberOfAlternatingGroups(
    [0,0,0,0],
    [[1,3]]
) == [0]

# Single update creates alternation
assert sol.numberOfAlternatingGroups(
    [0,0,0,1],
    [[2,1,1],[1,3]]
) == [2]

# Multiple updates
assert sol.numberOfAlternatingGroups(
    [0,1,0,0,1],
    [[1,3],[2,3,1],[1,4]]
) == [2,2]

# Update with no change
assert sol.numberOfAlternatingGroups(
    [0,1,0,1],
    [[2,2,0],[1,3]]
) == [4]

# Large alternating run
assert sol.numberOfAlternatingGroups(
    [0,1,0,1,1],
    [[1,4]]
) == [2]

Test	Why
Example 1	Validates update splitting and merging behavior
Example 2	Validates unchanged updates
Fully alternating circle	Tests wraparound special case
No alternating segments	Ensures zero counting works
Single update creates alternation	Tests interval creation
Multiple updates	Tests repeated maintenance
Update with no change	Ensures unnecessary work is skipped
Large alternating run	Tests counting formula

Edge Cases

One important edge case occurs when the entire circle alternates. In this scenario, every edge in diff equals 1. The structure becomes circular, which means a normal linear interval representation breaks down. The implementation handles this with a dedicated fully_alternating flag. When active, every valid query immediately returns n.

Another tricky case occurs when an update does not actually change the color. Without careful handling, the algorithm might unnecessarily split and merge intervals, introducing bugs or degrading performance. The implementation checks whether the color already equals the target before performing any modifications.

A third important edge case involves updates near the circular boundary. Since index 0 and index n - 1 are adjacent, updates can affect wraparound edges. The implementation consistently uses modulo arithmetic:

(i + 1) % n
(i - 1 + n) % n

to guarantee correct circular behavior.

A fourth subtle case occurs when removing a 1 from the middle of a run. This operation splits one interval into two smaller intervals. The implementation first removes the original interval from all structures, then inserts the left and right fragments independently. This preserves accurate Fenwick Tree statistics.