Shortest Distance to Target Color - Practice Coding Problems

Shortest Distance to Target Color - Problem

You're working with a colorful array where each position contains one of three colors: 1 (red), 2 (green), or 3 (blue). Your task is to efficiently answer multiple queries about finding the shortest distance from any given position to the nearest occurrence of a specific target color.

For each query (i, c), you need to find the minimum number of steps required to reach color c from index i. If the target color doesn't exist in the array, return -1.

Example: Given colors = [1,1,2,1,3,2,2,3,3], if you're at index 3 (color 1) and looking for color 2, you can go left to index 2 (distance = 1) or right to index 5 (distance = 2), so the answer is 1.

Input & Output

example_1.py — Basic Case

$ Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]

› Output: [3, 0, 3]

💡 Note: Query [1,3]: At index 1 (color 1), nearest color 3 is at index 4, distance = |4-1| = 3. Query [2,2]: At index 2 (color 2), we're already at color 2, distance = 0. Query [6,1]: At index 6 (color 2), nearest color 1 is at index 3, distance = |6-3| = 3.

example_2.py — Color Not Found

$ Input: colors = [1,2], queries = [[0,3]]

› Output: [-1]

💡 Note: Query [0,3]: At index 0, we're looking for color 3, but color 3 doesn't exist in the array, so we return -1.

example_3.py — Multiple Queries Same Position

$ Input: colors = [1,2,3,1,2], queries = [[2,1],[2,2],[2,3]]

› Output: [1, 1, 0]

💡 Note: All queries start at index 2 (color 3). For color 1: nearest is at index 3, distance = 1. For color 2: nearest is at index 1, distance = 1. For color 3: we're already at color 3, distance = 0.

Constraints

1 ≤ colors.length ≤ 5 × 10⁴
1 ≤ colors[i] ≤ 3
1 ≤ queries.length ≤ 5 × 10⁴
0 ≤ queries[i][0] < colors.length
1 ≤ queries[i][1] ≤ 3

Visualization

Tap to expand

Understanding the Visualization

Build Distance Map

Create a map showing distances to each color from every position

Forward Propagation

Scan left-to-right, updating distances based on colors seen so far

Backward Propagation

Scan right-to-left, finding closer colors from the other direction

Instant Queries

Answer any query in O(1) by looking up the precomputed distance

Key Takeaway

🎯 Key Insight: Instead of searching for each query, precompute all possible answers using dynamic programming. This transforms an O(n) search per query into O(1) lookup time!

Asked in

G Google 42 a Amazon 35 f Meta 28 ⊞ Microsoft 21

The optimal solution uses dynamic programming to precompute distances from each position to each color in O(n) time. A two-pass approach (forward and backward) ensures we find the minimum distance in each direction. This allows answering each query in O(1) time, making it perfect for handling many queries efficiently.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Linear Search for Each Query)	O(q × n)	O(1)	For each query, search linearly in both directions from the given index
Dynamic Programming (Optimal)	O(n + q)	O(n)	Precompute shortest distances for all positions and colors using DP
Preprocessing with Index Lists	O(n + q log n)	O(n)	Store all indices of each color, then use binary search to find nearest

Brute Force (Linear Search for Each Query) — Algorithm Steps

For each query (i, c), start from index i
Check if colors[i] == c, if yes return 0
Expand search radius: check i±1, then i±2, then i±3, etc.
Return the distance when target color is found
If we've searched the entire array without finding c, return -1

Visualization

Tap to expand

Step-by-Step Walkthrough

Start at query index

Begin search at the given index i

Check current position

If colors[i] matches target, return 0

Expand search radius

Check positions at distance 1, then 2, then 3...

First match wins

Return distance when target color is first found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int findDistance(int* colors, int n, int index, int targetColor) {
    if (colors[index] == targetColor) {
        return 0;
    }
    
    for (int distance = 1; distance < n; distance++) {
        // Check left
        if (index - distance >= 0 && colors[index - distance] == targetColor) {
            return distance;
        }
        // Check right
        if (index + distance < n && colors[index + distance] == targetColor) {
            return distance;
        }
    }
    
    return -1;
}

int* shortestDistanceColor(int* colors, int colorsSize, int** queries, int queriesSize, int* queryColSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int index = queries[i][0];
        int targetColor = queries[i][1];
        result[i] = findDistance(colors, colorsSize, index, targetColor);
    }
    
    return result;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × n)

For each of q queries, we might need to search the entire array of length n

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables for the current search

✓ Linear Space

38.2K Views

Medium Frequency

~18 min Avg. Time

1.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Linear Search for Each Query) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler