Shortest Distance to Target Color

The solution here for this medium LC problem might not be the fastest but I think it’s really clean and concise and easy to understand.

The idea is to create a mapping of the colors and their corresponding indices in the colors array. The values will be stored in a treeset so we can easily find the closest index to our target index.

Now for each query, first, we need to get all the indices for our target color. Then, find the closest index both from left and right sides of our target index. Finally, find the minimum difference between the target index and left or right closest index.

class Solution {
    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
        final Map<Integer, TreeSet<Integer>> mapping = new HashMap<>();
        
        for(int i=0; i < colors.length; i++){
            mapping.putIfAbsent(colors[i], new TreeSet<>());
            mapping.get(colors[i]).add(i);
        }
        
        List<Integer> output = new ArrayList<>();
        for(int[] query: queries){
            int index = query[0];
            int color = query[1];
            
            if(!mapping.containsKey(color)){
                output.add(-1);
                continue;
            }
            
            TreeSet<Integer> indices = mapping.get(color);
            Integer left = indices.floor(index);
            Integer right = indices.ceiling(index);
            
            output.add(Math.min(left == null ? Integer.MAX_VALUE : index - left, right == null ? Integer.MAX_VALUE: right - index));
        }
        
        return output;
    }
}

Runtime: 141 ms, faster than 14.02% of Java online submissions for Shortest Distance to Target Color.
Memory Usage: 67.9 MB, less than 100.00% of Java online submissions for Shortest Distance to Target Color.

Marc Lester Tan