Watch 10 video solutions for Minimum Seconds to Equalize a Circular Array, a medium level problem involving Array, Hash Table. This walkthrough by codingMohan has 2,371 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed array nums containing n integers.
At each second, you perform the following operation on the array:
i in the range [0, n - 1], replace nums[i] with either nums[i], nums[(i - 1 + n) % n], or nums[(i + 1) % n].Note that all the elements get replaced simultaneously.
Return the minimum number of seconds needed to make all elements in the array nums equal.
Example 1:
Input: nums = [1,2,1,2] Output: 1 Explanation: We can equalize the array in 1 second in the following way: - At 1st second, replace values at each index with [nums[3],nums[1],nums[3],nums[3]]. After replacement, nums = [2,2,2,2]. It can be proven that 1 second is the minimum amount of seconds needed for equalizing the array.
Example 2:
Input: nums = [2,1,3,3,2] Output: 2 Explanation: We can equalize the array in 2 seconds in the following way: - At 1st second, replace values at each index with [nums[0],nums[2],nums[2],nums[2],nums[3]]. After replacement, nums = [2,3,3,3,3]. - At 2nd second, replace values at each index with [nums[1],nums[1],nums[2],nums[3],nums[4]]. After replacement, nums = [3,3,3,3,3]. It can be proven that 2 seconds is the minimum amount of seconds needed for equalizing the array.
Example 3:
Input: nums = [5,5,5,5] Output: 0 Explanation: We don't need to perform any operations as all elements in the initial array are the same.
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 109Problem Overview: You get a circular array nums. Every second, each element can adopt the value of one of its neighbors. The goal is to determine the minimum number of seconds required for the entire array to become equal.
The circular nature means the first and last elements are neighbors. If a value appears multiple times, those positions can spread outward simultaneously. The problem becomes figuring out how long it takes for the largest gap between identical values to be filled.
Approach 1: Simulate Spread over Time (O(n²) time, O(n) space)
This approach directly models the process. At each second, elements copy values from adjacent positions. Conceptually this behaves like a multi-source spread where every index holding the same value expands outward one step per second. You repeatedly simulate rounds until all elements become equal. Implementation typically uses temporary arrays or queue-based propagation to track updates each second.
The main drawback is repeated scanning of the array. In the worst case, you simulate many seconds and process n elements per step, leading to O(n²) time complexity with O(n) auxiliary space. This method is useful for understanding the mechanics of the problem but does not scale well for large inputs.
Approach 2: Count and Track Character Frequency (O(n) time, O(n) space)
The optimal insight: the spread time for a value depends on the largest distance between its occurrences. If the array contains multiple indices with the same number, they act as simultaneous sources that fill the gaps between them. For each value, store all its indices using a hash table. Then compute the circular gaps between consecutive occurrences.
Because the array is circular, also consider the wrap-around distance between the last and first index. The worst gap determines how long propagation takes. Each second fills two positions of a gap (spreading from both sides), so the time needed is gap / 2 using integer division. Track the maximum gap for each value and compute its required seconds. The answer is the minimum time across all values.
This method performs a single pass to collect indices and another pass to evaluate gaps. Total complexity is O(n) time and O(n) space. The logic relies on efficient indexing in an array and constant-time lookups via a hash table.
Recommended for interviews: The hash map gap analysis is what interviewers expect. It shows you recognized the propagation pattern and reduced the problem to distance between identical values. Mentioning the simulation approach first demonstrates understanding of the process, but the O(n) solution proves strong algorithmic optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Spread over Time | O(n²) | O(n) | Useful for understanding the propagation process or when constraints are very small |
| Count and Track Character Frequency (Gap Analysis) | O(n) | O(n) | Best general solution; handles large arrays efficiently using hash map indexing |