Leetcode Weekly Contest 441 Q2. Closest Equal Element Queries

Q2. Closest Equal Element Queries

⭐Important learnings wrt 🔁Circular Array🔁  : 

 The two distances between elt at i & j  : 

• forward_dist  = (j-i+n) % n;
• backward_dist = (i-j+n) % n; 

How to get the two indexes `d` distance away from a given index, i ?

• next_d_idx = ( i + d) % n ;
• prev_d_idx = ( i - d + n) % n ;

As a special case when d=1, we can get next & prev elements as : 

• next_idx = (i+1) % n 
• prev_idx = (i-1+n ) % n

Alternatively, the +1 for forward should be thought as +(n-1) for backward or more generally, +d should be thought as +(n-d) when marching in backward direction.

class Solution {

    public List<Integer> solveQueries(int[] nums, int[] queries) {

        int n = nums.length;

        Map<Integer, List<Integer>> map = new HashMap<>(); //number - indexe(s)

        for(int i=0; i<n; i++)

            map.computeIfAbsent(nums[i], k->new ArrayList<>()).add(i);

        Integer[] nearestDistCache = new Integer[n]; // num[index] - nearestDist

        for (List<Integer> idxList : map.values()) {

            int len = idxList.size();

            if(len==1)

                nearestDistCache[idxList.get(0)] = -1;

            else

                for(int i = 0; i < len; i++) {

                    int currIdx = idxList.get(i);

   

                    int prevIdx = idxList.get((i - 1 + len) % len);

                    int nextIdx = idxList.get((i + 1) % len);

               

                    int distPrev = Math.min((currIdx - prevIdx + n) % n, (prevIdx - currIdx + n) % n);

                    int distNext = Math.min((nextIdx - currIdx + n) % n, (currIdx - nextIdx + n) % n);

               

                    nearestDistCache[currIdx] = Math.min(distPrev , distNext);

                }

        }

        // get required values from cache

        List<Integer> res = new ArrayList<>();

        for(int index : queries)

            res.add(nearestDistCache[index]);

        return res;

    }

    public int getMinDist(int i, int j, int n) {

        int fwd_dist = (j-i+n)%n;

        int bkw_dist = (i-j+n)%n;

        return Math.min(fwd_dist, bkw_dist);

    }

}