2808. Minimum Seconds to Equalize a Circular Array

link

First thought, find the higest frequency number. However, it could be sticked to each other.

Then think about the expansion, so we can find the maximum gap between the same element. And care about the left , and right.(cause it's circular array)

In contest

class Solution:
    def minimumSeconds(self, nums: List[int]) -> int:
        
        n = len(nums)
        
        M = defaultdict(list)
        
        for i in range(n):
            M[nums[i]].append(i)
            
        
        res = float('inf')
        
        for ll in M.values():
            current = float('-inf')
            # we don't need this actually
            if len(ll) == 1:
                continue
            ll.append(ll[0]+n)
            for i in range(1, len(ll) - 1):
                current = max(current, (ll[i] - ll[i-1]) // 2, (ll[i+1] - ll[i]) // 2)
                
            res = min(res, current)
        
        # we don't need this actually
        return n // 2 if res == float('inf') else res

Optimized

class Solution:
    def minimumSeconds(self, nums: List[int]) -> int:
        
        n = len(nums)
        
        M = defaultdict(list)
        
        for i in range(n):
            M[nums[i]].append(i)
            
        res = float('inf')
        
        for ll in M.values():
            current = float('-inf')
            ll.append(ll[0]+n)
            for a, b in pairwise(ll):
                current = max(current, (b-a)//2)
                
            res = min(res, current)
            
        return res