Minimum Seconds to Equalize a Circular Array — Editorial

Opening the reading…

Intuitionthe slowest empty stretch controls how fast a value can spread

Choose one value as the value that will fill the array. Every occurrence of that value can spread one position to the left and one position to the right per second. The positions between two consecutive occurrences therefore form empty stretches that are filled inward from both ends.

A stretch with gap positions between its boundary occurrences needs ceil(gap / 2) seconds, because the two boundaries fill it simultaneously. The value is fully spread only when its largest gap is filled, so the largest gap determines that value's required time. Finally, try every value and keep the smallest required time.

Approach

Build a hash map from each value to the sorted list of indices where it occurs. The scan visits indices from 0 to n - 1, so each stored list is already sorted and needs no separate sorting pass.

Process one value at a time and inspect every pair of consecutive occurrence indices. Consecutive occurrences bound one stretch that must be filled, so ignoring any pair could miss the time needed by that value.

For two ordinary consecutive positions vec[i] and vec[i + 1], compute the number of positions strictly between them as vec[i + 1] - vec[i] - 1. Subtracting one counts only the positions that do not already contain the chosen value.

For the final occurrence, compute the wraparound gap from vec.back() through index n - 1 and then from index 0 to vec[0]. This combines the two ends of the linear array into the single circular stretch that the ordinary pairs cannot see.

Keep the largest gap for the current value, because all of its gaps spread in parallel and the last one to fill determines when the entire circle contains that value.

Convert the largest gap to time with (maxGap + 1) / 2, which is integer arithmetic for ceil(maxGap / 2). Taking the minimum across values chooses the fastest value to spread everywhere.

Complexitythe position lists contain exactly one entry per array element

MEASURE	BOUND	WHY
Time	O(n)	The first scan inserts each index once. Later, each stored occurrence participates in exactly one gap computation for its value, including the wraparound gap for the last occurrence, so no index is processed more than a constant number of times.
Space	O(n) extra	The hash map and all position vectors together store exactly n indices, with O(n) additional buckets and vector metadata in the worst case when values are mostly distinct. The returned integer is required output and is excluded from the working-space bound.

Here, n is the array length. The total number of stored positions is n, regardless of how many distinct values occur.

Annotated solutionC++ - hashing positions and scanning circular gaps

CPPStore every value's positions, evaluate its ordinary and wraparound gaps, and minimize the resulting half-gap.

#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int minimumSeconds(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> pos;

        for (int i = 0; i < n; ++i) {
            pos[nums[i]].push_back(i);
        }

        int ans = n;
        for (auto& [value, indices] : pos) {
            int maxGap = 0;

            for (int i = 0; i < static_cast<int>(indices.size()); ++i) {
                int gap;
                if (i + 1 < static_cast<int>(indices.size())) {
                    gap = indices[i + 1] - indices[i] - 1;
                } else {
                    gap = (n - indices.back() - 1) + indices.front();
                }
                maxGap = max(maxGap, gap);
            }

            int seconds = (maxGap + 1) / 2;
            ans = min(ans, seconds);
        }

        return ans;
    }
};

The position of the wraparound calculation is important. For the last occurrence, there is no later index in the vector, but the circle still has one more consecutive pair: the last occurrence followed by the first occurrence after crossing the boundary. The expression adds the empty tail and empty head, without counting either boundary occurrence itself.