https://leetcode.com/problems/minimum-absolute-difference-queries/ from Google

Thinking process:

I’m not sure if Google interviewers would hit the constraints, but in Leetcode’s contest, when handling this kind of problem, we need to check constraints carefully.

For example, in this problem, there’s one weird constraint saying that 1 <= nums[i] <= 100. Another weird constraint is 1 <= queries.length <= 2 * 10^4. In the contest, we need to have a sense that the most operations one problem could have is about 10^6, so any time complexity bigger than O(10^6) will get a TLE. This happens to be the product of the range of nums[i] and the length of queries.

With this, we can image a solution where we examine from 1 to 100 in each query. Given that we know the left and right index from the query, for any number x in the range from 1 to 100, we just need to answer if there’s a nums[i] which value is x and the index i is in between the left and the right index in the query. If we can find two of these kind of number, then the difference of them would be a possible answer.

For example, if we have nums = [1,3,4,8] and a query [0,1], we can check from 1 to 100, and see if we can find the pair. Here, we know that 1 is at index 0, which is in the range, and then 2 doesn’t exist so we ignore, then 3 is at index 1, which is in the range, too. So, one possible answer for this query is 3-1=2.

If nums = [4,5,2,2,7,10] and the query is [0,2], we can do the same thing. We first check 1, which is not in the nums, then 2, which has two indexes 2 and 3, since index 2 is in the range, so we find a number. Number 3 is not in nums, ignore. Number 4 is in the range, we find a possible answer 4-2=2. Then number 5 is in the range as well, so another possible answer is 5-4=1, and we pick 1 as the answer of course.

To efficiently figure out if the number x is having an index which is in the range, we can construct a index set of this number, and do a binary search in each query. For example, in the example above, for the number 2, we can build a set {2, 3} as its index set. Then for the query [0,2], we only need to use 0 and 2 to do a binary search in the index set, and see if there’s any index in between. If yes, then we find a number.

To build the index set, we use below code.

1vector<set<int>> slots(101);
2int N = nums.size();
3for (int i=0; i<N; i++) {
4    slots[nums[i]].insert(i);
5}

To find a number is having an index which is in the range, we use the below code. Here, the start is the starting point we want search. Initially it would be 1. We first search the left index. Find the next index which is >= left index. If we can find one and this one is <= right index, then there’s an index in between left and right index.

1int find(vector<int>& nums, vector<set<int>>& slots, int l, int r, int start) {
2    for (int i = start; i<101; i++) {
3        auto it1 = slots[i].lower_bound(l);
4        if (it1 != slots[i].end() and *it1 <= r)
5            return i;
6    }
7    return -1;
8}

Finally, for each query, we use find function to find two numbers to get the possible answer, and then we need to check from 1 to 100 to find all the pairs and get the minimum answer.

Here is the code.

 1class Solution {
 2public:
 3    int find(vector<int>& nums, vector<set<int>>& slots, int l, int r, int start) {
 4        for (int i = start; i<101; i++) {
 5            auto it1 = slots[i].lower_bound(l);
 6            if (it1 != slots[i].end() and *it1 <= r)
 7                return i;
 8        }
 9        return -1;
10    }
11    vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
12        vector<set<int>> slots(101);
13        int N = nums.size();
14        for (int i=0; i<N; i++) {
15            slots[nums[i]].insert(i);
16        }
17        vector<int> ans;
18        for (auto q : queries) {
19            int l = q[0];
20            int r = q[1];
21            int x = INT_MAX;
22            int i = find(nums, slots, l, r, 1);
23            while (i != -1) {
24                int j = find(nums, slots, l, r, i+1);
25                if (j != -1)
26                    x = min(x, j - i);
27                i = j;
28            }
29            if (x != INT_MAX)
30                ans.push_back(x);
31            else
32                ans.push_back(-1);
33        }
34        return ans;
35    }
36};