LeetCode Solutions Blog

Shortest Distance to Target Color

Number: 1134

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an array of colors (where each color is 1, 2, or 3) and a list of queries, each query provides an index and a target color. The goal is to determine the shortest distance from the query index to any index in the array that contains the target color. If the target color does not exist in the array, return -1.

Key Insights

Pre-compute the positions for each color by traversing the colors array once.
Use separate sorted lists for each color to store the indices.
Binary search can quickly find the nearest index in the sorted list for a given query, reducing the overall processing time.
This method allows each query to be answered in O(log n) time after an O(n) pre-computation.

Space and Time Complexity

Time Complexity: O(n + m log n), where n is the number of elements in the colors array and m is the number of queries. Space Complexity: O(n), used for storing the indices of each color.

Solution

We precompute positions for each color by iterating over the array and storing indices in separate lists. For each query, we perform a binary search on the respective list of indices:

If the list is empty, we return -1.
Otherwise, we determine the insertion point and check its neighbor(s) to find the minimum distance between the query index and the nearest occurrence of the target color. This strategy efficiently handles multiple queries even when the input size is large.

Code Solutions

# Python solution with line-by-line comments
from bisect import bisect_left

def shortestDistanceColor(colors, queries):
    # Precompute positions for each color (1, 2, 3)
    color_positions = {1: [], 2: [], 3: []}
    for idx, color in enumerate(colors):
        color_positions[color].append(idx)
    
    results = []
    # Process each query
    for index, target in queries:
        positions = color_positions[target]
        # If no occurrences of target color, append -1
        if not positions:
            results.append(-1)
            continue

        # Use binary search to find the index of the smallest element >= query index
        pos = bisect_left(positions, index)
        distances = []
        # Check candidate at position pos, if valid.
        if pos < len(positions):
            distances.append(abs(positions[pos] - index))
        # Also check the previous element if it exists.
        if pos > 0:
            distances.append(abs(positions[pos-1] - index))
        # Append the minimum distance found.
        results.append(min(distances))
    return results

# Example usage
if __name__ == "__main__":
    colors = [1,1,2,1,3,2,2,3,3]
    queries = [[1,3],[2,2],[6,1]]
    print(shortestDistanceColor(colors, queries))  # Output: [3,0,3]