_1182.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;

publicclass_1182 {
publicstaticclassSolution1 {
publicList<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
Map<Integer, List<Integer>> map = buildMap(colors);
List<Integer> result = newArrayList<>();
for (int[] query : queries) {
result.add(binarySearch(query[0], map.get(query[1])));
 }
returnresult;
 }

privateIntegerbinarySearch(intindex, List<Integer> indices) {
if (indices == null) {
return -1;
 }
intleft = 0;
intright = indices.size() - 1;
intminDistance = Integer.MAX_VALUE;
while (left <= right) {
intmid = left + (right - left) / 2;
if (indices.get(mid) == index) {
return0;
 } elseif (indices.get(mid) > index) {
minDistance = Math.min(minDistance, indices.get(mid) - index);
right = mid - 1;
 } else {
minDistance = Math.min(minDistance, index - indices.get(mid));
left = mid + 1;
 }
 }
returnminDistance;
 }

privateMap<Integer, List<Integer>> buildMap(int[] colors) {
Map<Integer, List<Integer>> map = newHashMap<>();
for (inti = 0; i < colors.length; i++) {
if (!map.containsKey(colors[i])) {
map.put(colors[i], newArrayList<>());
 }
map.get(colors[i]).add(i);
 }
returnmap;
 }
 }
}