Shortest distance to target color

Array Binary Search Dynamic Programming

56.5% acceptance

Mar 31, 2026

539

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn shortest_distance_color(colors: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = colors.len();
    // dist[c][i] = shortest distance from index i to color c+1
    let mut dist = vec![vec![i32::MAX; n]; 3];
    // Left to right pass
    for c in 0..3 {
      let color = (c + 1) as i32;
      let mut last = -1i64;
      for i in 0..n {
        if colors[i] == color {
          last = i as i64;
        }
        if last >= 0 {
          dist[c][i] = (i as i64 - last) as i32;
        }
      }
      // Right to left pass
      last = -1;
      for i in (0..n).rev() {
        if colors[i] == color {
          last = i as i64;
        }
        if last >= 0 {
          dist[c][i] = dist[c][i].min((last - i as i64) as i32);
        }
      }
    }
    queries.iter().map(|q| {
      let (idx, c) = (q[0] as usize, (q[1] - 1) as usize);
      if dist[c][idx] == i32::MAX { -1 } else { dist[c][idx] }
    }).collect()
  }
}