---
# System prepended metadata

title: 2808. Minimum Seconds to Equalize a Circular Array
tags: [Leetcode, HashMap, Medium, Greedy]

---

Link: https://leetcode.com/problems/minimum-seconds-to-equalize-a-circular-array/description/
## 思路
不能直接greedy找出现频率最多的数字
那样的话会在这个testcase报错```[1,11,11,11,19,12,8,7,19]```
答案应该是2 但如果只看11答案就会是3

If number ```num``` appears at positions ```i``` and ```j```, it will take ```(j - i)/2``` seconds to make all numbers between ```i``` and ```j``` equal ```num```.

So, we need to find the maximum gap for all positions of ```num```

由于是circular array 因此我们还要将每个数字的```pos[0]+len(nums)```加进去
## Code
```python=
class Solution:
    def minimumSeconds(self, nums: List[int]) -> int:
        allPos = dict()
        for i, num in enumerate(nums):
            if num not in allPos:
                allPos[num] = []
            allPos[num].append(i)
        ans = math.inf
        for num in allPos.keys():
            allPos[num].append(allPos[num][0]+len(nums))
            maxGap = 0
            for i in range(len(allPos[num])-1):
                maxGap = max(maxGap, (allPos[num][i+1]-allPos[num][i])//2)
            ans = min(ans, maxGap)
        return ans
```