1182. Shortest Distance to Target Color Solution

The problem

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.

Python

class Solution:
    def shortestDistanceColor(
        self, colors: List[int], queries: List[List[int]]
    ) -> List[int]:
        n = len(colors)
        right = [[inf] * 3 for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(3):
                right[i][j] = right[i + 1][j]
            right[i][colors[i] - 1] = i
        left = [[-inf] * 3 for _ in range(n + 1)]
        for i, c in enumerate(colors, 1):
            for j in range(3):
                left[i][j] = left[i - 1][j]
            left[i][c - 1] = i - 1
        ans = []
        for i, c in queries:
            d = min(i - left[i + 1][c - 1], right[i][c - 1] - i)
            ans.append(-1 if d > n else d)
        return ans

Java

class Solution {
    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
        int n = colors.length;
        final int inf = 1 << 30;
        int[][] right = new int[n + 1][3];
        Arrays.fill(right[n], inf);
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j < 3; ++j) {
                right[i][j] = right[i + 1][j];
            }
            right[i][colors[i] - 1] = i;
        }
        int[][] left = new int[n + 1][3];
        Arrays.fill(left[0], -inf);
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 3; ++j) {
                left[i][j] = left[i - 1][j];
            }
            left[i][colors[i - 1] - 1] = i - 1;
        }
        List<Integer> ans = new ArrayList<>();
        for (int[] q : queries) {
            int i = q[0], c = q[1] - 1;
            int d = Math.min(i - left[i + 1][c], right[i][c] - i);
            ans.add(d > n ? -1 : d);
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
        int n = colors.size();
        int right[n + 1][3];
        const int inf = 1 << 30;
        fill(right[n], right[n] + 3, inf);
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j < 3; ++j) {
                right[i][j] = right[i + 1][j];
            }
            right[i][colors[i] - 1] = i;
        }
        int left[n + 1][3];
        fill(left[0], left[0] + 3, -inf);
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 3; ++j) {
                left[i][j] = left[i - 1][j];
            }
            left[i][colors[i - 1] - 1] = i - 1;
        }
        vector<int> ans;
        for (auto& q : queries) {
            int i = q[0], c = q[1] - 1;
            int d = min(i - left[i + 1][c], right[i][c] - i);
            ans.push_back(d > n ? -1 : d);
        }
        return ans;
    }
};

TypeScript

function shortestDistanceColor(colors: number[], queries: number[][]): number[] {
    const n = colors.length;
    const inf = 1 << 30;
    const right: number[][] = Array(n + 1)
        .fill(0)
        .map(() => Array(3).fill(inf));
    const left: number[][] = Array(n + 1)
        .fill(0)
        .map(() => Array(3).fill(-inf));
    for (let i = n - 1; i >= 0; --i) {
        for (let j = 0; j < 3; ++j) {
            right[i][j] = right[i + 1][j];
        }
        right[i][colors[i] - 1] = i;
    }
    for (let i = 1; i <= n; ++i) {
        for (let j = 0; j < 3; ++j) {
            left[i][j] = left[i - 1][j];
        }
        left[i][colors[i - 1] - 1] = i - 1;
    }
    const ans: number[] = [];
    for (const [i, c] of queries) {
        const d = Math.min(i - left[i + 1][c - 1], right[i][c - 1] - i);
        ans.push(d > n ? -1 : d);
    }
    return ans;
}

func shortestDistanceColor(colors []int, queries [][]int) (ans []int) {
	n := len(colors)
	const inf = 1 << 30
	right := make([][3]int, n+1)
	left := make([][3]int, n+1)
	right[n] = [3]int{inf, inf, inf}
	left[0] = [3]int{-inf, -inf, -inf}
	for i := n - 1; i >= 0; i-- {
		for j := 0; j < 3; j++ {
			right[i][j] = right[i+1][j]
		}
		right[i][colors[i]-1] = i
	}
	for i := 1; i <= n; i++ {
		for j := 0; j < 3; j++ {
			left[i][j] = left[i-1][j]
		}
		left[i][colors[i-1]-1] = i - 1
	}
	for _, q := range queries {
		i, c := q[0], q[1]-1
		d := min(i-left[i+1][c], right[i][c]-i)
		if d > n {
			d = -1
		}
		ans = append(ans, d)
	}
	return
}

Try this approach in the editor

Complexity analysis

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

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.

Shortest Distance to Target Color solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Shortest Distance to Target Color solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems