LeetCode 1182 - Shortest Distance to Target Color

LeetCode Problem 1182

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Dynamic Programming

Solution

Problem Understanding

The problem gives us an array called colors, where each position contains one of three possible values: 1, 2, or 3. Each value represents a color assigned to that index.

We are also given a list of queries. Every query contains two integers:

• i, the starting index
• c, the target color we want to find

For each query, we must determine the minimum distance between index i and any position in the array whose value equals c.

Distance is measured using absolute index difference:

$$|i - j|$$

where j is an index such that:

$$colors[j] = c$$

If the target color does not exist anywhere in the array, the answer for that query is -1.

For example, if:

colors = [1,1,2,1,3,2,2,3,3]

and the query is:

[1,3]

then we start at index 1 and search for the nearest 3. The closest 3 appears at index 4, so the distance is:

$$|1 - 4| = 3$$

The constraints are important:

• colors.length can be as large as 5 * 10^4
• queries.length can also be as large as 5 * 10^4

A naive solution that scans the entire array for every query could require:

$$5 \times 10^4 \times 5 \times 10^4 = 2.5 \times 10^9$$

operations in the worst case, which is far too slow.

The fact that there are only three possible colors is a strong hint that preprocessing can help us answer queries efficiently.

Several edge cases are important:

• The target color may not exist at all
• The queried index itself may already contain the target color
• The closest matching color could appear either to the left or to the right
• Multiple occurrences of the same color may exist
• The array may contain only one distinct color

A correct solution must handle all of these efficiently.

Approaches

Brute Force Approach

The most straightforward approach is to process each query independently.

For every query [i, c], we scan the entire colors array and look for indices where the value equals c. For every matching index, we compute the distance from i and keep track of the minimum.

This approach is correct because it explicitly checks every possible candidate position for the target color. Since the minimum distance among all valid positions is computed, the result is guaranteed to be accurate.

However, this method is inefficient. If there are n elements and q queries, then in the worst case we perform a full scan of the array for every query.

The complexity becomes:

$$O(n \times q)$$

With both values potentially equal to 5 * 10^4, this is too slow.

Optimal Approach, Preprocessing with Binary Search

The key observation is that the array itself never changes. Only the queries change.

Instead of repeatedly scanning the array, we can preprocess the positions of each color.

We store:

• all indices containing color 1
• all indices containing color 2
• all indices containing color 3

For example:

colors = [1,1,2,1,3,2,2,3,3]

becomes:

1 -> [0,1,3]
2 -> [2,5,6]
3 -> [4,7,8]

Now each query becomes:

• retrieve the sorted list of positions for color c
• use binary search to locate the closest position to index i

Because the positions are naturally stored in sorted order, binary search allows us to find the nearest candidate efficiently.

For each query, we only need to examine:

• the first position greater than or equal to i
• the position immediately before it

One of those two must contain the closest occurrence.

This reduces query time from O(n) to O(log n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × q)	O(1)	Scan the entire array for every query
Optimal	O(n + q log n)	O(n)	Preprocess indices and answer queries with binary search

Algorithm Walkthrough

1. Create a mapping from each color to a list of indices where that color appears.

We iterate through the colors array once. For every index, we append the index into the corresponding color list.

Example:

colors = [1,1,2,1,3,2,2,3,3]

produces:

1 -> [0,1,3]
2 -> [2,5,6]
3 -> [4,7,8]

These lists are automatically sorted because we traverse the array from left to right. 2. Process each query independently.

For a query [i, c], retrieve the list of indices corresponding to color c. 3. Handle the case where the color does not exist.

If the list is empty, append -1 to the answer list because no valid position exists. 4. Use binary search to locate the insertion position for index i.

We use binary search to find the first index in the positions list that is greater than or equal to i.

Suppose:

positions = [4,7,8]
i = 6

Binary search returns position 1, corresponding to value 7. 5. Check the candidate on the right.

If the insertion index is valid, compute:

abs(positions[idx] - i)

6. Check the candidate on the left.

The nearest occurrence could also lie immediately before the insertion point.

If idx > 0, compute:

abs(positions[idx - 1] - i)

7. Take the minimum of the valid distances.

The closest occurrence must be one of these two neighbors because the list is sorted. 8. Append the result to the answer list. 9. Return the completed result list after all queries are processed.

Why it works

The preprocessing step stores all occurrences of each color in sorted order. Binary search identifies the exact position where the query index would fit in that sorted order. Since all positions to the left are smaller and all positions to the right are larger, the nearest valid occurrence must be either the insertion position or the immediately preceding position. Checking both guarantees that the minimum possible distance is found.

Python Solution

from bisect import bisect_left
from collections import defaultdict
from typing import List

class Solution:
    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        color_positions = defaultdict(list)

        for index, color in enumerate(colors):
            color_positions[color].append(index)

        result = []

        for index, target_color in queries:
            positions = color_positions[target_color]

            if not positions:
                result.append(-1)
                continue

            insert_pos = bisect_left(positions, index)

            min_distance = float("inf")

            if insert_pos < len(positions):
                min_distance = min(
                    min_distance,
                    abs(positions[insert_pos] - index)
                )

            if insert_pos > 0:
                min_distance = min(
                    min_distance,
                    abs(positions[insert_pos - 1] - index)
                )

            result.append(min_distance)

        return result

The implementation begins by constructing a dictionary where each color maps to a list of indices where that color appears. Since the array is traversed from left to right, the indices are automatically stored in sorted order.

For every query, the algorithm retrieves the positions list associated with the target color. If the list is empty, the target color does not exist in the array, so -1 is appended immediately.

The bisect_left function performs binary search on the sorted positions list. It returns the first location where the query index could be inserted while preserving sorted order.

The closest occurrence can only be:

• the element at the insertion position
• the element immediately before it

The code checks both candidates carefully while ensuring indices stay within bounds.

The minimum valid distance is appended to the result list, and the final answers are returned after all queries are processed.

Go Solution

package main

import (
	"math"
	"sort"
)

func shortestDistanceColor(colors []int, queries [][]int) []int {
	colorPositions := make(map[int][]int)

	for index, color := range colors {
		colorPositions[color] = append(colorPositions[color], index)
	}

	result := make([]int, 0, len(queries))

	for _, query := range queries {
		index := query[0]
		targetColor := query[1]

		positions := colorPositions[targetColor]

		if len(positions) == 0 {
			result = append(result, -1)
			continue
		}

		insertPos := sort.SearchInts(positions, index)

		minDistance := math.MaxInt32

		if insertPos < len(positions) {
			distance := positions[insertPos] - index
			if distance < minDistance {
				minDistance = distance
			}
		}

		if insertPos > 0 {
			distance := index - positions[insertPos-1]
			if distance < minDistance {
				minDistance = distance
			}
		}

		result = append(result, minDistance)
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python version.

Instead of Python's bisect_left, Go uses sort.SearchInts, which performs binary search on a sorted slice.

Go slices naturally handle dynamic storage for the position lists. Since indices are always non-negative and bounded by array size, integer overflow is not a concern here.

The implementation uses math.MaxInt32 as the initial sentinel value for the minimum distance.

Worked Examples

Example 1

colors = [1,1,2,1,3,2,2,3,3]
queries = [[1,3],[2,2],[6,1]]

Preprocessing Step

Color	Positions
1	[0,1,3]
2	[2,5,6]
3	[4,7,8]

Query 1: [1,3]

We search for the nearest 3 from index 1.

positions = [4,7,8]

Binary search for 1:

Step	Value
insertion position	0
right candidate	4
distance	3

No left candidate exists.

Answer:

3

Query 2: [2,2]

positions = [2,5,6]

Binary search for 2:

Step	Value
insertion position	0
right candidate	2
distance	0

Answer:

0

Query 3: [6,1]

positions = [0,1,3]

Binary search for 6:

Step	Value
insertion position	3
left candidate	3
distance	3

Answer:

3

Final result:

[3,0,3]

Example 2

colors = [1,2]
queries = [[0,3]]

Preprocessing

Color	Positions
1	[0]
2	[1]
3	[]

For query [0,3]:

positions = []

Since color 3 does not exist, return:

-1

Final result:

[-1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + q log n)	Preprocessing takes O(n), each query uses binary search
Space	O(n)	Stores all indices grouped by color

The preprocessing phase scans the array exactly once, producing linear complexity. Each query performs a binary search on one of the color position lists, which requires logarithmic time. Since there are q queries, total query processing costs O(q log n).

The additional space usage comes from storing every index exactly once across the three lists.

Test Cases

from typing import List

class Solution:
    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        from bisect import bisect_left
        from collections import defaultdict

        color_positions = defaultdict(list)

        for index, color in enumerate(colors):
            color_positions[color].append(index)

        result = []

        for index, target_color in queries:
            positions = color_positions[target_color]

            if not positions:
                result.append(-1)
                continue

            insert_pos = bisect_left(positions, index)

            min_distance = float("inf")

            if insert_pos < len(positions):
                min_distance = min(min_distance, abs(positions[insert_pos] - index))

            if insert_pos > 0:
                min_distance = min(min_distance, abs(positions[insert_pos - 1] - index))

            result.append(min_distance)

        return result

solution = Solution()

assert solution.shortestDistanceColor(
    [1,1,2,1,3,2,2,3,3],
    [[1,3],[2,2],[6,1]]
) == [3,0,3]  # provided example

assert solution.shortestDistanceColor(
    [1,2],
    [[0,3]]
) == [-1]  # target color missing

assert solution.shortestDistanceColor(
    [1,2,3],
    [[0,1],[1,2],[2,3]]
) == [0,0,0]  # exact matches at queried indices

assert solution.shortestDistanceColor(
    [1,1,1,1],
    [[2,1]]
) == [0]  # single repeated color

assert solution.shortestDistanceColor(
    [1,2,1,2,1],
    [[2,2]]
) == [1]  # nearest color appears on both sides

assert solution.shortestDistanceColor(
    [3,3,3],
    [[1,1]]
) == [-1]  # queried color absent entirely

assert solution.shortestDistanceColor(
    [1],
    [[0,1],[0,2]]
) == [0,-1]  # smallest possible array

assert solution.shortestDistanceColor(
    [1,2,3,1,2,3],
    [[5,1]]
) == [2]  # closest occurrence on the left

assert solution.shortestDistanceColor(
    [1,2,3,1,2,3],
    [[0,3]]
) == [2]  # closest occurrence on the right

Test	Why
[1,1,2,1,3,2,2,3,3]	Validates the official example
[1,2] with query for 3	Tests missing color handling
Exact self matches	Ensures distance 0 works correctly
Single repeated color	Tests uniform arrays
Nearest on both sides	Ensures binary search neighbor logic works
Entire color absent	Verifies -1 behavior
Single element array	Tests minimum input size
Closest on left	Ensures left neighbor check works
Closest on right	Ensures right neighbor check works

Edge Cases

Target Color Does Not Exist

A very important edge case occurs when the queried color never appears in the array.

Example:

colors = [1,2]
query = [0,3]

If the implementation blindly performs binary search without checking whether the positions list is empty, it may produce an index error or incorrect answer.

The solution handles this safely by checking:

if not positions:
    result.append(-1)

before any binary search occurs.

Query Index Already Contains the Target Color

Another important case is when the queried index itself already has the desired color.

Example:

colors = [1,2,3]
query = [1,2]

The correct answer is 0.

Binary search naturally handles this because the insertion position points directly to the queried index. The computed distance becomes:

abs(1 - 1) = 0

which is the minimum possible distance.

Closest Match Appears Only on One Side

Sometimes the nearest occurrence exists only to the left or only to the right.

Example:

positions = [2,5,8]
query index = 1

There is no valid left candidate.

Similarly:

positions = [2,5,8]
query index = 10

There is no valid right candidate.

Incorrect implementations often fail due to out-of-bounds access in these situations.

The solution explicitly checks boundaries:

if insert_pos < len(positions):

and:

if insert_pos > 0:

before accessing candidates, ensuring correctness in both cases.