Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1182.html

1182. Shortest Distance to Target Color

Level

Medium

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

Solution

The idea is that given an index and a color, search in both sides of the given index, find the closest index where the color equals the given color and calculate the closest distance. To save runtime, use a map to store each color and index and the distance so that if there are repeated queries, retrieve the distance directly from the map and there is no need to search again. If a color is not found, then the query result is -1.

  • class Solution {
    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
        final int MAX_LENGTH = 50000;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        List<Integer> distances = new ArrayList<Integer>();
        int colorsLength = colors.length;
        int queriesCount = queries.length;
        outer:
        for (int i = 0; i < queriesCount; i++) {
            int[] query = queries[i];
            int index = query[0], color = query[1];
            if (colors[index] == color)
                distances.add(0);
            else {
            	int key = color * MAX_LENGTH + index;
                if (map.containsKey(key)) {
                    int distance = map.get(key);
                    distances.add(distance);
                    continue;
                }
                int step = 1;
                int left = index - step, right = index + step;
                while (left >= 0 || right < colorsLength) {
                    if (left >= 0 && right < colorsLength) {
                        int leftColor = colors[left], rightColor = colors[right];
                        if (leftColor == color || rightColor == color) {
                            distances.add(step);
                            map.put(key, step);
                            continue outer;
                        } else {
                            left--;
                            right++;
                            step++;
                        }
                    } else if (left >= 0) {
                        int leftColor = colors[left];
                        if (leftColor == color) {
                            distances.add(step);
                            map.put(key, step);
                            continue outer;
                        } else {
                            left--;
                            step++;
                        }
                    } else {
                        int rightColor = colors[right];
                        if (rightColor == color) {
                            distances.add(step);
                            map.put(key, step);
                            continue outer;
                        } else {
                            right++;
                            step++;
                        }
                    }
                }
                distances.add(-1);
            }
        }
        return distances;
    }
}

  • // OJ: https://leetcode.com/problems/shortest-distance-to-target-color/
// Time: O(QlogQ + C + Q)
// Space: O(C)
class Solution {
public:
    vector<int> shortestDistanceColor(vector<int>& C, vector<vector<int>>& Q) {
        vector<int> ans(Q.size(), -1);
        for (int i = 0; i < Q.size(); ++i) Q[i].push_back(i);
        sort(begin(Q), end(Q));
        unordered_map<int, int> m;
        for (int i = 0, j = 0; i < C.size() && j < Q.size(); ++i) {
            m[C[i]] = i;
            while (j < Q.size() && Q[j][0] == i) {
                if (m.count(Q[j][1])) ans[Q[j][2]] = i - m[Q[j][1]];
                ++j;
            }
        }
        m.clear();
        for (int i = C.size() - 1, j = Q.size() - 1; i >= 0 && j >= 0; --i) {
            m[C[i]] = i;
            while (j >= 0 && Q[j][0] == i) {
                if (m.count(Q[j][1]) && (ans[Q[j][2]] == -1 || m[Q[j][1]] - i < ans[Q[j][2]])) {
                    ans[Q[j][2]] = m[Q[j][1]] - i;
                }
                --j;
            }
        }
        return ans;
    }
};

  • class Solution:
    def shortestDistanceColor(
        self, colors: List[int], queries: List[List[int]]
    ) -> List[int]:
        color_indexes = defaultdict(list)
        for i, c in enumerate(colors):
            color_indexes[c].append(i)
        res = []
        for i, c in queries:
            if c not in color_indexes:
                res.append(-1)
            else:
                t = color_indexes[c]
                left, right = 0, len(t) - 1
                while left < right:
                    mid = (left + right) >> 1
                    if t[mid] >= i:
                        right = mid
                    else:
                        left = mid + 1
                val = abs(t[left] - i)
                if left > 0:
                    val = min(val, abs(t[left - 1] - i))
                if left < len(t) - 1:
                    val = min(val, abs(t[left + 1] - i))
                res.append(val)
        return res



  • 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
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

  • 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;
}

All Problems

All Solutions