Shortest Distance to Target Color

Companies:
  • Google Interview Questions

Problem Statement

You are given an array colors, in which there are three colors: 12 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.

Sample Test Cases

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.

Problem Solution

The difficulty of this question is, how do we quickly find the position of c that is closest to i? An intuitive idea is of course to find all the positions of c, and then find the one that is closest to the position of i. In order to save all the positions of each number, it is better to use a dictionary. The format of the dictionary is unordered_map<int, vector<int>>, that is, the key is a number, and the value is an ordered list that represents all of the number. Therefore, the problem is abstracted into: how to find the closest target number in an ordered list?

Thinking of the limitation of time complexity, the obvious idea is : Use binary search to find the closest target. We can use lower_bound() to find j where num[j] >= target. The number closest to target should be nums[j-1] or nums[j]. Therefore, we need to make a judgment here as to which number is closest to the target.

Complexity Analysis

Time Complexity: O(NlogN) since we are looping through elements and checking lower_bounds.

Space Complexity: O(N) since we are storing elements in a map.

Code Implementation

 #include<bits/stdc++.h>
 using namespace std;

 void shortestDistanceColor(vector<int >& colors, vector<vector<int> >& queries) {
        const int N = colors.size();
        unordered_map<int, vector<int> > m;
        for (int i = 0; i < N; ++i) {
            m[colors[i]].push_back(i);
        }
        vector<int> res;
        for (auto& query : queries) {
            int cur = INT_MAX;
            int target = query[0];
            if (!m.count(query[1])) {
                res.push_back(-1);
                continue;
            }
            int pos = closest(m[query[1]], target);
            res.push_back(abs(pos - target));
        }
        for(int i=0;i<res.size();i++)
        {
            cout<<res[i]<<" ";

        }
    }
    int closest(vector<int>& nums, int target) {
        int pos = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        if (pos == 0) return nums[0];
        if (pos == nums.size()) return nums[nums.size() - 1];
        if (nums[pos] - target < target - nums[pos - 1])
            return nums[pos];
        return nums[pos - 1];
    }

    int main()
    {
        vector<int>color;
        color.push_back(1);
        color.push_back(1);
        color.push_back(2);
        color.push_back(1);
        color.push_back(3);
        color.push_back(2);
        color.push_back(2);
        color.push_back(3);
        color.push_back(3);
      vector<vector<int>> v1 = {{1,3},{2,2},{6,1}};
      shortestDistanceColor(colors,v1);

}

 

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]