Minimum Seconds to Equalize a Circular Array

Med

#2512Time: O(U * n^2), where U is the number of unique elements and n is the array size. In the worst case, U can be n, leading to a complexity of O(n^3).Space: O(n), where n is the size of the array. This is required to store copies of the array and helper data structures for each step of the simulation.

Data structures

Array Hash Table

Prompt

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 <= 10⁵
1 <= nums[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the process of equalizing the array for every possible target value. The target values can only be the numbers initially present in the array. For each unique number in the input array, we treat it as a potential target. We then simulate the spread of this target value second by second until the entire array is filled with it. The minimum number of seconds over all possible targets is the answer.

Algorithm

Find all unique numbers in nums to identify potential target values.
Initialize min_time to a very large value.
For each unique number target:
- Create a temporary copy of the nums array.
- Initialize seconds = 0.
- Loop until all elements in the temporary array are equal to target:
  1. Increment seconds.
  2. Create a new array next_state for the next second's configuration.
  3. Find all indices j where the temporary array currently has the value target.
  4. For each such index j, the value target can spread to j-1, j, and j+1 (circularly). Mark these positions as being able to become target in the next step.
  5. Populate next_state: if a position can become target, set it to target. Otherwise, keep its old value.
  6. Replace the temporary array with next_state for the next iteration.
- After the loop terminates, update min_time = min(min_time, seconds).
Return min_time.

Walkthrough

The core idea is to test every unique number from the input nums as the final value of the equalized array. For a chosen target value x, we start with the initial array and simulate the operation. In each second, a position i can become x if nums[i], nums[i-1], or nums[i+1] is already x. We repeat this process, counting the seconds, until the whole array becomes x. We do this for all unique initial numbers and take the minimum of the seconds counted.

1// This approach is conceptual and too slow for the given constraints.2import java.util.*;3 4class Solution {5    public int minimumSeconds(List<Integer> nums) {6        int n = nums.size();7        Set<Integer> uniqueElements = new HashSet<>(nums);8        int minSeconds = Integer.MAX_VALUE;9 10        for (int target : uniqueElements) {11            List<Integer> currentNums = new ArrayList<>(nums);12            int seconds = 0;13            while (true) {14                long countTarget = 0;15                for(int val : currentNums) {16                    if (val == target) {17                        countTarget++;18                    }19                }20                if (countTarget == n) {21                    break;22                }23 24                seconds++;25                List<Integer> nextNums = new ArrayList<>(currentNums);26                Set<Integer> canBecomeTarget = new HashSet<>();27                for (int i = 0; i < n; i++) {28                    if (currentNums.get(i) == target) {29                        canBecomeTarget.add(i);30                        canBecomeTarget.add((i - 1 + n) % n);31                        canBecomeTarget.add((i + 1) % n);32                    }33                }34 35                for (int idx : canBecomeTarget) {36                    nextNums.set(idx, target);37                }38                currentNums = nextNums;39            }40            minSeconds = Math.min(minSeconds, seconds);41        }42        return minSeconds;43    }44}

Complexity

Time

O(U * n^2), where U is the number of unique elements and n is the array size. In the worst case, U can be n, leading to a complexity of O(n^3).

Space

O(n), where n is the size of the array. This is required to store copies of the array and helper data structures for each step of the simulation.

Trade-offs

Pros

Conceptually simple and directly follows the problem statement's description of the operation.

Cons

Extremely inefficient due to its high time complexity, making it impractical for the given constraints.
Involves repeated array copying and iteration within nested loops, leading to poor performance.
Likely to cause a 'Time Limit Exceeded' (TLE) error on most platforms.

Instead of simulating, we can analyze the problem mathematically. To make all elements equal to a value x, x must spread from its initial positions to cover the entire array. The time required is determined by the largest "gap" between any two consecutive occurrences of x in the circular array. The time to cover a gap of size d is floor(d/2) seconds. We can calculate this for every unique number in the array and find the minimum time.

Algorithm

Use a HashMap<Integer, List<Integer>> to store the indices of each number. The key will be the number, and the value will be a list of its indices.
Iterate through the input array nums and populate the HashMap. The lists of indices will be naturally sorted as we iterate from left to right.
Initialize min_seconds to a large value (e.g., n).
Iterate through each number x and its list of indices positions in the HashMap.
- Let the list of indices be p_0, p_1, ..., p_{k-1}.
- Calculate the maximum gap between consecutive occurrences. Initialize max_gap = 0.
- First, calculate the circular gap between the last and first occurrence: gap = (n - p_{k-1}) + p_0. Update max_gap with this value.
- Then, iterate from i = 1 to k-1 and update max_gap = max(max_gap, p_i - p_{i-1}).
- The time required for this target x is time_for_x = max_gap / 2 (using integer division).
- Update min_seconds = min(min_seconds, time_for_x).
Return min_seconds.

Walkthrough

The key insight is that the problem can be solved independently for each unique number present in the initial array. For any target value x, the time it takes to make the whole array x depends on the maximum distance any element has to "travel". An element at index i can become x in s seconds if its circular distance to an initial occurrence of x is at most s. To make the whole array x, every position must be within s seconds of an initial x. This means s must be at least the maximum of these minimum distances, which is determined by the midpoint of the largest gap between two consecutive occurrences of x. If the largest gap has a length of max_gap, the time required is floor(max_gap / 2).

1import java.util.*;2 3class Solution {4    public int minimumSeconds(List<Integer> nums) {5        int n = nums.size();6        Map<Integer, List<Integer>> pos = new HashMap<>();7        for (int i = 0; i < n; i++) {8            pos.computeIfAbsent(nums.get(i), k -> new ArrayList<>()).add(i);9        }10 11        int minSeconds = Integer.MAX_VALUE;12 13        for (List<Integer> indices : pos.values()) {14            int maxGap = 0;15            // First, calculate the circular gap between the last and first occurrence16            maxGap = indices.get(0) + n - indices.get(indices.size() - 1);17 18            // Then, calculate the gaps between consecutive occurrences19            for (int i = 1; i < indices.size(); i++) {20                maxGap = Math.max(maxGap, indices.get(i) - indices.get(i - 1));21            }22 23            // The time needed is half of the largest gap24            minSeconds = Math.min(minSeconds, maxGap / 2);25        }26 27        return minSeconds;28    }29}

Complexity

Time

O(n). Populating the HashMap takes O(n). Iterating through the map's values involves visiting each index once across all lists, which is also O(n) in total.

Space

O(n). In the worst case, if all elements are unique, the HashMap will store `n` keys. If all elements are the same, it will store one key with a list of `n` indices. In both scenarios, the total space used is proportional to `n`.

Trade-offs

Pros

Highly efficient with linear time complexity, easily passing the given constraints.
Avoids costly simulation by using a direct mathematical formula.
Solves the problem in a single pass after grouping indices.

Cons

Requires extra space for the HashMap to store indices, which can be up to O(n).

Solutions

Solution

1class Solution {2public3  int minimumSeconds(List<Integer> nums) {4    Map<Integer, List<Integer>> d = new HashMap<>();5    int n = nums.size();6    for (int i = 0; i < n; ++i) {7      d.computeIfAbsent(nums.get(i), k->new ArrayList<>()).add(i);8    }9    int ans = 1 << 30;10    for (List<Integer> idx : d.values()) {11      int m = idx.size();12      int t = idx.get(0) + n - idx.get(m - 1);13      for (int i = 1; i < m; ++i) {14        t = Math.max(t, idx.get(i) - idx.get(i - 1));15      }16      ans = Math.min(ans, t / 2);17    }18    return ans;19  }20}

1class Solution {2public:3  int minimumSeconds(vector<int> &nums) {4    unordered_map<int, vector<int>> d;5    int n = nums.size();6    for (int i = 0; i < n; ++i) {7      d[nums[i]].push_back(i);8    }9    int ans = 1 << 30;10    for (auto &[_, idx] : d) {11      int m = idx.size();12      int t = idx[0] + n - idx[m - 1];13      for (int i = 1; i < m; ++i) {14        t = max(t, idx[i] - idx[i - 1]);15      }16      ans = min(ans, t / 2);17    }18    return ans;19  }20};

1class Solution:2    def minimumSeconds(self, nums: List[int]) -> int: d = defaultdict(list) for i, x in enumerate(nums): d[x]. append(i) ans = inf n = len(nums) for idx in d . values(): t = idx[0] + n - idx[- 1] for i, j in pairwise(idx): t = max(t, j - i) ans = min(ans, t // 2) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem