LeetCode 2808 - Minimum Seconds to Equalize a Circular Array

The problem gives a circular array nums of length n. At each second, every element in the array can be replaced simultaneously by either itself, its previous neighbor, or its next neighbor.

leetcodemediumarrayhash-table

LeetCode Problem 2808

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

Problem Understanding

The problem gives a circular array nums of length n. At each second, every element in the array can be replaced simultaneously by either itself, its previous neighbor, or its next neighbor. The task is to determine the minimum number of seconds required to make all elements equal.

In simpler terms, the array elements "propagate" their values to adjacent positions each second. Because the array is circular, the first and last elements are considered neighbors. The goal is to determine how long it takes for one of the repeated numbers to spread across the entire array.

The input is guaranteed to be non-empty (n >= 1), with values up to 10^9. The constraints indicate that n can be as large as 10^5, so any solution must avoid simulating each second naively, as that would result in a time complexity of O(n^2) or worse.

Key edge cases include arrays where all elements are already equal (resulting in 0 seconds), arrays where values alternate, and arrays with repeated values that are spread unevenly. Since the array is circular, propagation can wrap around from end to start.

Approaches

Brute Force

A brute-force approach would simulate each second: for every element, update it with the maximum frequency among itself and its neighbors, and repeat until all elements are equal. This guarantees correctness because it follows the problem's rules directly. However, it is too slow for large arrays, as each step takes O(n), and the number of steps can be up to n in the worst case, leading to O(n^2) complexity.

Optimal Approach

The key observation is that the minimum number of seconds is determined by the largest distance between consecutive occurrences of the same value in the circular array. If you consider a specific value, the farthest gap between its occurrences tells you how long it will take to propagate that value to fill that gap.

Formally, for each unique number, record all its indices. For consecutive indices (i, j) in the circular sense (considering the wrap-around gap between the last and first index), the required seconds to cover that segment is (gap - 1) // 2, because propagation spreads to adjacent elements each second. The maximum over all gaps for a number gives the time needed for that number to dominate the array. The answer is the minimum among all unique numbers.

This approach is efficient because it only requires a single pass to record indices and compute maximum gaps per number.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Simulate propagation second by second
Optimal O(n) O(n) Compute maximum gaps per unique number and choose minimum

Algorithm Walkthrough

  1. Initialize a dictionary to map each number to a list of its indices.
  2. Iterate through nums and populate the dictionary with the indices where each number occurs.
  3. For each number, consider its list of sorted indices. Compute the gaps between consecutive indices, including the circular gap from the last index back to the first.
  4. For each gap, calculate the number of seconds required to propagate a value to fill the gap using (gap - 1) // 2.
  5. Track the maximum propagation time for each number. This represents the seconds needed for that number to fill the entire array.
  6. Return the minimum value among all maximum propagation times for all numbers.

Why it works: The propagation spreads outward one step per second. The largest empty gap between occurrences of a number determines the bottleneck. By finding the largest such gap and computing (gap - 1) // 2, we capture the minimal seconds needed for that value to dominate. Minimizing over all numbers ensures we find the absolute minimum time.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def minimumSeconds(self, nums: List[int]) -> int:
        n = len(nums)
        positions = defaultdict(list)
        
        for i, num in enumerate(nums):
            positions[num].append(i)
        
        min_seconds = float('inf')
        
        for num, indices in positions.items():
            max_gap = 0
            m = len(indices)
            for i in range(m):
                # Circular gap: next index minus current index
                next_index = indices[(i + 1) % m]
                current_index = indices[i]
                gap = (next_index - current_index - 1 + n) % n
                max_gap = max(max_gap, gap)
            # Propagation takes ceil(gap/2), integer division achieves same
            min_seconds = min(min_seconds, (max_gap + 1) // 2)
        
        return min_seconds

Explanation: The code first maps each number to its indices. For each number, it computes gaps between consecutive occurrences in a circular manner. The largest gap determines the seconds needed for that number to propagate. Finally, the code returns the minimum seconds over all numbers.

Go Solution

func minimumSeconds(nums []int) int {
    n := len(nums)
    positions := make(map[int][]int)
    
    for i, num := range nums {
        positions[num] = append(positions[num], i)
    }
    
    minSeconds := n
    
    for _, indices := range positions {
        m := len(indices)
        maxGap := 0
        for i := 0; i < m; i++ {
            nextIndex := indices[(i+1)%m]
            currentIndex := indices[i]
            gap := (nextIndex - currentIndex - 1 + n) % n
            if gap > maxGap {
                maxGap = gap
            }
        }
        seconds := (maxGap + 1) / 2
        if seconds < minSeconds {
            minSeconds = seconds
        }
    }
    
    return minSeconds
}

Go-specific notes: Go requires manual handling of slices and maps. We avoid integer overflow concerns since n <= 1e5. The circular gap calculation is identical to Python.

Worked Examples

Example 1: nums = [1,2,1,2]

Value Indices Gaps Max Gap Seconds
1 [0,2] 1, 2 1 1
2 [1,3] 1, 2 1 1

Minimum seconds = 1.

Example 2: nums = [2,1,3,3,2]

Value Indices Gaps Max Gap Seconds
2 [0,4] 3, 0 3 2
1 [1] 4 4 2
3 [2,3] 0, 3 3 2

Minimum seconds = 2.

Example 3: nums = [5,5,5,5]

Only one value, already equal. Seconds = 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to build indices and another pass per unique number to compute gaps, total O(n)
Space O(n) Dictionary of indices for each unique number, total up to n

The complexity is efficient for the problem constraints.

Test Cases

# Basic examples
assert Solution().minimumSeconds([1,2,1,2]) == 1  # alternating pattern
assert Solution().minimumSeconds([2,1,3,3,2]) == 2  # uneven spread
assert Solution().minimumSeconds([5,5,5,5]) == 0  # all equal

# Edge cases
assert Solution().minimumSeconds([1]) == 0  # single element
assert Solution().minimumSeconds([1,2]) == 1  # two distinct elements
assert Solution().minimumSeconds([1,2,3,4,5]) == 2  # all distinct
assert Solution().minimumSeconds([1,1,2,2,1,1]) == 1  # repeating clusters
Test Why
[1,2,1,2] Alternating values
[2,1,3,3,2] Uneven spread of values
[5,5,5,5] All equal, zero seconds
[1] Single element array
[1,2] Minimal array with two different numbers
[1,2,3,4,5] All unique, propagation from any value
[1,1,2,2,1,1] Clustered repeats, tests gap calculation

Edge Cases

The first edge case is an array of length 1. The function must immediately return 0, as propagation is unnecessary. The implementation handles this naturally since the dictionary will contain one key with a single index, resulting in zero seconds.

The second edge case is when all elements are already equal. The algorithm must return 0 and not miscompute gaps. In our approach, the maximum gap for a single-value array is 0, so (0 + 1) // 2 = 0 correctly returns 0.

The third edge case is a circular propagation that wraps around the end to the start.