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.

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

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
        int[][] distMap = new int[4][colors.length];
        for(int color = 1; color < 4; color++) {
            distMap[color] = processColor(colors, color);
        }
        
        List<Integer> resultList = new ArrayList(queries.length);
        
        for(int[] query: queries) {
            int dist = distMap[query[1]][query[0]];
            int result = (dist == Integer.MAX_VALUE)? -1: dist;
            resultList.add(result);
        }
        
        return resultList;
    }
    
    private int[] processColor(int[] colors, int color) {
        int[] dist = new int[colors.length];
        
        processColorLeft(colors, color, dist);
        
        processColorRight(colors, color, dist);
        
        return dist;
    }
    
    private void processColorLeft(int[] colors, int color, int[] dist) {
        int n = colors.length, prevIndex = -1;
        for(int index = 0; index < n; index++) {
            if(colors[index] == color) {
                dist[index] = 0;
                prevIndex = index;
            } else if(prevIndex == -1) {
                dist[index] = Integer.MAX_VALUE;
            } else {
                dist[index] = index - prevIndex;
            }
        }
    }
    
    private void processColorRight(int[] colors, int color, int[] dist) {
        int n = colors.length, prevIndex = -1;
        for(int index = n-1; index >= 0; index--) {
            if(colors[index] == color) {
                dist[index] = 0;
                prevIndex = index;
            } else if(prevIndex == -1) {
                dist[index] = Math.min(dist[index], Integer.MAX_VALUE);
            } else {
                dist[index] = Math.min(dist[index], (prevIndex-index));
            }
        }
    }
}

Follow up