Skip to main content
Talentd

Minimum Seconds to Equalize a Circular Array - Solution & Explanation

MediumArrayHash Table12 min readAsked at: Amazon
Practice this problem

Problem Statement

You are given a 0-indexed array nums containing n integers.

At each second, you perform the following operation on the array:

  • For every index 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 <= 105
  • 1 <= nums[i] <= 109

Approach Overview

Problem 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 1: Count and Track Character Frequency

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Simulate Spread over Time

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.

Code

CJava

C

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Enumeration

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulate Spread over TimeO(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

Video Solution

2808. Minimum Seconds to Equalize a Circular Array | O(N^3) - O(N*N) - O(N) | Leetcode Biweekly 110 • codingMohan • 2,388 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Seconds to Equalize a Circular Array easy or hard?
Minimum Seconds to Equalize a Circular Array is considered a medium difficulty problem. The challenge is recognizing that the spread from multiple identical values happens simultaneously, which allows the solution to be reduced to computing maximum gaps in a circular array.
Minimum Seconds to Equalize a Circular Array Python/Java solution
Python and Java implementations typically build a dictionary or HashMap from value to index list, compute circular gaps, and track the maximum gap for each value. The result is the minimum gap // 2 across all values. Both implementations run in O(n) time with O(n) extra space.
How to solve Minimum Seconds to Equalize a Circular Array in O(n)?
Store all indices of each number in a hash map. For each value, compute the maximum distance between consecutive indices, including the wrap-around gap between the last and first positions in the circular array. The time required for that value is gap // 2. Return the minimum time among all values.
What is the best approach for Minimum Seconds to Equalize a Circular Array?
The optimal approach tracks the indices of each value using a hash map and computes the largest circular gap between consecutive occurrences. The time needed for that value to fill the gap is gap / 2 because the spread happens from both sides. Evaluating this for all values gives the minimum required seconds. This solution runs in O(n) time and O(n) space.
Is Minimum Seconds to Equalize a Circular Array asked at Google/Amazon/Meta?
This problem reflects patterns commonly used in interviews at companies like Amazon, Google, and Meta where array propagation or distance-based reasoning appears. The key interview skill tested is recognizing how simultaneous spreading reduces the problem to analyzing gaps between identical values.
What data structure is used in Minimum Seconds to Equalize a Circular Array?
The primary data structure is a hash table that maps each value to the list of indices where it appears. Arrays are used for storing the input and iterating through positions, while the hash map enables efficient grouping and gap calculations.
What is the time complexity of Minimum Seconds to Equalize a Circular Array?
The optimal solution runs in O(n) time because each element is processed a constant number of times while building index lists and computing gaps. Space complexity is O(n) for storing indices of each value in a hash map. A naive simulation approach can degrade to O(n²) time.

Ready to solve this problem?

Practice Minimum Seconds to Equalize a Circular Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays