Show problems as
Classic problem #2672MediumArray

Number of Adjacent Elements With the Same Color

Real-world version: Matching Neighbours on a Tile Shelf
Tracked in this browser only
Read Number of Adjacent Elements With the Same Color on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A display shelf carries n tiles in a row, numbered 0 through n - 1. Every tile starts out blank, meaning it carries no colour whatsoever.

You are given queries. Its i-th entry names a position index_i followed by a colour colour_i. Work through the queries in the order given: query i paints the tile at index_i in colour colour_i, wiping out whatever that tile carried before.

Straight after each query, count the neighbouring tile pairs that carry the same colour. Two tiles are neighbours when their positions are one apart. A pair only counts when both of its tiles have been painted, so a blank tile never takes part in a counted pair, not even alongside another blank tile.

Return answer, where answer[i] is that count taken right after query i is applied.

Examples

Example 1

Input
n = 4, queries = [[0, 2], [1, 2], [3, 2], [1, 7], [2, 7]]
Output
[0, 1, 1, 0, 1]

After the first query only tile 0 is painted, so no pair can count. The second query paints tile 1 in the same colour, giving one pair. Tile 3 is then painted but tile 2 is still blank, so the count stays at 1. Repainting tile 1 in colour 7 breaks that pair, and painting tile 2 in colour 7 forms a new one.

Example 2

Input
n = 1, queries = [[0, 5], [0, 9]]
Output
[0, 0]

A shelf of one tile has no neighbouring pairs at all, so both counts are 0.

Example 3

Input
n = 3, queries = [[0, 4], [2, 4], [1, 9]]
Output
[0, 0, 0]

Tiles 0 and 2 both carry colour 4, but they are two apart and so are not neighbours. Painting tile 1 in colour 9 matches neither of them, so every count is 0.

Constraints

  • 1 <= n <= 10^5
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= index_i <= n - 1
  • 1 <= colour_i <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def color_the_array(n: int, queries: list[list[int]]) -> list[int]:
Java
public int[] colorTheArray(int n, int[][] queries)

More on the same topics