Shortest Distance to Target Color

Shortest Distance to Target Color

What is this problem about?

The Shortest Distance to Target Color interview question gives you a colored array (each element is 1, 2, or 3) and a list of queries. Each query (i, c) asks for the minimum distance from index i to any index containing color c. If no element of color c exists, return -1. This is a preprocessing problem: precompute nearest color positions using binary search or DP.

Why is this asked in interviews?

Google asks this problem because it tests the tradeoff between query-time computation and preprocessing. Answering each query naively is O(n), but with preprocessing, each query becomes O(log n) (binary search on sorted position lists) or O(1) (precomputed DP tables). It evaluates whether candidates recognize when preprocessing dramatically improves query response time — a key systems design consideration.

Algorithmic pattern used

Two clean approaches: binary search on position lists, and DP precomputation. Binary search: for each color, store all indices where it appears in a sorted list. For query (i, c), binary search for the nearest index to i in color c's list — check the two bracketing positions and take the minimum distance. DP approach: for each color c, create an array left[i] = distance to nearest c to the left of i, and right[i] = distance to nearest c to the right. Answer each query in O(1) using min(left[i], right[i]).

Example explanation

colors = [1, 1, 2, 1, 3, 2, 2, 3, 3], queries = [(3,2), (8,3), (1,3)].

Color 2 positions: [2, 5, 6].

Query (3,2): binary search finds index 2 (distance 1) and index 5 (distance 2). Min = 1. Query (8,3): color 3 positions [4,7,8]. Index 8 is position 8 → distance 0. Query (1,3): nearest 3 is at index 4. Distance = 3.

Common mistakes candidates make

• Using O(n) scan for each query without preprocessing — too slow for large inputs.
• Not handling the case where color c doesn't exist in the array — return -1.
• In binary search, forgetting to check both the element before and after the insertion point — one might be closer.
• In the DP approach, not initializing left/right arrays with infinity before propagation.

Interview preparation tip

For the Shortest Distance to Target Color coding problem, the binary search dynamic programming array interview pattern provides two valid approaches. The DP approach (two-pass left/right precomputation) gives O(1) queries after O(n) preprocessing — preferred when queries are frequent. The binary search approach is O(log n) per query after O(n log n) preprocessing. Google interviewers ask about the tradeoff — know both approaches and their complexities. Practice the two-pass DP template for "nearest element of type X" queries.