Alternating Groups I — Solution in Python, Java & C++
Alternating Groups I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Alternating Groups I is an easy coding problem on arrays and sliding window, asked in Amazon, Google and Paytm interviews.
- Difficulty: Easy
- Topics: Arrays, Sliding Window
- Asked at: Amazon, Google, Paytm
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Tiles are arranged in a circle, coloured red (0) or blue (1). An alternating group is three contiguous tiles — wrapping around the circle — whose middle tile differs in colour from both of its neighbours.
Return the number of alternating groups.
Example 1
Input: colors = [1,1,1]
Output: 0
Explanation: Every tile matches its neighbours.
Example 2
Input: colors = [0,1,0,0,1]
Output: 3
Example 3
Input: colors = [0,1,0,1]
Output: 4
Explanation: A fully alternating circle: every tile is the middle of a group.
Constraints
3 <= colors.length <= 100colors[i] is either 0 or 1.
Hints for Alternating Groups I
Hint 1
Centre a window on each tile in turn.
Hint 2
Wrapping is handled by indexing modulo the length.
Hint 3
A group is alternating exactly when the middle differs from both sides.
How to solve Alternating Groups I
Every tile is the middle of exactly one group, so scan the tiles and count those that differ from both neighbours, indexing modulo n to close the circle.
Approach
- For each index
i, readcolors[(i - 1 + n) % n]andcolors[(i + 1) % n]. - Count
iwhen its colour differs from both.
Why it works
Adding n before the modulus is what keeps the left index correct at i == 0, since a plain -1 % n is negative in most languages. Counting by middle tile rather than by window start makes each group counted exactly once.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- A plain
(i - 1) % ngoes negative at the start of the array. - With only two colours, "differs from both neighbours" also means the neighbours match each other.
- The circle means there are
ngroups to consider, notn - 2.
Reference solution
Python
from typing import List
def numberOfAlternatingGroups(colors: List[int]) -> int:
n = len(colors)
count = 0
for i in range(n):
left = colors[(i - 1) % n]
right = colors[(i + 1) % n]
if colors[i] != left and colors[i] != right:
count += 1
return countJava
public static int numberOfAlternatingGroups(int[] colors) {
int n = colors.length, count = 0;
for (int i = 0; i < n; i++) {
int left = colors[(i - 1 + n) % n];
int right = colors[(i + 1) % n];
if (colors[i] != left && colors[i] != right) count++;
}
return count;
}C++
int numberOfAlternatingGroups(vector<int>& colors) {
int n = (int) colors.size(), count = 0;
for (int i = 0; i < n; i++) {
int left = colors[(i - 1 + n) % n];
int right = colors[(i + 1) % n];
if (colors[i] != left && colors[i] != right) count++;
}
return count;
}JavaScript
var numberOfAlternatingGroups = function(colors) {
var n = colors.length, count = 0;
for (var i = 0; i < n; i++) {
var left = colors[(i - 1 + n) % n];
var right = colors[(i + 1) % n];
if (colors[i] !== left && colors[i] !== right) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sliding Window Technique