Question

1182. Shortest Distance to Target Color

中文文档

Description

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^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

Solutions

Solution 1: Preprocessing

We 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.

class Solution:
  def shortestDistanceColor(
    self, colors: List[int], queries: List[List[int]]
  ) -> List[int]:
    n = len(colors)
    right = [[inf] * 3 for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
      for j in range(3):
        right[i][j] = right[i + 1][j]
      right[i][colors[i] - 1] = i
    left = [[-inf] * 3 for _ in range(n + 1)]
    for i, c in enumerate(colors, 1):
      for j in range(3):
        left[i][j] = left[i - 1][j]
      left[i][c - 1] = i - 1
    ans = []
    for i, c in queries:
      d = min(i - left[i + 1][c - 1], right[i][c - 1] - i)
      ans.append(-1 if d > n else d)
    return ans

class Solution {
  public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
    int n = colors.length;
    final int inf = 1 << 30;
    int[][] right = new int[n + 1][3];
    Arrays.fill(right[n], inf);
    for (int i = n - 1; i >= 0; --i) {
      for (int j = 0; j < 3; ++j) {
        right[i][j] = right[i + 1][j];
      }
      right[i][colors[i] - 1] = i;
    }
    int[][] left = new int[n + 1][3];
    Arrays.fill(left[0], -inf);
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < 3; ++j) {
        left[i][j] = left[i - 1][j];
      }
      left[i][colors[i - 1] - 1] = i - 1;
    }
    List<Integer> ans = new ArrayList<>();
    for (int[] q : queries) {
      int i = q[0], c = q[1] - 1;
      int d = Math.min(i - left[i + 1][c], right[i][c] - i);
      ans.add(d > n ? -1 : d);
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
    int n = colors.size();
    int right[n + 1][3];
    const int inf = 1 << 30;
    fill(right[n], right[n] + 3, inf);
    for (int i = n - 1; i >= 0; --i) {
      for (int j = 0; j < 3; ++j) {
        right[i][j] = right[i + 1][j];
      }
      right[i][colors[i] - 1] = i;
    }
    int left[n + 1][3];
    fill(left[0], left[0] + 3, -inf);
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < 3; ++j) {
        left[i][j] = left[i - 1][j];
      }
      left[i][colors[i - 1] - 1] = i - 1;
    }
    vector<int> ans;
    for (auto& q : queries) {
      int i = q[0], c = q[1] - 1;
      int d = min(i - left[i + 1][c], right[i][c] - i);
      ans.push_back(d > n ? -1 : d);
    }
    return ans;
  }
};

func shortestDistanceColor(colors []int, queries [][]int) (ans []int) {
  n := len(colors)
  const inf = 1 << 30
  right := make([][3]int, n+1)
  left := make([][3]int, n+1)
  right[n] = [3]int{inf, inf, inf}
  left[0] = [3]int{-inf, -inf, -inf}
  for i := n - 1; i >= 0; i-- {
    for j := 0; j < 3; j++ {
      right[i][j] = right[i+1][j]
    }
    right[i][colors[i]-1] = i
  }
  for i := 1; i <= n; i++ {
    for j := 0; j < 3; j++ {
      left[i][j] = left[i-1][j]
    }
    left[i][colors[i-1]-1] = i - 1
  }
  for _, q := range queries {
    i, c := q[0], q[1]-1
    d := min(i-left[i+1][c], right[i][c]-i)
    if d > n {
      d = -1
    }
    ans = append(ans, d)
  }
  return
}

function shortestDistanceColor(colors: number[], queries: number[][]): number[] {
  const n = colors.length;
  const inf = 1 << 30;
  const right: number[][] = Array(n + 1)
    .fill(0)
    .map(() => Array(3).fill(inf));
  const left: number[][] = Array(n + 1)
    .fill(0)
    .map(() => Array(3).fill(-inf));
  for (let i = n - 1; i >= 0; --i) {
    for (let j = 0; j < 3; ++j) {
      right[i][j] = right[i + 1][j];
    }
    right[i][colors[i] - 1] = i;
  }
  for (let i = 1; i <= n; ++i) {
    for (let j = 0; j < 3; ++j) {
      left[i][j] = left[i - 1][j];
    }
    left[i][colors[i - 1] - 1] = i - 1;
  }
  const ans: number[] = [];
  for (const [i, c] of queries) {
    const d = Math.min(i - left[i + 1][c - 1], right[i][c - 1] - i);
    ans.push(d > n ? -1 : d);
  }
  return ans;
}