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.
This approach involves identifying the dominant element in the array and determining the time needed for all elements to be converted to the dominant element through allowed operations.
Use two traversals: first, to count occurrences and positions of each element, and second, to compute the minimum time needed by checking for separate sections of each repeated element.
The program uses a hash map to track indices of each number. Then, for each unique number, it calculates the maximal gap between consecutive indices. This gap represents how far apart instances of this number are, and thus how many steps it would take to propagate it through the array. Finally, it determines the minimum time needed for any number to become the universal value using the formula (max_distance + 1) // 2.
Python
JavaScript
Time Complexity: O(n), since we traverse the array a fixed number of times. Space Complexity: O(n), due to storage of elements' indices in the hash map.
This approach simulates how numbers spread across the array by utilizing a queue where each element propagates to its neighbors in a time-step manner, similar to BFS in graph traversal.
This C program simulates the spread of a number across the array by reducing the index count for each adjacent number during each time step. It uses two pointers to manage the circular queue, similar to a BFS traversal. By observing the pattern of spread, this approach evaluates when full uniformity is reached.
Time Complexity: O(n^2) in the worst case, as the array is traversed multiple times. Space Complexity: O(n), since additional memory for indices and the counter is necessary.
We assume that all elements eventually become x, and x must be an element in the array.
The number x can expand one bit to the left and right every second. If there are multiple identical x, then the time required to expand the entire array depends on the maximum distance between two adjacent x.
Therefore, we enumerate each element as the final x, calculate the maximum distance t between two adjacent elements in each x, then the final answer is min\limits_{x \in nums} \left\lfloor \frac{t}{2} \right\rfloor.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Count and Track Character Frequency | Time Complexity: O(n), since we traverse the array a fixed number of times. Space Complexity: O(n), due to storage of elements' indices in the hash map. |
| Simulate Spread over Time | Time Complexity: O(n^2) in the worst case, as the array is traversed multiple times. Space Complexity: O(n), since additional memory for indices and the counter is necessary. |
| Enumeration | — |
| 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 |
2808. Minimum Seconds to Equalize a Circular Array | O(N^3) - O(N*N) - O(N) | Leetcode Biweekly 110 • codingMohan • 2,371 views views
Watch 9 more video solutions →Practice Minimum Seconds to Equalize a Circular Array with our built-in code editor and test cases.
Practice on FleetCode