1182. Shortest Distance to Target Color

Problem Description

You are presented with an array called colors, in which the elements are integers representing different colors. The integers 1, 2, and 3 correspond to three distinct colors. Along with this array, a set of queries is provided, each query being a pair of integers (i, c) where i is an index in the colors array and c is one of the three colors. Your task is to find the shortest distance from the position i to the location of the requested color c in the array. The distance is measured as the number of steps needed to move from index i to the index of the target color c. If the target color c does not exist in the array, you should return -1.

Intuition

The essence of the solution is to precompute and store the closest occurrence of each color to every index in the array, both from the left and the right directions. Once we have this precomputed information, any query can be answered quickly by comparing the distances from the index i to the nearest occurrences of color c on both sides.

Here's a step-by-step breakdown of the intuition:

1. We create two tables (arrays), right and left, that will contain, for each index i in the colors array, the nearest index on the right and left respectively where each of the three colors is found.

2. Starting from the right end of the colors array, we fill the right table with indices of the closest occurrence of each color as we move leftward. We initialize the table with infinity (inf) to signify that initially, we haven't found any colors.

3. Similarly, starting from the left end of the colors array, we fill the left table with indices of the closest occurrence of each color as we move rightward. The table is initially filled with -inf to indicate no colors found.

4. For each query (i, c), we determine the distance to the color c by taking the minimum between the distance to the closest occurrence of color c on the right and on the left of the index i.

5. If the computed minimum distance is greater than the size of the colors array, this indicates that there is no such color c in the colors array, and we return -1 for that query. Otherwise, we return the computed distance.

This approach makes it possible to answer each query in constant time after the initial precomputation, which is done in linear time relative to the size of the colors array. This is much more efficient than a straightforward approach where you might check the entire array for each individual query.

Learn more about Binary Search and Dynamic Programming patterns.

Solution Approach

The solution provided above does not use a binary search approach as mentioned in the Reference Solution Approach. Instead, it relies on dynamic programming with precomputation to find the nearest occurrence of each color to every index, from both directions. The steps can be explained as follows:

1. Two 2D tables, right and left, are created to record the indexes of the nearest color occurrence on the right and left sides of each index i. Both are initialized with appropriate values to indicate that initially, no color has been found yet (using inf for the right direction, and -inf for the left).

2. The right table is filled by traversing the colors array in reverse, from n - 1 to 0. At each index i, it updates only the column corresponding to colors[i] - 1 (since colors are 1-indexed, we subtract 1 to use zero-based indexing) with the current index i. This implies updating the position of the encountered color and leaving the others as previously computed.

3. The left table is populated by iterating through the colors array from the start, incrementing index i. Similar to the right table, it updates the column corresponding to colors[i] - 1 at each step.

4. Once the tables are built, the solution evaluates each query (i, c). It calculates the distances to color c from both the right and the left tables for the given index i. The shorter of the two distances is considered, as we are looking for the shortest path to the desired color.

5. If the smallest distance is greater than the length of the array, it indicates that the target color does not exist, and -1 is returned for that query. Otherwise, the shortest calculated distance is returned.

The tables right and left exploit the fact that colors array indices and the colors themselves can be indexed and compared directly to store relevant distances quickly. These precomputation tables allow the queries to be answered swiftly in O(1) time after the initial setup, thus making the solution efficient and suitable for scenarios with multiple queries on the same colors array.

This approach enables the solution to bypass binary search, providing a direct access method to retrieve the shortest distance for each query. While binary search is a powerful tool for searching in sorted arrays, in this context, the precomputation strategy streamlines query handling and avoids repeated search operations.

Example Walkthrough

Let's illustrate the solution approach with a small example. Assume we have an array colors and a set of queries as follows:

colors array: [1, 3, 2, 1, 2, 3, 3, 2] queries: [(4, 3), (2, 1), (5, 2)]

Step 1: Initialize right and left tables

We create two 2D tables right and left. Since we have 3 colors, each table will have 3 columns, and the number of rows will be equal to the length of the colors array. We initialize right table with inf and left table with -inf.

Initial right table (8 rows, 3 columns, initialized with inf):

1inf inf inf
2inf inf inf
3inf inf inf
4inf inf inf
5inf inf inf
6inf inf inf
7inf inf inf
8inf inf inf

Initial left table (8 rows, 3 columns, initialized with -inf):

1-inf -inf -inf
2-inf -inf -inf
3-inf -inf -inf
4-inf -inf -inf
5-inf -inf -inf
6-inf -inf -inf
7-inf -inf -inf
8-inf -inf -inf

Step 2: Populate the right table

We traverse the colors array from right to left, updating the right table as we encounter each color.

Final right table:

1 5   7   6
2 5   7   6
3 5   7   3
4 5   7   3
5 5   5   3
6 5   5   5
7-1   5   5
8-1   7   5

Step 3: Populate the left table

We traverse the colors array from left to right, updating the left table with encountered colors.

Final left table:

1-1  -1  -1
2 0  -1   1
3 0  -1   1
4 3  -1   1
5 3   4   1
6 3   4   5
7 3   4   6
8 3   7   6

Step 4: Evaluate queries

For each query (i, c), we calculate the two distances to color c from both right and left tables for index i, and we take the shorter one.

1. Query (4, 3) would check right[4][2] and left[4][2] since color '3' corresponds to the 3rd column (index 2). Thus, we have right[4][2] = 5 and left[4][2] = 1. The shortest distance is 5 - 4 = 1 from the left.

2. Query (2, 1) checks right[2][0] and left[2][0]. We get right[2][0] = 5 and left[2][0] = 0. The shortest distance is 2 - 0 = 2 from the left.

3. Query (5, 2) checks right[5][1] and left[5][1]. We find right[5][1] = 5 and left[5][1] = 4. The shortest distance is 5 - 4 = 1 from the left.

Step 5: Return results for queries

The results of the queries are distances [1, 2, 1] correspondingly.

By precomputing the right and left tables, we efficiently answer each query in constant time with the precomputed values without the need for a binary search for each query. This is particularly advantageous when there are many queries, as the time savings can be significant.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the operations performed:

1. The first loop iterates backward from n - 1 to 0, which is O(n), where n is the length of the colors list. Inside this loop, there is another loop that runs 3 times (for each color), which is O(1). So, combined this is O(n).

2. The second loop iterates from 1 to n, which is O(n). Similar to the first loop, it has an inner loop that runs 3 times, so overall this is also O(n).

3. The last loop processes the queries. For each query, the code performs constant time comparisons to calculate the distance, which is O(1). If there are q queries, this loop is O(q).

Therefore, the total time complexity is the sum of these three loops: O(n) + O(n) + O(q) = O(2n + q). Since constants are dropped in Big O notation, the simplified time complexity is O(n + q).

Space Complexity

The space complexity is determined by the additional space used:

1. Two two-dimensional lists (right and left) are created, each with dimensions (n + 1) x 3. Thus, the space occupied by these lists is 2 x (n + 1) x 3, which simplifies to O(6n + 6).

2. The space for the output list ans depends on the number of queries q, which makes it O(q).

Combined, the total space complexity is O(6n + 6 + q). After removing constants and non-dominant terms, the space complexity simplifies to O(n + q).

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