LeetCode 1182. Shortest Distance to Target Color

Description

https://leetcode.com/problems/shortest-distance-to-target-color/

You are given an array colors, in which there are three colors: 12 and 3.

You are also given some queries. Each query consists of two integers i and c, return the shortest distance between the given index i and the target color c. If there is no solution return -1.

Example 1:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

Example 2:

Input: colors = [1,2], queries = [[0,3]]
Output: [-1]
Explanation: There is no 3 in the array.

Constraints:

  • 1 <= colors.length <= 5*10^4
  • 1 <= colors[i] <= 3
  • 1 <= queries.length <= 5*10^4
  • queries[i].length == 2
  • 0 <= queries[i][0] < colors.length
  • 1 <= queries[i][1] <= 3

Explanation

Build a mapping between color and its indices. Then for each query, do a binary search to find which color index is the nearest one to the query target position.

Python Solution

class Solution:
    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        
        mapping = defaultdict(list)
        
        for i, color in enumerate(colors):
            mapping[color].append(i)
            
        results = []
        
        
        for query in queries:
            position = query[0]
            color = query[1]

            if color not in mapping:
                results.append(-1)
                continue
                
            index_list = mapping[color]
            insert = bisect.bisect_left(index_list, position)
            
            
            left_nearest = abs(index_list[max(insert - 1, 0)] - position)
            right_nearest = abs(index_list[min(insert, len(index_list) - 1)] - position)
            
            results.append(min(left_nearest, right_nearest))

            
        return results
  • Time Complexity: O(Qlog(N) + N).
  • Space Complexity: O(N).

where Q is the length of queries and N is the length of colors.

Leave a Reply

Your email address will not be published.