# Minimum Seconds to Equalize a Circular Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-seconds-to-equalize-a-circular-array)
Canonical: https://scaleengineer.com/dsa/problems/minimum-seconds-to-equalize-a-circular-array
**Data structures:** Array, Hash Table
---
## Problem
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 <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute-Force Simulation
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.
**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.
**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.
### Explanation
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.

```java
// This approach is conceptual and too slow for the given constraints.
import java.util.*;

class Solution {
    public int minimumSeconds(List<Integer> nums) {
        int n = nums.size();
        Set<Integer> uniqueElements = new HashSet<>(nums);
        int minSeconds = Integer.MAX_VALUE;

        for (int target : uniqueElements) {
            List<Integer> currentNums = new ArrayList<>(nums);
            int seconds = 0;
            while (true) {
                long countTarget = 0;
                for(int val : currentNums) {
                    if (val == target) {
                        countTarget++;
                    }
                }
                if (countTarget == n) {
                    break;
                }

                seconds++;
                List<Integer> nextNums = new ArrayList<>(currentNums);
                Set<Integer> canBecomeTarget = new HashSet<>();
                for (int i = 0; i < n; i++) {
                    if (currentNums.get(i) == target) {
                        canBecomeTarget.add(i);
                        canBecomeTarget.add((i - 1 + n) % n);
                        canBecomeTarget.add((i + 1) % n);
                    }
                }

                for (int idx : canBecomeTarget) {
                    nextNums.set(idx, target);
                }
                currentNums = nextNums;
            }
            minSeconds = Math.min(minSeconds, seconds);
        }
        return minSeconds;
    }
}
```
### 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`.

## Optimal Approach using Hashing and Gap Calculation
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.
**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`.
**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).
### Explanation
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)`.

```java
import java.util.*;

class Solution {
    public int minimumSeconds(List<Integer> nums) {
        int n = nums.size();
        Map<Integer, List<Integer>> pos = new HashMap<>();
        for (int i = 0; i < n; i++) {
            pos.computeIfAbsent(nums.get(i), k -> new ArrayList<>()).add(i);
        }

        int minSeconds = Integer.MAX_VALUE;

        for (List<Integer> indices : pos.values()) {
            int maxGap = 0;
            // First, calculate the circular gap between the last and first occurrence
            maxGap = indices.get(0) + n - indices.get(indices.size() - 1);

            // Then, calculate the gaps between consecutive occurrences
            for (int i = 1; i < indices.size(); i++) {
                maxGap = Math.max(maxGap, indices.get(i) - indices.get(i - 1));
            }

            // The time needed is half of the largest gap
            minSeconds = Math.min(minSeconds, maxGap / 2);
        }

        return minSeconds;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int minimumSeconds(List<Integer> nums) {
    Map<Integer, List<Integer>> d = new HashMap<>();
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      d.computeIfAbsent(nums.get(i), k->new ArrayList<>()).add(i);
    }
    int ans = 1 << 30;
    for (List<Integer> idx : d.values()) {
      int m = idx.size();
      int t = idx.get(0) + n - idx.get(m - 1);
      for (int i = 1; i < m; ++i) {
        t = Math.max(t, idx.get(i) - idx.get(i - 1));
      }
      ans = Math.min(ans, t / 2);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumSeconds(vector<int> &nums) {
    unordered_map<int, vector<int>> d;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      d[nums[i]].push_back(i);
    }
    int ans = 1 << 30;
    for (auto &[_, idx] : d) {
      int m = idx.size();
      int t = idx[0] + n - idx[m - 1];
      for (int i = 1; i < m; ++i) {
        t = max(t, idx[i] - idx[i - 1]);
      }
      ans = min(ans, t / 2);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```