Nearest Can of a Given Color

Medium

Paint cans stand in a row on a shelf; paints[i] is the color of the can at position i. There are only three colors: 1, 2 and 3. Each query queries[j] = [i, c] asks how close to position i the nearest can of color c is. The distance between positions a and b is |a - b|; if position i already holds color c, the answer is 0. If the shelf has no can of color c at all, the answer is -1. Return the answers to the queries in order.

Example 1

paints=[3, 1, 1, 2, 3, 1], queries=[[0, 2], [3, 3], [5, 1], [2, 3]] → [3, 1, 0, 2]

From 0 to the nearest color 2 (index 3) is 3 steps. From 3, color 3 is one step away at index 4. Index 5 is color 1 itself, so 0. From 2, color 3 sits at index 0 or 4, 2 steps either way.

Example 2

paints=[2, 2, 1], queries=[[1, 3], [0, 1]] → [-1, 2]

Color 3 never appears, so the answer is -1. The nearest color 1 from index 0 is at index 2.

Constraints

1 ≤ len(paints) ≤ 5·10⁴
paints[i] ∈ {1, 2, 3}
1 ≤ len(queries) ≤ 5·10⁴
queries[j] = [i, c], 0 ≤ i < len(paints), c ∈ {1, 2, 3}

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Dynamic Programming

Similar problems

Longest Rising Selection Medium Longest Shared Run Medium Words Hidden in a Text Medium Longest Equal-Gap Chain Medium Two Separate Segments With a Given Sum Medium

Input

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

Expected

[3, 1, 0, 2]

Run checks the first 3 tests in your browser. Submit checks all 91 tests on the server, hidden ones included.