[Java/Python 3] Min of the longest distance between same numbers.
Intuition:\nAssume the final values of the modified array nums are all xs, then x must be among the original input array.\n\nSuppose i < j, nums[i] == nums[j] =
**Intuition:**\nAssume the final values of the modified array `nums` are all `x`s, then `x` must be among the original input array.\n\nSuppose `i < j`, `nums[i] == nums[j] == x` and `nums[k] != x`for all `k` such that `i < k < j`. we can derive following conclusion:\n\n**Since each second we can only change the neighbors of `x`s, we can  at most  change 2 numbers among those between 2 `x`s each second. Therefore, at least `(j - i) / 2` seconds needed to change to `x` all numbers between `i` and `j`.**\n\n----\n\n**Algorithm:**\n\n 1. Use `HashMap/dict` to store the indices of same numbers;\n2. Traverse the indices of same numbers to find the longest distance between them and divide it by 2;\n3. Find the minimum value among the values in step 2. \n\n```java\n    public int minimumSeconds(List<Integer> nums) {\n        int n = nums.size(), ans = n;\n        Map<Integer, List<Integer>> indices = new HashMap<>();\n        for (int i = 0; i < n; ++i) {\n            indices.computeIfAbsent(nums.get(i), l -> new ArrayList<>()).add(i);    \n        }\n        for (var l : indices.values()) {\n            l.add(l.get(0) + n);\n            int longest = 0;\n            for (int i = 1; i < l.size(); ++i) {\n                longest = Math.max(longest, (l.get(i) - l.get(i - 1)));\n            }\n            ans = Math.min(ans, longest / 2);\n        }\n        return ans;\n    }\n```\n\n```python\n    def minimumSeconds(self, nums: List[int]) -> int:\n        n, indices = len(nums), defaultdict(list)\n        for i, num in enumerate(nums):\n            indices[num].append(i)\n        ans = n        \n        for l in indices.values():\n            l.append(l[0] + n)\n            ans = min(ans, max(y - x for x, y in pairwise(l)) // 2)\n        return ans\n```\n\nFor the above python 3 code, we can trade `O(n)` space and time for better readability as follows:\n```python\n    def minimumSeconds(self, nums: List[int]) -> int:\n        nums += nums # make circular array.\n        indices = defaultdict(list)\n        for i, num in enumerate(nums):\n            indices[num].append(i)\n        return min(max(b - a for a, b in pairwise(l)) // 2 for l in indices.values())\n```\n**Analysis:**\n\nTime & space: `O(n)`, where `n = nums.length`.\n\n----\n\n**Q & A:**\n\n*Q1:*  l.append(l[0] + n) --> why is this done?\n\n (For the following answer, credit to -- **@IndominouS**)\n*A1:*  To calculate the circular distance between the 1st and last indices.\n\nAs it is circular array the right element of the last element will be first element of the array.\n\n(first,second,last) refers to indices of appearances.\n\n[__first__second _ _ last _ _ _n - 1]\n\nImagine adding the array two times:\n\n[__first__second _ _ last _ _ _n - 1] + [__first__second _ _ last _ _ _n - 1]\n\nNow to calculate the right partner of last element we need to add the index of first element after rotating.\nSo after rotating we have traversed over n elements and the first will arrive at (first)th index hence we add ((index of first) + n)\nso as to calculate [(index of first after rotation) - last index)]\n\n**Summary**\nThis is a circular array, and we need to find the right neighbor for the last index, the first index, which need to add the size of the array `n`to compute the correct distance between the two neighbors.\n\n*Q2:* Why is it `O(n)`, as we have the following nested for loops?\n```python\n        for l in indices.values():\n            l.append(l[0] + n)\n            ans = min(ans, max(y - x for x, y in pairwise(l)) // 2)\n```\n\n*A2:* Suppose we had NOT appended any element for each list `l`. the code would be as follows:\n```python\n        for l in indices.values():\n            ans = min(ans, max(y - x for x, y in pairwise(l)) // 2)\n```\nSince all list `l`s are from the indices of input, no more and no less,  we actually traverse all `n` indices of the input and the time cost is `O(n)`. \n\nLet us further suppose we double the sizes of all list `l`s, \n```python\n        for l in indices.values():\n            l += l\n            ans = min(ans, max(y - x for x, y in pairwise(l)) // 2)\n```\nthen we at most visit `2 * n` elements after completion of the nested for loops, and the time cost `O(2 * n) = O(n)`. \n\nFor the original code, each list `l` adds only `1` element, and `len(l) + 1 <= 2 * len(l)`, that is, the increased size of list `l` is still no more than the double size of the original list `l`. \n\nTherefore, the time cost is `O(n + m) <= O(n + n) = O(n)`, where `m` is the number of  list `l`s, of course `m <= n`.\n\n**End of Q & A**\n\n----\n\nPlease\n# Upvote\n\nif the post is helpful for you.
['Java', 'Python3']