Beginner Friendly Optimized Binary Search + Hash Table Solution | C++ | Beats 100%
IntuitionThe core idea is to precompute the indices for each element so that for any query, you can quickly find the closest occurrence by checking its immediat
# Intuition
The core idea is to precompute the indices for each element so that for any query, you can quickly find the closest occurrence by checking its immediate neighbors in the sorted list. By evaluating both direct and wrap-around distances, the solution elegantly handles the circular nature of the array.

# Approach

1. **Mapping Indices:**  
   - **Step:** Traverse the `nums` array and build a hash map where each unique value is mapped to a list of its indices.  

2. **Binary Search for Position:**  
   - **Step:** For each query index, retrieve the value at that index. Then, perform a binary search on the corresponding list of indices to locate the exact position of the query index.  

3. **Finding Circular Neighbors:**  
   - **Step:** Identify the neighbors around the query index in the sorted list:  
     - **Left Neighbor:** The previous element in the list (or the last element if the query is at the beginning).  
     - **Right Neighbor:** The next element in the list (or the first element if the query is at the end).  

4. **Calculating Minimum Distance:**  
   - **Step:** Compute the distances between the query index and its neighbors:  
     - **Direct Distance:** Use the absolute difference between indices.  
     - **Circular Distance:** Account for the wrap-around by considering the distance from the query index to the neighbor via the end or beginning of the array.  

5. **Handling Single Occurrence:**  
   - **Step:** If a value occurs only once in the array, return `-1` for that query since there is no other index to compare.  
---

### Example Run

Let's consider an example with:

- **Input:**  
  `nums = [1, 3, 1, 4, 1, 3, 2]`  
  `queries = [0, 3, 5]`

#### **Query 0 (index 0):**
- **Element:** `nums[0] = 1`
- **Indices for 1:** `[0, 2, 4]` (from the hash map)  
- **Binary Search:** Finds the position of index `0` in `[0, 2, 4]` is at position `0`.  
- **Neighbors:**  
  - **Left Neighbor:** Wrap-around gives index `4` (last element).  
  - **Right Neighbor:** Index `2` (next element).
- **Distance Calculations:**  
  - Direct distance from `0` to `2`: `|0 - 2| = 2`  
  - Circular distance from `0` to `4`: `|0 + 7 - 4| = 3` (since `n = 7`)
- **Result:** Minimum distance is `min(2, 3) = 2`.

#### **Query 1 (index 3):**
- **Element:** `nums[3] = 4`
- **Indices for 4:** `[3]`  
- **Result:** Since `4` appears only once, the answer is `-1`.

#### **Query 2 (index 5):**
- **Element:** `nums[5] = 3`
- **Indices for 3:** `[1, 5]`
- **Binary Search:** Finds the position of index `5` in `[1, 5]` is at position `1`.  
- **Neighbors:**  
  - **Left Neighbor:** Index `1` (previous element in the list).  
  - **Right Neighbor:** Wrap-around gives index `1` (first element, since we're at the end of the list).
- **Distance Calculations:**  
  - Direct distance: `|5 - 1| = 4`  
  - Circular distance: `|7 - 5 + 1| = 3` (via the circular path)  
- **Result:** Minimum distance is `min(4, 3) = 3`.

**Final Output:** `[2, -1, 3]`

# Complexity
- Time complexity: $$O(n + q * log n)$$
    - n: Represents the number of elements in the input array nums.

    - q: Represents the number of queries in the queries array.

- Space complexity: $$O(n + q)$$
    - n: Represents the number of elements in the input array nums.

    - q: Represents the number of queries in the queries array.


# Code
```cpp []
class Solution {
public:
    int binsearch(vector <int> &arr, int l, int h, int &key){
        int m = floor((l+h)/2);
        if(arr[m] == key)return m;
        if(key<arr[m]) return binsearch(arr, l, m-1, key);
        else return binsearch(arr, m+1, h, key);
    }
    vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
        vector<int> res;
        int n = nums.size();
        unordered_map <int, vector <int>>H;
        for(int i =0; i<nums.size(); i++){
            H[nums[i]].push_back(i);
        }
        for(int q: queries){
            int num = nums[q];
            vector <int> &indexes = H[num]; // Reference to avoid copy (reduces the time complexity)
            int m = indexes.size();

            // Find position using binary search
            int i = binsearch(indexes, 0, m-1, q);
            int dist = -1;

            // calculate circular neighbors
            int left = (i+(m-1))%m;
            int right = (i+1)%m;
            if(!(m==1)){
                dist = min(abs(q-indexes[left]), abs(q-indexes[right])); // non-circular left and right distance 
                dist = min(abs(n-q+indexes[right]), dist); // circular right distance
                dist = min(abs(q+n-indexes[left]), dist); // circular left distance
            }
            res.push_back(dist);
        }
        return res;
    }
};
```
['Array', 'Hash Table', 'Binary Search', 'C++']