Shortest Distance to Target Color

class Solution {
    public List<Integer> findNearestColors(int[] palette, int[][] requests) {
        int len = palette.length;
        int[] farRight = {0, 0, 0};
        int[] farLeft = {len - 1, len - 1, len - 1};
    
        int[][] proximity = new int[3][len];
    
        for (int i = 0; i < 3; i++) {
            Arrays.fill(proximity[i], -1);
        }
    
        // Forward traversal
        for (int i = 0; i < len; i++) {
            int c = palette[i] - 1;
            for (int j = farRight[c]; j < i + 1; j++) {
                proximity[c][j] = i - j;
            }
            farRight[c] = i + 1;
        }
    
        // Backward traversal
        for (int i = len - 1; i >= 0; i--) {
            int c = palette[i] - 1;
            for (int j = farLeft[c]; j > i - 1; j--) {
                if (proximity[c][j] == -1 || proximity[c][j] > j - i) {
                    proximity[c][j] = j - i;
                }
            }
            farLeft[c] = i - 1;
        }
    
        List<Integer> response = new ArrayList<>();
        for (int[] req : requests) {
            response.add(proximity[req[1] - 1][req[0]]);
        }
        return response;
    }
}

This Java solution involves finding the shortest distance for each request from the given palette to the target colors. The Solution class contains a method findNearestColors that processes the input palette of colors and a series of requests, each specifying a position and a target color. Follow these steps to understand this code:

1. Initialize necessary variables:

   • len - the length of the palette array.
   • farRight and farLeft - arrays that keep track of the rightmost and leftmost indices reached by each color in the palette.
   • proximity - a 2D-array where each row corresponds to a color and each column corresponds to the shortest distance of the respective color from a certain index.

2. Fill the proximity matrix with initial values of -1, a placeholder indicating no proximity calculated yet.

3. Conduct a forward traversal over the palette:

   • Update the farRight array whenever a new instance of a color is found.
   • Fill in distances for each color index range swept from the previous position to the current.

4. Conduct a backward traversal:

   • Similar to the forward pass, update the farLeft.
   • Compare and possibly update proximity values, ensuring they hold the minimum distance for backward encounters of the same color.

5. Construct the response list:

   • For each request defined by the start index and a target color from the requests array, retrieve the shortest distance from the proximity array and add it to the response list.

6. Return the list of shortest distances.

By using two sweeps across the palette, the solution efficiently calculates both forward and backward closest distances for each color, ensuring that the final response values represent the closest possible distances to the requested colors from specified positions.

class Solution:
    def minimumDistancePerColor(self, colorList: List[int], searchQueries: List[List[int]]) -> List[int]:
        # Establish basic parameters and structure
        color_count = len(colorList)
        nearest_right = [0, 0, 0]
        nearest_left = [color_count - 1, color_count - 1, color_count - 1]
    
        color_distance = [[-1] * color_count for _ in range(3)]
    
        # Populate distances from right to left
        for index in range(color_count):
            current_color = colorList[index] - 1
            for position in range(nearest_right[current_color], index + 1):
                color_distance[current_color][position] = index - position
            nearest_right[current_color] = index + 1
    
        # Populate distances from left to right
        for index in range(color_count - 1, -1, -1):
            current_color = colorList[index] - 1
            for position in range(nearest_left[current_color], index - 1, -1):
                # Update if no distance found yet or a closer distance is found
                if color_distance[current_color][position] == -1 or color_distance[current_color][position] > position - index:
                    color_distance[current_color][position] = position - index
            nearest_left[current_color] = index - 1
    
        return [color_distance[color - 1][position] for position, color in searchQueries]

The given Python code is designed to find the shortest distance to a target color in a list based on multiple queries. This capability is encapsulated within a class named Solution that features the method minimumDistancePerColor which accepts colorList, a list of integers representing colors, and searchQueries, a list of lists detailing position and target color queries.

The method workflow is as follows:

1. Initialize variables color_count to get the number of elements in colorList, and nearest_right and nearest_left to serve as arrays to track the nearest rightmost and leftmost indices of each color.

2. Set up a 2D list color_distance where each sublist represents distances for a specific color from every position to the nearest occurrence of that color to the left and right.

3. Populate the color_distance array with distances from the rightmost index of colorList to the left. This is achieved by iterating from the start to the end of colorList. For each color, calculate the distance from the previous indexed position to the current position being evaluated.

4. Populate the color_distance array with distances from the leftmost index of colorList to the right. This operates by iterating from the end to the start of colorList, updating distances only if no previous distance is found or a shorter distance is identified.

5. For each query in searchQueries, extract the relevant distance using the color_distance array filled previously enabling each position and desired color to efficiently fetch the computed nearest distance.

This approach in combining forward and backward passes to compute distances ensures each query result retrieval in constant time, effective for scenarios where multiple queries on large datasets are expected.