DSA SheetMedium
EditorialPractice

GREEDY › PART I

Minimum Seconds to Equalize a Circular Array

MediumEditorial · 7 minGenerated by gpt-5.6-luna · Aug 27

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

a circular array with repeated occurrences of one chosen valueA ring represents the circular array. Two marked positions contain the chosen value, and the arc between them contains the largest number of unmarked positions. Layers from both marked positions move inward along that arc, one position per second on each side. The final middle position is reached after ceil(gap / 2) seconds, showing why the largest empty arc controls the total time.circular array · chosen value vleft occurrenceright occurrencespread inward7 gap positionsmiddle positionceil(7 / 2) = 4 s

Approach

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(n) extraThe 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.

Common mistakestwo index calculations that look plausible and fail on boundary cases

Previous · Mice and Cheese