Is Shortest Distance to Target Color easy or hard?

Shortest Distance to Target Color is rated Medium. The brute force idea is straightforward, but the optimal solution requires recognizing that preprocessing distances allows queries to be answered instantly.

Shortest Distance to Target Color Python/Java solution

Most implementations preprocess distances using arrays and two passes. The same logic works across Python, Java, C++, Go, and TypeScript. After building the distance tables, each query returns the stored value in constant time.

How to solve Shortest Distance to Target Color in O(n)?

Use preprocessing with two linear passes. During the first pass, track the most recent index of each color from the left. During the second pass, track occurrences from the right and update the minimum distance. After this preprocessing, each query simply returns the stored distance in O(1).

What is the best approach for Shortest Distance to Target Color?

The optimal approach is preprocessing the array using two dynamic programming passes. One pass scans left to right and another scans right to left to track the nearest occurrence of each color. This allows every query to be answered in O(1) time after O(n) preprocessing.

Is Shortest Distance to Target Color asked at Google/Amazon/Meta?

Shortest Distance to Target Color is a medium-level array and preprocessing problem similar to questions asked in companies like Google, Amazon, and Meta. It tests array traversal, preprocessing strategies, and efficient query handling.

What data structure is used in Shortest Distance to Target Color?

The common solution uses arrays for preprocessing distances and sometimes hash maps or lists to store indices of each color. When using the alternative approach, binary search is applied on sorted index lists for each color.

What is the time complexity of Shortest Distance to Target Color?

The optimal solution runs in O(n + q) time where n is the number of elements in the colors array and q is the number of queries. Preprocessing takes O(n) and each query is answered in constant time. Space complexity is O(n) for storing precomputed distances.

Description Hints 3 Solution Video 10:02

1182. Shortest Distance to Target Color

Medium56.5% acceptance1 companyPremium elsewhere, free here

You are given an array colors, in which there are three colors: 1, 2 and 3.

You are also given some queries. Each query consists of two integers i and c, return the shortest distance between the given index i and the target color c. If there is no solution return -1.

Example 1:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

Example 2:

Input: colors = [1,2], queries = [[0,3]]
Output: [-1]
Explanation: There is no 3 in the array.

Constraints:

1 <= colors.length <= 5*10^4
1 <= colors[i] <= 3
1 <= queries.length <= 5*10^4
queries[i].length == 2
0 <= queries[i][0] < colors.length
1 <= queries[i][1] <= 3

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Greedy solution is too slow because of the limits.

Hint 2

Can you solve this problem offline by doing some pre-processing?

Hint 3

Calculate the answers for all indexes moving to their left and to their right.

10:02

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,1,2,1,3,2,2,3,3]
[[1,3],[2,2],[6,1]]

Input

[1,2]
[[0,3]]

Your code is saved on this device.Solution