Find number with smallest max gap
When the array is equalized, it means that one of the numbers (let\'s call it x) in the original array is present at each position of the array, so that the arr
When the array is equalized, it means that one of the numbers (let\'s call it `x`) in the original array is present at each position of the array, so that the array becomes `[x,x,x,x ...]`\n\nHow long would it take to equalize the array once we\'ve chosen `x`?\nEach second, `x` will expand left and right from its current position:\n\n`[xyzyzyx] =>  [xxzyzxx] => [xxxyxxx]`... \n\nFor every \'gap\' between two positions of `x`, this gap will be smaller by 2 positions every second. How to compute the gaps? If we call `pos`, an array containing all the positions of `x` in the original array (in order), the time to fill gap `i `will be `(pos[i-1] - pos[i])/2`. So the time to fill all the gaps will be `\u230AmaxGap/2\u230B`.\n\nHow to find `x`? Well it\'s the number in the array which has the smallest `maxGap`!\n\nThe algorithm is the following:\n1. create a map of positions, which contains for each number its list of positions\n2. for each number, compute its max gap\n3. chose the number which has the smallest max gap\n4. return `\u230AminMaxGap/2\u230B`\n\n```\nclass Solution {\n\n    private int n;\n\n    public int minimumSeconds(List<Integer> nums) {\n        n = nums.size();\n        Map<Integer, List<Integer>> positions = new HashMap<>();\n\n        for (int i = 0; i < n; i++) {\n            Integer v = nums.get(i);\n            positions.computeIfAbsent(v, _k -> new ArrayList<>()).add(i);\n        }\n\n        int min = Integer.MAX_VALUE;\n\n        for (List<Integer> value : positions.values()) {\n            min = Math.min(getMaxGap(value), min);\n        }\n\n        return min/2;\n\n    }\n\n    public int getMaxGap(List<Integer> positions){\n        int max = 0;\n        int prev = positions.get(positions.size()-1)-n; // first gap is between first position and last position\n        for (int p : positions) {\n            max = Math.max(p - prev, max);\n            prev = p;\n        }\n\n        return max;\n    }\n}\n```
['Java']