Minimum Seconds to Equalize a Circular Array — Solution
Minimum Seconds to Equalize a Circular Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Seconds to Equalize a Circular Array is a medium coding problem on arrays, hash table and greedy, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Greedy
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a 0-indexed array nums of n integers arranged in a circle: index n - 1 is next to index 0.
Every second, all elements are replaced simultaneously: each nums[i] becomes one of nums[i], nums[(i - 1 + n) % n] or nums[(i + 1) % n] (you choose for each index).
Return the minimum number of seconds needed to make every element of the array equal.
Example 1
Input: nums = [1,2,1,2]
Output: 1
Explanation: In one second every 2 copies a neighbouring 1, giving `[1,1,1,1]`.
Example 2
Input: nums = [2,1,3,3,2]
Output: 2
Explanation: Spreading the 3s takes two seconds: `[2,3,3,3,3]`, then `[3,3,3,3,3]`.
Example 3
Input: nums = [5,5,5,5]
Output: 0
Constraints
1 <= n == nums.length <= 10^51 <= nums[i] <= 10^9
Hints for Minimum Seconds to Equalize a Circular Array
Hint 1
Fix the final value
v. Every second, each copy ofvcan spread one step left and one step right — so the time is how far the farthest index is from its nearest copy ofv.Hint 2
Between two consecutive copies of
vthat aregpositions apart (going round the circle), the farthest index in the gap isfloor(g / 2)away from a copy.Hint 3
For each distinct value record its largest circular gap between consecutive occurrences, including the wrap-around gap from its last occurrence back to its first. Take the minimum of
floor(gap / 2)over all values.
How to solve Minimum Seconds to Equalize a Circular Array
Choosing a target value v, the copies of v flood outwards one cell per second in both directions. A gap of g steps between consecutive copies is filled from both ends in floor(g / 2) seconds, so the cost of v is half its largest circular gap.
Approach
- For each distinct value keep its first index, its last index seen so far, and its largest gap so far.
- Scanning
ifrom left to right, whennums[i]was seen before atlast, update the gap withi - last; then setlast = i. - After the scan, close the circle for each value with the gap
first + n - last(a value seen once gets the gapn). - Return the minimum of
floor(maxGap / 2)over all values.
Why it works
After t seconds the cells holding v (under the best choices) are exactly the cells within circular distance t of an original copy: each second a cell may copy a neighbour, so v spreads one step per second and no faster. A cell between copies g apart is at distance at most floor(g / 2) from one of them, with equality at the middle, so v needs exactly floor(maxGap / 2) seconds.
Complexity
- Time —
O(n) expected (hash map) - Space —
O(n)
Pitfalls
- Forgetting the wrap-around gap from the last copy to the first.
- A value that appears once has gap
n, not 0. - Simulating second by second is far too slow when the answer is large.
Reference solution
Python
from typing import List
def minimumSeconds(nums: List[int]) -> int:
n = len(nums)
first, last, gap = {}, {}, {}
for i, v in enumerate(nums):
if v in last:
gap[v] = max(gap[v], i - last[v])
else:
first[v] = i
gap[v] = 0
last[v] = i
best = n
for v in first:
g = max(gap[v], first[v] + n - last[v])
best = min(best, g // 2)
return bestJava
public static int minimumSeconds(int[] nums) {
int n = nums.length;
HashMap<Integer, int[]> info = new HashMap<>(); // value -> {first, last, gap}
for (int i = 0; i < n; i++) {
int[] e = info.get(nums[i]);
if (e == null) {
info.put(nums[i], new int[]{i, i, 0});
} else {
e[2] = Math.max(e[2], i - e[1]);
e[1] = i;
}
}
int best = n;
for (int[] e : info.values()) {
int g = Math.max(e[2], e[0] + n - e[1]);
best = Math.min(best, g / 2);
}
return best;
}C++
int minimumSeconds(vector<int>& nums) {
int n = nums.size();
unordered_map<int, array<int, 3>> info; // value -> {first, last, gap}
for (int i = 0; i < n; i++) {
auto it = info.find(nums[i]);
if (it == info.end()) {
info[nums[i]] = {i, i, 0};
} else {
auto& e = it->second;
e[2] = max(e[2], i - e[1]);
e[1] = i;
}
}
int best = n;
for (auto& kv : info) {
auto& e = kv.second;
int g = max(e[2], e[0] + n - e[1]);
best = min(best, g / 2);
}
return best;
}JavaScript
var minimumSeconds = function(nums) {
var n = nums.length;
var info = new Map(); // value -> [first, last, gap]
for (var i = 0; i < n; i++) {
var e = info.get(nums[i]);
if (e === undefined) {
info.set(nums[i], [i, i, 0]);
} else {
if (i - e[1] > e[2]) e[2] = i - e[1];
e[1] = i;
}
}
var best = n;
info.forEach(function(e) {
var g = Math.max(e[2], e[0] + n - e[1]);
if (Math.floor(g / 2) < best) best = Math.floor(g / 2);
});
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets