You are given an array colors, in which there are three colors: 1, 2 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^41 <= colors[i] <= 31 <= queries.length <= 5*10^4queries[i].length == 20 <= queries[i][0] < colors.length1 <= queries[i][1] <= 3We can preprocess the distance from each position to the nearest color 1, 2, 3 on the left, and the distance from each position to the nearest color 1, 2, 3 on the right, and record them in the arrays left and right. Initially, left[0][0] = left[0][1] = left[0][2] = -infty, and right[n][0] = right[n][1] = right[n][2] = infty, where n is the length of the array colors.
Then for each query (i, c), the minimum distance is d = min(i - left[i + 1][c - 1], right[i][c - 1] - i). If d > n, there is no solution, and the answer to this query is -1.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array colors.
Java
C++
Go
TypeScript
Sort Colors - Quicksort Partition - Leetcode 75 - Python • NeetCode • 106,865 views views
Watch 9 more video solutions →Practice Shortest Distance to Target Color with our built-in code editor and test cases.
Practice on FleetCode