Problem Description

You have an array colors containing only three possible values: 1, 2, and 3, representing three different colors.

You need to answer multiple queries about this array. Each query gives you:

• An index i (position in the array)
• A target color c (which is 1, 2, or 3)

For each query, find the shortest distance from index i to any occurrence of color c in the array. The distance is calculated as the absolute difference between indices.

If color c doesn't exist anywhere in the array, or cannot be reached from index i, return -1 for that query.

Example:

• If colors = [1, 1, 2, 1, 3, 2, 2, 3, 3] and query is (i=1, c=3)
• You need to find the closest 3 to index 1
• The 3s are at indices 4, 7, and 8
• The distances are |1-4|=3, |1-7|=6, and |1-8|=7
• The shortest distance is 3

The function should return a list of answers corresponding to each query in the order they were given.

Intuition

When we need to find the shortest distance from a given index to a target color, we essentially need to look in two directions: left and right. The closest occurrence of the target color could be on either side.

The naive approach would be to search both directions for each query, but this would be inefficient if we have many queries. Instead, we can preprocess the array once to store useful information that helps us answer all queries quickly.

The key insight is that for any position i, we only need to know:

• Where is the nearest occurrence of each color to the left of i?
• Where is the nearest occurrence of each color to the right of i?

With this information preprocessed, answering each query becomes a simple calculation: for query (i, c), the answer is the minimum of:

• Distance to the nearest color c on the left: i - left_position
• Distance to the nearest color c on the right: right_position - i

To build these preprocessing arrays:

• For the right array: We scan from right to left. At each position, we either encounter the color (update its position) or carry forward the previously known nearest position of each color.
• For the left array: We scan from left to right. Similar logic applies - we track the most recent occurrence of each color as we move forward.

We use infinity and -infinity as initial values to handle edge cases where a color doesn't exist on one side. If the calculated minimum distance exceeds the array length, it means the color doesn't exist in the array at all, so we return -1.

This preprocessing approach transforms a potentially O(n) operation per query into an O(1) lookup, making the solution efficient for multiple queries.

Learn more about Binary Search and Dynamic Programming patterns.

Solution Approach

The solution uses preprocessing to build two auxiliary arrays that store the nearest positions of each color from both directions.

Data Structures:

• right: A 2D array of size (n+1) × 3 where right[i][j] stores the index of the nearest occurrence of color j+1 at or to the right of position i
• left: A 2D array of size (n+1) × 3 where left[i][j] stores the index of the nearest occurrence of color j+1 at or to the left of position i-1

Implementation Steps:

1. Initialize the preprocessing arrays:

   • Set right[n][0] = right[n][1] = right[n][2] = inf (no colors exist beyond the array)
   • Set left[0][0] = left[0][1] = left[0][2] = -inf (no colors exist before the array)

2. Build the right array (scanning right to left):

   for i in range(n - 1, -1, -1):
       for j in range(3):
           right[i][j] = right[i + 1][j]  # Copy values from the right
       right[i][colors[i] - 1] = i        # Update current color's position

   • For each position i, first copy all nearest positions from i+1
   • Then update the position for the current color at index i

3. Build the left array (scanning left to right):

   for i, c in enumerate(colors, 1):
       for j in range(3):
           left[i][j] = left[i - 1][j]   # Copy values from the left
       left[i][c - 1] = i - 1             # Update current color's position

   • Note: left array is 1-indexed for easier query processing
   • Similar logic: copy previous values, then update current color

4. Process queries:

   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)

   • For query (i, c), calculate:
     • Distance to nearest c on the left: i - left[i + 1][c - 1]
     • Distance to nearest c on the right: right[i][c - 1] - i
   • Take the minimum of these two distances
   • If the distance exceeds n, the color doesn't exist, return -1

Time Complexity: O(n + q) where n is the array length and q is the number of queries Space Complexity: O(n) for the preprocessing arrays

Example Walkthrough

Let's walk through a small example with colors = [1, 2, 1, 3] and queries [(0, 3), (2, 2), (1, 1)].

Step 1: Initialize preprocessing arrays

• Array length n = 4
• right array (size 5×3): Initialize right[4] with [inf, inf, inf]
• left array (size 5×3): Initialize left[0] with [-inf, -inf, -inf]

Step 2: Build right array (scan right to left)

Starting from index 3 (rightmost):

• i = 3: colors[3] = 3

  • Copy from right[4]: right[3] = [inf, inf, inf]
  • Update color 3: right[3][2] = 3
  • Result: right[3] = [inf, inf, 3]

• i = 2: colors[2] = 1

  • Copy from right[3]: right[2] = [inf, inf, 3]
  • Update color 1: right[2][0] = 2
  • Result: right[2] = [2, inf, 3]

• i = 1: colors[1] = 2

  • Copy from right[2]: right[1] = [2, inf, 3]
  • Update color 2: right[1][1] = 1
  • Result: right[1] = [2, 1, 3]

• i = 0: colors[0] = 1

  • Copy from right[1]: right[0] = [2, 1, 3]
  • Update color 1: right[0][0] = 0
  • Result: right[0] = [0, 1, 3]

Step 3: Build left array (scan left to right)

• i = 1: colors[0] = 1

  • Copy from left[0]: left[1] = [-inf, -inf, -inf]
  • Update color 1: left[1][0] = 0
  • Result: left[1] = [0, -inf, -inf]

• i = 2: colors[1] = 2

  • Copy from left[1]: left[2] = [0, -inf, -inf]
  • Update color 2: left[2][1] = 1
  • Result: left[2] = [0, 1, -inf]

• i = 3: colors[2] = 1

  • Copy from left[2]: left[3] = [0, 1, -inf]
  • Update color 1: left[3][0] = 2
  • Result: left[3] = [2, 1, -inf]

• i = 4: colors[3] = 3

  • Copy from left[3]: left[4] = [2, 1, -inf]
  • Update color 3: left[4][2] = 3
  • Result: left[4] = [2, 1, 3]

Step 4: Process queries

Query 1: (i=0, c=3)

• Distance to left: 0 - left[1][2] = 0 - (-inf) = inf
• Distance to right: right[0][2] - 0 = 3 - 0 = 3
• Minimum: min(inf, 3) = 3
• Answer: 3

Query 2: (i=2, c=2)

• Distance to left: 2 - left[3][1] = 2 - 1 = 1
• Distance to right: right[2][1] - 2 = inf - 2 = inf
• Minimum: min(1, inf) = 1
• Answer: 1

Query 3: (i=1, c=1)

• Distance to left: 1 - left[2][0] = 1 - 0 = 1
• Distance to right: right[1][0] - 1 = 2 - 1 = 1
• Minimum: min(1, 1) = 1
• Answer: 1

Final Result: [3, 1, 1]

Solution Implementation

Time and Space Complexity

The time complexity is O(n + q), where n is the length of the array colors and q is the number of queries.

• Building the right array: O(n × 3) = O(n) - iterating through n elements, updating 3 color positions each time
• Building the left array: O(n × 3) = O(n) - iterating through n elements, updating 3 color positions each time
• Processing queries: O(q) - each query takes O(1) time to compute the minimum distance
• Total: O(n + n + q) = O(n + q)

The space complexity is O(n).

• right array: O((n + 1) × 3) = O(n) - storing 3 color positions for each of n + 1 positions
• left array: O((n + 1) × 3) = O(n) - storing 3 color positions for each of n + 1 positions
• ans array: O(q) - storing results for q queries
• Total: O(n + n + q) = O(n + q)

However, if we consider the output array ans as part of the required output rather than auxiliary space, the space complexity becomes O(n), which matches the reference answer. The reference answer likely considers only the auxiliary space used by the left and right arrays.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors in Index Mapping

One of the most common mistakes in this solution is confusion between the 0-indexed array positions and the 1-indexed left array. The left array uses 1-based indexing to simplify query processing, but this can easily lead to errors.

Pitfall Example:

# WRONG: Using left[i] instead of left[i + 1]
distance_to_left = query_position - nearest_left[query_position][target_color_idx]

Why it's wrong: The left[i] stores information about positions up to i-1. To get information about positions up to and including query_position, you need left[query_position + 1].

Correct Solution:

# CORRECT: Use left[i + 1] for query at position i
distance_to_left = query_position - nearest_left[query_position + 1][target_color_idx]

2. Color Index Conversion Mistakes

The colors are 1-indexed (1, 2, 3) but arrays are 0-indexed, requiring careful conversion.

Pitfall Example:

# WRONG: Forgetting to subtract 1 from color value
nearest_right[position][colors[position]] = position  # colors[position] could be 3!

Why it's wrong: This would cause an IndexError when colors[position] = 3 since valid indices are 0, 1, 2.

Correct Solution:

# CORRECT: Convert 1-based color to 0-based index
current_color = colors[position] - 1
nearest_right[position][current_color] = position

3. Incorrect Boundary Value Initialization

Using inappropriate sentinel values can lead to incorrect distance calculations.

Pitfall Example:

# WRONG: Using 0 or -1 as sentinel values
nearest_left = [[-1] * 3 for _ in range(n + 1)]

Why it's wrong: Using -1 or 0 as sentinel values will produce incorrect distances. For example, if no color exists to the left, query_position - (-1) would give query_position + 1, which might seem like a valid distance.

Correct Solution:

# CORRECT: Use infinity values to ensure non-existent colors produce large distances
nearest_left = [[float('-inf')] * 3 for _ in range(n + 1)]
nearest_right = [[float('inf')] * 3 for _ in range(n + 1)]

4. Incorrect Distance Validation

Determining whether a color exists requires careful threshold checking.

Pitfall Example:

# WRONG: Using wrong threshold or comparison
if min_distance >= n:  # Should be > not >=
    result.append(-1)

Why it's wrong: A distance equal to n-1 is valid (from index 0 to index n-1), so using >= would incorrectly mark some valid distances as non-existent.

Correct Solution:

# CORRECT: Distance exceeding n means color doesn't exist
if min_distance > n:
    result.append(-1)

5. Not Handling Edge Cases Properly

Failing to handle queries at array boundaries correctly.

Pitfall Example:

# WRONG: Not checking array bounds for queries
for query_position, target_color in queries:
    # Directly accessing without validation
    distance_to_right = nearest_right[query_position][target_color_idx] - query_position

Why it's wrong: While the problem typically ensures valid query positions, defensive programming should validate that 0 <= query_position < n.

Correct Solution:

# Add validation if needed
for query_position, target_color in queries:
    if query_position < 0 or query_position >= n:
        result.append(-1)
        continue
    # Process valid query...