Python - Greedy + Hash Table - 727 ms Beats 100%
Intuition\nThis problem seems truly complicated at the first glance, but actually we only need to find the minimum of (the maximum interval between two same num
# Intuition\nThis problem seems truly complicated at the first glance, but actually we only need to find the minimum of (the maximum interval between two same numbers) for all numbers that appeared in the string, and the answer is the minimum / 2, rounded up.\nTo do this in O(n) time, we use a dict of keep track of all info that we need and iterate through nums.\n\n# Approach\nWe first retrieve all the numbers that appeared in nums, and use these as the key for our info dict. Their corresponding values are lists [cur_max_interval, last_index, head_num].\ncur_max_interval is the maximum interval met between two current keys;\nlast_index is the last index at which the num is the current key, initialized to -1;\nhead_num is the number of num before the first occurence of the current key.\n\nLet\'s start the iteration.\n1. If last_index is -1, it means that the current index is the first occurence of the current number, so we update the corresponding head_num using i.\n2. If not, we get the interval length ending at the current index, which is i - last_index - 1, updating cur_max_interval if the current one is larger.\nFor both situations, set last_index to i\n\nAfter the above iteration over nums, we got all the largest intervals between two occurences of a key, but as the problem is asking for a circular array, we also need to consider the interval which starts after the last occurence and ends before the first occurence of a key, which equals to head_num + tail_num(len(nums) - last_index). \n\nFind the key with the smallest largest interval (a bit awkward, but easy to understand as you follow the steps), the answer is that interval length doing a rounded-up division by two.\n\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution:\n    def minimumSeconds(self, nums: List[int]) -> int:\n        ele = Counter(nums).keys()\n        result = inf\n        info = {}\n        length = len(nums)\n\n        for key in ele:\n            # [cur_max_interval, last_index, head_num]\n            info[key] = [-inf, -1, 0]\n\n        for i, num in enumerate(nums):\n            cur = info[num]\n\n            if cur[1] == -1:\n                cur[1] = i\n                cur[2] = i\n            elif cur[1] != i:\n                cur[0] = max(cur[0], i-cur[1]-1)\n                cur[1] = i\n\n        for key in ele:\n            cur = info[key]\n            if cur[0] == -inf:\n                result = min(result, (cur[2]+length-cur[1]) // 2)\n            else:\n                result = min(result, max(\n                    (cur[0]+1)//2, (cur[2]+length-cur[1]) // 2))\n\n        return result\n```\n\nPlease upvote if you find it helpful! :D
['Hash Table', 'Greedy', 'Python', 'Python3']