[C++ & Java] Iterate and take diff of last seen index
Intuition
For each index the next near by index can be the next similar item in the array or the previous similar item in the array
So we can simply iterate and
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- For each index the next near by index can be the next similar item in the array or the previous similar item in the array 
- So we can simply iterate and track the last index seen. And for each index now take the diff of last seen index with current one. Do this once form left to right and once from right to left.
- To nullify the effect of circular array, we can consider the double size of the array while we iterate. 


# Complexity
- Time complexity: O(N)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(N)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
    unordered_map<int, int> leftSeen, rightSeen;
    vector<int> dist(nums.size(), INT_MAX), ans;
    for(int i = 0; i < nums.size()*2; ++i){
        if(leftSeen.find(nums[i % nums.size()]) != leftSeen.end()){
            dist[i % nums.size()] = i - leftSeen[nums[i % nums.size()]];
        }
        leftSeen[nums[i % nums.size()]] = i;
    }
    for(int i = nums.size() * 2 - 1; i >= 0; --i){
        if(rightSeen.find(nums[i % nums.size()]) != rightSeen.end()){
            dist[i % nums.size()] = min(dist[i%nums.size()], (rightSeen[nums[i % nums.size()]] - i));
        }
        rightSeen[nums[i % nums.size()]] = i;
    }
    for(auto q: queries){
        if(dist[q] >= nums.size()) ans.push_back(-1);
        else ans.push_back(dist[q]);
    }
    return ans;
}
```
```java []
List<Integer> solveQueries(int[] nums, int[] queries) {
    Map<Integer,Integer> lastSeen = new HashMap<>(), rightSeen = new HashMap<>();
    List<Integer> dist = new ArrayList<>(), ans = new ArrayList<>();
    for(int i = 0, n = nums.length; i < nums.length*2; ++i){
        if(i < n) dist.add(n+1);
        if(lastSeen.containsKey(nums[i % n])){
            int curInd = i % n;
            dist.set(curInd, Math.min(dist.get(curInd), i - lastSeen.get(nums[curInd])));
        }
        lastSeen.put(nums[i % n], i);
    }
    for(int i = nums.length*2-1, n = nums.length; i >= 0; --i){
        if(rightSeen.containsKey(nums[i % n])){
            int curInd = i % n;
            dist.set(curInd, Math.min(dist.get(curInd), rightSeen.get(nums[curInd]) - i));
        }
        rightSeen.put(nums[i % n], i);
    }
    for(int q: queries) ans.add((dist.get(q) >= nums.length)?-1: dist.get(q));
    return ans;
}
```


Further we can do the same in single pass with single map as welll.
- To do so we just need to update the previous index distance as well with the diff of curInd and the prevInd.

```cpp []
vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
    unordered_map<int, int> lastSeen;
    vector<int> dist(nums.size(), INT_MAX), ans;
    for(int i = 0, n = nums.size(); i < nums.size()*2; ++i){
        if(lastSeen.find(nums[i % nums.size()]) != lastSeen.end()){
            int curInd = i % n, prevIndex = lastSeen[nums[curInd]] % n;
            dist[curInd] = min(dist[curInd], i - lastSeen[nums[curInd]]);
            dist[prevIndex] = min(dist[prevIndex], i - lastSeen[nums[curInd]]);
        }
        lastSeen[nums[i % n]] = i;
    }
    for(auto q: queries) ans.push_back((dist[q] >= nums.size())?-1: dist[q]);
    return ans;
}
```
```Java []
List<Integer> solveQueries(int[] nums, int[] queries) {
    Map<Integer,Integer> lastSeen = new HashMap<>();
    List<Integer> dist = new ArrayList<>(), ans = new ArrayList<>();
    for(int i = 0, n = nums.length; i < nums.length*2; ++i){
        if(i < n) dist.add(n+1);
        if(lastSeen.containsKey(nums[i % n])){
            int curInd = i % n, prevIndex = lastSeen.get(nums[curInd]) % n;
            dist.set(curInd, Math.min(dist.get(curInd), i - lastSeen.get(nums[curInd])));
            dist.set(prevIndex, Math.min(dist.get(prevIndex), i - lastSeen.get(nums[curInd])));
        }
        lastSeen.put(nums[i % n], i);
    }
    for(int q: queries) ans.add((dist.get(q) >= nums.length)?-1: dist.get(q));
    return ans;
}
```


---

<span style="color:green">
<b>Here is an article of my last interview experience - A Journey to FAANG Company, I recomand you to go through this to know which all resources I have used & how I cracked interview at Amazon: </b> </span> 

https://leetcode.com/discuss/interview-experience/3171859/Journey-to-a-FAANG-Company-Amazon-or-SDE2-(L5)-or-Bangalore-or-Oct-2022-Accepted
 
---
['C++', 'Java']