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^41 <= colors[i] <= 31 <= queries.length <= 5*10^4queries[i].length == 20 <= queries[i][0] < colors.length1 <= queries[i][1] <= 3Problem 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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n * q) | O(1) | Small arrays or when implementing a quick baseline solution |
| Preprocessing with Dynamic Programming | O(n + q) | O(n) | Best overall approach when many queries must be answered efficiently |
| Index Lists + Binary Search | O(n + q log n) | O(n) | Useful when color positions are stored and queries are handled independently |
Leetcode - Shortest distance to target colour Solution • Snow_Coder • 593 views views
Watch 8 more video solutions →Practice Shortest Distance to Target Color with our built-in code editor and test cases.
Practice on FleetCode