Minimum Seconds to Equalize a Circular Array

Medium
1804.

Minimum Seconds to Equalize a Circular Array

Minimum Seconds to Equalize a Circular Array is a medium coding problem on arrays, hash table and greedy, asked in Amazon and Microsoft interviews.

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^5
  • 1 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumSeconds = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= nums[i] <= 10^9

Hints for Minimum Seconds to Equalize a Circular Array

  1. Hint 1

    Fix the final value v. Every second, each copy of v can spread one step left and one step right — so the time is how far the farthest index is from its nearest copy of v.

  2. Hint 2

    Between two consecutive copies of v that are g positions apart (going round the circle), the farthest index in the gap is floor(g / 2) away from a copy.

  3. 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

  1. For each distinct value keep its first index, its last index seen so far, and its largest gap so far.
  2. Scanning i from left to right, when nums[i] was seen before at last, update the gap with i - last; then set last = i.
  3. After the scan, close the circle for each value with the gap first + n - last (a value seen once gets the gap n).
  4. 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 best

Java

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