Skip to main content
Talentd

Shortest Distance to Target Color - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary SearchDynamic Programming8 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array colors where each position contains a color (1, 2, or 3). For each query [index, color], return the shortest distance from index to any occurrence of the target color. If the color never appears, return -1.

Approach 1: Brute Force Scan (O(n * q) time, O(1) space)

For each query, scan the entire colors array and track the closest position where the target color appears. Compute the absolute distance between the query index and every matching element. Keep the minimum distance found. This works but becomes slow when both the array and query count are large because the array is repeatedly scanned for every query.

Approach 2: Preprocessing with Dynamic Programming (O(n + q) time, O(n) space)

Precompute the distance to each color from every index using two passes across the array. Maintain two arrays while scanning: one from left to right storing the nearest occurrence of each color seen so far, and another from right to left storing the nearest occurrence on the right. For each index and color, record the minimum distance from these two passes. After preprocessing, each query becomes a constant-time lookup. This technique is essentially a prefix and suffix distance DP over the array and fits naturally with array traversal and dynamic programming ideas.

Approach 3: Preprocessing with Color Positions + Binary Search (O(n + q log n) time, O(n) space)

Store the indices of each color in three separate sorted lists. When answering a query, retrieve the list for the target color and use binary search to find the closest index to the query position. Check the nearest element on the left and right of the insertion point to compute the minimum distance. This avoids scanning the array and keeps queries efficient, especially when the array is large. The approach directly leverages binary search on sorted index lists.

Recommended for interviews: The dynamic programming preprocessing approach is typically expected. It reduces the problem to two linear passes and answers queries in O(1). Starting with the brute force method shows you understand the problem constraints, while moving to preprocessing demonstrates optimization skills and strong control over array traversal patterns.

Solution

We can preprocess the distance from each position to the nearest color 1, 2, 3 on the left, and the distance from each position to the nearest color 1, 2, 3 on the right, and record them in the arrays left and right. Initially, left[0][0] = left[0][1] = left[0][2] = -infty, and right[n][0] = right[n][1] = right[n][2] = infty, where n is the length of the array colors.

Then for each query (i, c), the minimum distance is d = min(i - left[i + 1][c - 1], right[i][c - 1] - i). If d > n, there is no solution, and the answer to this query is -1.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array colors.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ScanO(n * q)O(1)Small arrays or when implementing a quick baseline solution
Preprocessing with Dynamic ProgrammingO(n + q)O(n)Best overall approach when many queries must be answered efficiently
Index Lists + Binary SearchO(n + q log n)O(n)Useful when color positions are stored and queries are handled independently

Video Solution

Leetcode - Shortest distance to target colour Solution • Snow_Coder • 593 views views

Watch 5 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Shortest Distance to Target Color with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays