Number of Adjacent Elements With the Same Color solution and explanation
9 more videos on this problem
Number of Adjacent Elements With the Same Color - Leetcode 2672 - PythonAlgorithms Casts · 12:00 · 1K views
Leetcode 2672. Number of Adjacent Elements With the Same Color | Weekly Contest 343 | weekly contestOffCampus Phodenge | Aman Chowdhury · 12:32 · 739 views
Number of Adjacent Elements With the Same Color | HARDER Follow-ups | Weekly Contest 344codingMohan · 36:17 · 552 views
2672. Number of Adjacent Elements With the Same Color (Leetcode Medium)Programming Live with Larry · 32:12 · 465 views
6418. Number of Adjacent Elements With the Same Color - LEETCODE WEEKLY CONTEST 344Joyjit Codes · 5:24 · 425 views
Leetcode 344 contest, problem 2672. Number of Adjacent Elements With the Same ColorAyush Rao · 7:33 · 252 views
Leetcode 2672 || Number of Adjacent Elements With the Same Color || Leetcode Weekly Medium || cppKomal Pal · 11:33 · 171 views
Leetcode 2672. Number of Adjacent Elements With the Same ColorElite Code · 30:12 · 129 views
Leetcode 2672 Number of Adjacent Elements With the Same Color leetcode weekly contest 334ADVANCED MATHEMATICS · 22:34 · 126 views
Leetcode 2672. Number of Adjacent Elements With the Same Color (dp)LetsCode · 11:12 · 123 views
The problem
You are given an integer n representing an array colors of length n where all elements are set to 0's meaning uncolored. You are also given a 2D integer array queries where queries[i] = [indexi, colori]. For the ith query:
- Set
colors[indexi]tocolori. - Count adjacent pairs in
colorsset to the same color (regardless ofcolori).
Return an array answer of the same length as queries where answer[i] is the answer to the ith query.
Example 1:
Input: n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]
Output: [0,1,1,0,2]
Explanation:
- Initially array colors = [0,0,0,0], where 0 denotes uncolored elements of the array.
- After the 1st query colors = [2,0,0,0]. The count of adjacent pairs with the same color is 0.
- After the 2nd query colors = [2,2,0,0]. The count of adjacent pairs with the same color is 1.
- After the 3rd query colors = [2,2,0,1]. The count of adjacent pairs with the same color is 1.
- After the 4th query colors = [2,1,0,1]. The count of adjacent pairs with the same color is 0.
- After the 5th query colors = [2,1,1,1]. The count of adjacent pairs with the same color is 2.
Example 2:
Input: n = 1, queries = [[0,100000]]
Output: [0]
Explanation:
After the 1st query colors = [100000]. The count of adjacent pairs with the same color is 0.
Constraints:
1 <= n <= 1051 <= queries.length <= 105queries[i].length == 20 <= indexi <= n - 11 <= colori <= 105
Approach overview
Problem Overview: You maintain an array of size n where every element starts uncolored. Each query assigns a color to an index. After every update, return how many adjacent pairs (i, i+1) currently share the same color.
The key observation: only the neighbors of the updated index can change the number of valid adjacent pairs. You never need to recompute the entire array after each query.
Approach 1: Direct Updating with Adjacent Check (Time: O(q), Space: O(n))
Maintain an array storing the current color at each index and a running counter for adjacent equal pairs. For every query (idx, color), first check if the index already had a color. If so, remove any existing contributions with neighbors idx-1 and idx+1 where the colors matched. Then update the color at idx and re-check the same neighbors to add back any new matches. Each query performs constant work: two neighbor comparisons and a few counter updates. This makes the total time O(q) for q queries, with O(n) space for the color array. This approach is essentially a small array simulation where updates affect only local state.
Approach 2: Optimized Verification with Lazy Initialization (Time: O(q), Space: O(n))
Instead of initializing the entire array with a default color, store a sentinel value such as -1 to represent an uncolored position and treat it as invalid during comparisons. When processing a query, skip neighbor checks if the neighbor is still uncolored. This avoids unnecessary comparisons early in the process and keeps the logic explicit: only colored cells participate in adjacency counts. The algorithm still performs constant work per query, so the time complexity remains O(q) with O(n) space. Conceptually this is the same incremental update strategy but with cleaner handling of uninitialized cells.
Both approaches rely on the same insight: recomputing the entire array after each update would be O(nq), which is unnecessary. Only two potential adjacent pairs can change when a single index is recolored.
Recommended for interviews: Approach 1 is what interviewers expect. It demonstrates that you recognize the local impact of an update and maintain a running count instead of recomputing from scratch. Explaining why only idx-1 and idx+1 matter shows strong understanding of array state updates and incremental simulation. The lazy initialization variation is a small optimization but the core idea—subtract old matches, update, then add new matches—is the important part.
Approach 1: Approach 1: Direct Updating with Adjacent Check
We iterate through each query, updating the color of the given index in the colors array. After each update, we check the color of the neighboring elements (left and right) to determine if there is an increase or decrease in the count of adjacent similar colors. This direct checking ensures we update our result efficiently.
def colorQueries(n, queries):
colors = [0] * n
result = []
count = 0
for query in queries:
index, new_color = query
if index > 0 and colors[index] == colors[index - 1]:
count -= 1
if index < n - 1 and colors[index] == colors[index + 1]:
count -= 1
colors[index] = new_color
if index > 0 and colors[index] == colors[index - 1]:
count += 1
if index < n - 1 and colors[index] == colors[index + 1]:
count += 1
result.append(count)
return result
n = 4
queries = [[0,2], [1,2], [3,1], [1,1], [2,1]]
print(colorQueries(n, queries))import java.util.*;
public class ColorQueries {
public static int[] colorQueries(int n, int[][] queries) {
int[] colors = new int[n];
int[] result = new int[queries.length];
int count = 0;
for (int i = 0; i < queries.length; i++) {
int index = queries[i][0];
int new_color = queries[i][1];
if (index > 0 && colors[index] == colors[index - 1]) count--;
if (index < n - 1 && colors[index] == colors[index + 1]) count--;
colors[index] = new_color;
if (index > 0 && colors[index] == colors[index - 1]) count++;
if (index < n - 1 && colors[index] == colors[index + 1]) count++;
result[i] = count;
}
return result;
}
public static void main(String[] args) {
int n = 4;
int[][] queries = {{0,2},{1,2},{3,1},{1,1},{2,1}};
int[] answer = colorQueries(n, queries);
System.out.println(Arrays.toString(answer));
}
}#include <vector>
#include <iostream>
std::vector<int> colorQueries(int n, std::vector<std::vector<int>>& queries) {
std::vector<int> colors(n, 0);
std::vector<int> result;
int count = 0;
for (auto& query : queries) {
int index = query[0];
int new_color = query[1];
if (index > 0 && colors[index] == colors[index - 1]) count--;
if (index < n - 1 && colors[index] == colors[index + 1]) count--;
colors[index] = new_color;
if (index > 0 && colors[index] == colors[index - 1]) count++;
if (index < n - 1 && colors[index] == colors[index + 1]) count++;
result.push_back(count);
}
return result;
}
int main() {
int n = 4;
std::vector<std::vector<int>> queries = {{0,2},{1,2},{3,1},{1,1},{2,1}};
std::vector<int> result = colorQueries(n, queries);
for (int r : result) {
std::cout << r << " ";
}
std::cout << std::endl;
return 0;
}function colorQueries(n, queries) {
const colors = new Array(n).fill(0);
const result = [];
let count = 0;
for (const [index, new_color] of queries) {
if (index > 0 && colors[index] === colors[index - 1]) count--;
if (index < n - 1 && colors[index] === colors[index + 1]) count--;
colors[index] = new_color;
if (index > 0 && colors[index] === colors[index - 1]) count++;
if (index < n - 1 && colors[index] === colors[index + 1]) count++;
result.push(count);
}
return result;
}
const n = 4;
const queries = [[0,2], [1,2], [3,1], [1,1], [2,1]];
console.log(colorQueries(n, queries).join(", "));#include <stdio.h>
#include <stdlib.h>
int* colorQueries(int n, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
int* colors = (int*)calloc(n, sizeof(int));
int* result = (int*)malloc(queriesSize * sizeof(int));
int count = 0;
for (int k = 0; k < queriesSize; k++) {
int index = queries[k][0];
int new_color = queries[k][1];
// Check left
if (index > 0 && colors[index] == colors[index - 1]) count--;
// Check right
if (index < n - 1 && colors[index] == colors[index + 1]) count--;
// Update the color
colors[index] = new_color;
// Check left again
if (index > 0 && colors[index] == colors[index - 1]) count++;
// Check right again
if (index < n - 1 && colors[index] == colors[index + 1]) count++;
result[k] = count;
}
*returnSize = queriesSize;
return result;
}
int main() {
// Example usage
int n = 4;
int queries[5][2] = {{0,2},{1,2},{3,1},{1,1},{2,1}};
int* queriesColSize = (int*)malloc(5 * sizeof(int));
for(int i = 0; i < 5; i++) {
queriesColSize[i] = 2;
}
int returnSize;
int** qPtr = (int**)malloc(5 * sizeof(int*));
for(int i = 0; i < 5; i++) {
qPtr[i] = queries[i];
}
int* result = colorQueries(n, qPtr, 5, queriesColSize, &returnSize);
for(int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
printf("\n");
free(queriesColSize);
free(qPtr);
free(result);
return 0;
}using System;
public class ColorQueries {
public static int[] ColorQueryResults(int n, int[][] queries) {
int[] colors = new int[n];
int[] result = new int[queries.Length];
int count = 0;
for (int i = 0; i < queries.Length; i++) {
int index = queries[i][0];
int newColor = queries[i][1];
if (index > 0 && colors[index] == colors[index - 1]) count--;
if (index < n - 1 && colors[index] == colors[index + 1]) count--;
colors[index] = newColor;
if (index > 0 && colors[index] == colors[index - 1]) count++;
if (index < n - 1 && colors[index] == colors[index + 1]) count++;
result[i] = count;
}
return result;
}
public static void Main() {
int n = 4;
int[][] queries = new int[][] { new int[] {0, 2}, new int[] {1, 2}, new int[] {3, 1}, new int[] {1, 1}, new int[] {2, 1} };
int[] answer = ColorQueryResults(n, queries);
Console.WriteLine(string.Join(", ", answer));
}
}The Python solution makes use of a list to store the color states of elements in the original array. As we process each query, similar adjacent pairs are adjusted by comparing colors of immediate neighbors.
Time Complexity: O(len(queries)) as it processes each query in constant time.
Space Complexity: O(n) for the color list.
Approach 2: Approach 2: Optimized Verification with Lazy Initialization
This approach optimizes the process by using lazy initialization. Instead of resetting counts each time, it uses previous state data. Before updating an element, adjacent pairs are compared, and only necessary changes are tracked and updated in the adjacent count.
def optimizedColorQueries(n, queries):
colors = [0] * n
result = []
count = 0
for query in queries:
index, new_color = query
left_same = (index > 0 and colors[index] == colors[index - 1])
right_same = (index < n - 1 and colors[index] == colors[index + 1])
count -= int(left_same) + int(right_same)
colors[index] = new_color
left_same = (index > 0 and colors[index] == colors[index - 1])
right_same = (index < n - 1 and colors[index] == colors[index + 1])
count += int(left_same) + int(right_same)
result.append(count)
return result
n = 4
queries = [[0,2], [1,2], [3,1], [1,1], [2,1]]
print(optimizedColorQueries(n, queries))import java.util.*;
public class OptimizedColorQueries {
public static int[] optimizedColorQueries(int n, int[][] queries) {
int[] colors = new int[n];
int[] result = new int[queries.length];
int count = 0;
for (int i = 0; i < queries.length; i++) {
int index = queries[i][0];
int new_color = queries[i][1];
boolean left_same = (index > 0 && colors[index] == colors[index - 1]);
boolean right_same = (index < n - 1 && colors[index] == colors[index + 1]);
count -= (left_same ? 1 : 0) + (right_same ? 1 : 0);
colors[index] = new_color;
left_same = (index > 0 && colors[index] == colors[index - 1]);
right_same = (index < n - 1 && colors[index] == colors[index + 1]);
count += (left_same ? 1 : 0) + (right_same ? 1 : 0);
result[i] = count;
}
return result;
}
public static void main(String[] args) {
int n = 4;
int[][] queries = {{0,2},{1,2},{3,1},{1,1},{2,1}};
int[] answer = optimizedColorQueries(n, queries);
System.out.println(Arrays.toString(answer));
}
}#include <vector>
#include <iostream>
std::vector<int> optimizedColorQueries(int n, std::vector<std::vector<int>>& queries) {
std::vector<int> colors(n, 0);
std::vector<int> result;
int count = 0;
for (auto& query : queries) {
int index = query[0];
int new_color = query[1];
bool left_same = (index > 0 && colors[index] == colors[index - 1]);
bool right_same = (index < n - 1 && colors[index] == colors[index + 1]);
count -= left_same + right_same;
colors[index] = new_color;
left_same = (index > 0 && colors[index] == colors[index - 1]);
right_same = (index < n - 1 && colors[index] == colors[index + 1]);
count += left_same + right_same;
result.push_back(count);
}
return result;
}
int main() {
int n = 4;
std::vector<std::vector<int>> queries = {{0,2},{1,2},{3,1},{1,1},{2,1}};
std::vector<int> result = optimizedColorQueries(n, queries);
for (int r : result) {
std::cout << r << " ";
}
std::cout << std::endl;
return 0;
}function optimizedColorQueries(n, queries) {
const colors = new Array(n).fill(0);
const result = [];
let count = 0;
for (const [index, new_color] of queries) {
let left_same = (index > 0 && colors[index] === colors[index - 1]);
let right_same = (index < n - 1 && colors[index] === colors[index + 1]);
count -= left_same + right_same;
colors[index] = new_color;
left_same = (index > 0 && colors[index] === colors[index - 1]);
right_same = (index < n - 1 && colors[index] === colors[index + 1]);
count += left_same + right_same;
result.push(count);
}
return result;
}
const n = 4;
const queries = [[0,2], [1,2], [3,1], [1,1], [2,1]];
console.log(optimizedColorQueries(n, queries).join(", "));#include <stdio.h>
#include <stdlib.h>
int* optimizedColorQueries(int n, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
int* colors = (int*)calloc(n, sizeof(int));
int* result = (int*)malloc(queriesSize * sizeof(int));
int count = 0;
for (int k = 0; k < queriesSize; k++) {
int index = queries[k][0];
int new_color = queries[k][1];
int left_same = (index > 0 && colors[index] == colors[index - 1]);
int right_same = (index < n - 1 && colors[index] == colors[index + 1]);
count -= left_same + right_same;
colors[index] = new_color;
left_same = (index > 0 && colors[index] == colors[index - 1]);
right_same = (index < n - 1 && colors[index] == colors[index + 1]);
count += left_same + right_same;
result[k] = count;
}
*returnSize = queriesSize;
return result;
}
int main() {
// Example usage
int n = 4;
int queries[5][2] = {{0,2},{1,2},{3,1},{1,1},{2,1}};
int* queriesColSize = (int*)malloc(5 * sizeof(int));
for(int i = 0; i < 5; i++) {
queriesColSize[i] = 2;
}
int returnSize;
int** qPtr = (int**)malloc(5 * sizeof(int*));
for(int i = 0; i < 5; i++) {
qPtr[i] = queries[i];
}
int* result = optimizedColorQueries(n, qPtr, 5, queriesColSize, &returnSize);
for(int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
printf("\n");
free(queriesColSize);
free(qPtr);
free(result);
return 0;
}using System;
public class OptimizedColorQueries {
public static int[] OptimizedQueryResults(int n, int[][] queries) {
int[] colors = new int[n];
int[] result = new int[queries.Length];
int count = 0;
for (int i = 0; i < queries.Length; i++) {
int index = queries[i][0];
int newColor = queries[i][1];
bool leftSame = (index > 0 && colors[index] == colors[index - 1]);
bool rightSame = (index < n - 1 && colors[index] == colors[index + 1]);
count -= (leftSame ? 1 : 0) + (rightSame ? 1 : 0);
colors[index] = newColor;
leftSame = (index > 0 && colors[index] == colors[index - 1]);
rightSame = (index < n - 1 && colors[index] == colors[index + 1]);
count += (leftSame ? 1 : 0) + (rightSame ? 1 : 0);
result[i] = count;
}
return result;
}
public static void Main() {
int n = 4;
int[][] queries = new int[][] { new int[] {0, 2}, new int[] {1, 2}, new int[] {3, 1}, new int[] {1, 1}, new int[] {2, 1} };
int[] answer = OptimizedQueryResults(n, queries);
Console.WriteLine(string.Join(", ", answer));
}
}Python's lazy calculation technique checks only around the area influenced by each query, which makes each operation more performant compared to resetting all counts, especially with consecutive similar modifications.
Time Complexity: O(len(queries)) given minimized per-query operations.
Space Complexity: O(n) for the list of colors.
Approach 3: Default Approach
function colorTheArray(n: number, queries: number[][]): number[] {
const nums: number[] = new Array(n).fill(0);
const ans: number[] = [];
let x = 0;
for (const [i, c] of queries) {
if (i > 0 && nums[i] > 0 && nums[i - 1] == nums[i]) {
--x;
}
if (i < n - 1 && nums[i] > 0 && nums[i + 1] == nums[i]) {
--x;
}
if (i > 0 && nums[i - 1] == c) {
++x;
}
if (i < n - 1 && nums[i + 1] == c) {
++x;
}
ans.push(x);
nums[i] = c;
}
return ans;
}func colorTheArray(n int, queries [][]int) (ans []int) {
nums := make([]int, n)
x := 0
for _, q := range queries {
i, c := q[0], q[1]
if i > 0 && nums[i] > 0 && nums[i-1] == nums[i] {
x--
}
if i < n-1 && nums[i] > 0 && nums[i+1] == nums[i] {
x--
}
if i > 0 && nums[i-1] == c {
x++
}
if i < n-1 && nums[i+1] == c {
x++
}
ans = append(ans, x)
nums[i] = c
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Direct Updating with Adjacent Check | Time Complexity: Space Complexity: |
| Approach 2: Optimized Verification with Lazy Initialization | Time Complexity: Space Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Updating with Adjacent Check | O(q) | O(n) | Best general solution. Maintain a running count and update only affected neighbors. |
| Optimized Verification with Lazy Initialization | O(q) | O(n) | Useful when you want clearer handling of uncolored indices using sentinel values. |
Frequently asked questions
Is Number of Adjacent Elements With the Same Color easy or hard?
The problem is rated Medium because the implementation requires careful handling of updates and edge cases such as recoloring an already colored index. The core logic is simple once you realize only adjacent neighbors can affect the answer after each query.
Number of Adjacent Elements With the Same Color Python/Java solution
Implementations in Python or Java follow the same idea: store colors in an array, keep a running adjacency counter, and update neighbor relationships on every query. Each query checks indices i-1 and i+1 before and after recoloring. This produces an O(q) time solution with O(n) space.
How to solve Number of Adjacent Elements With the Same Color in O(n)?
Maintain an array of colors and a variable storing the number of adjacent equal pairs. For each query, subtract matches formed by the old color with neighbors, update the color, then check neighbors again to add new matches. Because only two pairs can change per update, each query takes O(1) time.
What is the best approach for Number of Adjacent Elements With the Same Color?
The best approach keeps a running count of adjacent equal pairs and updates it locally after each query. When recoloring index i, check only neighbors i-1 and i+1. Remove previous matches involving the old color, assign the new color, then add new matches. This runs in O(q) time for q queries with O(n) space.
Is Number of Adjacent Elements With the Same Color asked at Google/Amazon/Meta?
Problems with incremental array updates and adjacency tracking appear frequently in interviews at large tech companies. Variants of this pattern—maintaining counts while processing updates—have been reported in interviews at companies like Amazon and Google because they test state management and edge-case handling.
What data structure is used in Number of Adjacent Elements With the Same Color?
The primary data structure is a simple array storing the current color of each index. The algorithm also maintains a single integer counter tracking adjacent equal pairs. No complex structures are required because each update affects only neighboring elements.
What is the time complexity of Number of Adjacent Elements With the Same Color?
The optimal solution runs in O(q) time where q is the number of queries. Each query performs constant work by checking at most two neighbors and updating a counter. Space complexity is O(n) to store the current color of each array position.