Solution Explanation for Shortest Distance to Target Color

This problem asks to find the shortest distance from a given index i in the colors array to the target color c. The solution uses a pre-processing technique to significantly improve efficiency.

Approach: Preprocessing with Left and Right Arrays

The core idea is to avoid repeatedly searching for the nearest color for each query. Instead, we precompute the distances to the nearest occurrence of each color (1, 2, and 3) from every index in both directions (left and right).

1. Preprocessing:

   • Two 2D arrays, left and right, are created. left[i][j] stores the index of the nearest occurrence of color j+1 to the left of index i (inclusive). Similarly, right[i][j] stores the index of the nearest occurrence of color j+1 to the right of index i (inclusive).
   • If a color is not found to the left or right, -∞ and ∞ are used as placeholders respectively. These are represented as a sufficiently large negative and positive number in the code (e.g., -inf and inf).
   • The preprocessing iterates through colors once in each direction to populate left and right.

2. Query Processing:

   • For each query [i, c], the shortest distance is determined by:
     • min(i - left[i + 1][c - 1], right[i][c - 1] - i)
     • left[i+1][c-1] is used because it considers indices before i.
     • right[i][c-1] is used directly as it represents distances from index i to the right.
   • If the calculated distance d exceeds the length of colors, it means the target color c is not present, so -1 is returned for that query.

Time and Space Complexity

• Time Complexity: O(N + Q), where N is the length of colors and Q is the number of queries. The preprocessing step takes O(N) time, and processing each query takes O(1) time, resulting in O(Q) for all queries.
• Space Complexity: O(N), dominated by the size of the left and right arrays.

Code Examples (Python, Java, C++, Go, TypeScript)

The code examples provided earlier demonstrate the implementation of this approach in different programming languages. Each example follows the same algorithm:

1. Initialization: Create left and right arrays and initialize them with appropriate placeholders.
2. Preprocessing: Iterate through colors to populate left and right with distances to nearest occurrences of each color.
3. Query Handling: Process each query using the formula mentioned above to calculate the shortest distance.

This preprocessing approach transforms the problem from multiple linear searches (which would have O(N*Q) time complexity) into a constant-time query operation, resulting in a much more efficient solution.