dsa-programs/Algorithms/IntegerArray/ClosestEqualElementQueries.java at master · SrinivasVadige/dsa-programs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
package Algorithms.IntegerArray;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author Srinivas Vadige, srinivas.vadige@gmail.com
 * @since 15 March 2025
 */
public class ClosestEqualElementQueries {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int[] queries = {3, 1, 2, 4, 2};
        System.out.println("solveQueries(nums, queries) => " + solveQueries(nums, queries));
        nums = new int[]{1, 2, 3, 4, 5};
        queries = new int[]{3, 1, 2, 4, 2};
        System.out.println("solveQueriesMyApproach(nums, queries) => " + solveQueriesMyApproach(nums, queries));
    }

    public static List<Integer> solveQueries(int[] nums, int[] queries) {
        int sz = nums.length;
        Map<Integer, List<Integer>> indices = new HashMap<>();
        for (int i = 0; i < sz; i++) {
            indices.computeIfAbsent(nums[i], _ -> new ArrayList<>()).add(i);
        }
        for (List<Integer> iList : indices.values()) {
            int m = iList.size();
            if (m == 1) {
                nums[iList.get(0)] = -1;
                continue;
            }
            for (int i = 0; i < m; i++) {
                int j = iList.get(i);
                int f = iList.get((i + 1) % m), b = iList.get((i - 1 + m) % m);
                int forward = Math.min((sz - j - 1) + f + 1, Math.abs(j - f));
                int backward = Math.min(Math.abs(b - j), j + (sz - b));
                nums[j] = Math.min(backward, forward);
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int q : queries) {
            res.add(nums[q]);
        }
        return res;
    }


        /**
        PATTERNS:
        ---------
        1) nums is circular iList ---> i.e n-1 is connected to 0
        2) We can find distance in two ways (1) l to r (2) circular r to l
        3) so min(1,2)
        4)
    */
    public static List<Integer> solveQueriesButTLE(int[] nums, int[] queries) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i=0; i<nums.length; i++) {
            List<Integer> l = map.getOrDefault(nums[i], new ArrayList<>());
            l.add(i);
            map.put(nums[i], l);
        }

        List<Integer> lst = new ArrayList<>();
        for (int i: queries) {
            int dist = Integer.MAX_VALUE;

            if (map.get(nums[i]).size()==1) dist=-1; // no-dups
            else {
                for (int j: map.get(nums[i])) { // iList
                    if (i==j) continue; // same index
                    // dist from left side
                    dist = Math.min(dist, Math.abs(j-i));
                    // dist from circular right side
                    dist = Math.min(dist, Math.min(j+nums.length-i, nums.length-j+i) );

                }
            }

            lst.add(dist);
        }
        return lst;
    }

    // same as above solveQueriesButTLE() but little optimized
    public static List<Integer> solveQueriesMyApproach(int[] nums, int[] queries) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i=0; i<nums.length; i++) {
            map.computeIfAbsent(nums[i], _ -> new ArrayList<>()).add(i);
            // List<Integer> l = map.getOrDefault(nums[i], new ArrayList<>());
            // l.add(i);
            // map.put(nums[i], l);
        }

        List<Integer> lst = new ArrayList<>();
        for (int i: queries) {
            int dist = Integer.MAX_VALUE;

            if (map.get(nums[i]).size()==1) dist=-1; // no-dup
            else {
                // now consider only left, left-circular, right, right-circular
                // i.e max of 4 js
                Set<Integer> jList = new HashSet<>();
                List<Integer> iList = map.get(nums[i]);
                int iInIList = Collections.binarySearch(iList, i);

                // check left
                if ( 0 != iInIList ) jList.add(iList.get(iInIList-1));
                // check left circularly
                jList.add(iList.get(iList.size()-1));
                // check right
                if (iInIList != iList.size()-1) jList.add(iList.get(iInIList+1));
                // check right circularly
                jList.add(iList.get(0));

                jList.remove(i);
                for (int j: jList) {
                    // dist from left side
                    dist = Math.min(dist, Math.abs(j-i));
                    // dist from circular right side
                    dist = Math.min(dist, i>j? nums.length-i+j : nums.length-j+i);
                }
            }
            lst.add(dist);
        }
        return lst;
    }
}