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 theminimum number of seconds needed to make all elements in the array nums equal.

Examples

Example 1

1
2
3
4
5
6
7
8
9


    
    
    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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    
    
    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

1
2
3
4
5
6
7


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

Solution

Method 1 – Greedy + Distance Calculation

Intuition

For each value, the slowest position to be equalized is the largest gap between its occurrences (circularly). The minimum seconds is the minimum over all values of the maximum gap divided by 2 (rounded up).

Approach

  1. For each unique value, collect all indices where it occurs.
  2. For each value, compute the maximum gap between consecutive indices (circularly).
  3. The answer is the minimum over all values of (max_gap // 2).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <vector>
#include <unordered_map>
#include <algorithm>
class Solution {
public:
    int minimumSeconds(vector<int>& nums) {
        int n = nums.size(), res = n;
        unordered_map<int,vector<int>> pos;
        for (int i = 0; i < n; ++i) pos[nums[i]].push_back(i);
        for (auto& [v, idxs] : pos) {
            int max_gap = 0;
            for (int i = 0; i < idxs.size(); ++i) {
                int j = (i+1)%idxs.size();
                int gap = (idxs[j]-idxs[i]+n)%n;
                max_gap = max(max_gap, gap);
            }
            res = min(res, max_gap/2);
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func minimumSeconds(nums []int) int {
    n := len(nums)
    pos := map[int][]int{}
    for i, v := range nums { pos[v] = append(pos[v], i) }
    res := n
    for _, idxs := range pos {
        maxGap := 0
        for i := range idxs {
            j := (i+1)%len(idxs)
            gap := (idxs[j]-idxs[i]+n)%n
            if gap > maxGap { maxGap = gap }
        }
        if maxGap/2 < res { res = maxGap/2 }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import java.util.*;
class Solution {
    public int minimumSeconds(List<Integer> nums) {
        int n = nums.size(), res = n;
        Map<Integer,List<Integer>> pos = new HashMap<>();
        for (int i = 0; i < n; i++) pos.computeIfAbsent(nums.get(i), k->new ArrayList<>()).add(i);
        for (List<Integer> idxs : pos.values()) {
            int maxGap = 0;
            for (int i = 0; i < idxs.size(); i++) {
                int j = (i+1)%idxs.size();
                int gap = (idxs.get(j)-idxs.get(i)+n)%n;
                maxGap = Math.max(maxGap, gap);
            }
            res = Math.min(res, maxGap/2);
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun minimumSeconds(nums: List<Int>): Int {
        val n = nums.size
        val pos = mutableMapOf<Int,MutableList<Int>>()
        nums.forEachIndexed { i,v -> pos.getOrPut(v){mutableListOf()}.add(i) }
        var res = n
        for (idxs in pos.values) {
            var maxGap = 0
            for (i in idxs.indices) {
                val j = (i+1)%idxs.size
                val gap = (idxs[j]-idxs[i]+n)%n
                maxGap = maxOf(maxGap, gap)
            }
            res = minOf(res, maxGap/2)
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from collections import defaultdict
class Solution:
    def minimumSeconds(self, nums: list[int]) -> int:
        n = len(nums)
        pos = defaultdict(list)
        for i, v in enumerate(nums):
            pos[v].append(i)
        res = n
        for idxs in pos.values():
            max_gap = 0
            for i in range(len(idxs)):
                j = (i+1)%len(idxs)
                gap = (idxs[j]-idxs[i]+n)%n
                max_gap = max(max_gap, gap)
            res = min(res, max_gap//2)
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

use std::collections::HashMap;
impl Solution {
    pub fn minimum_seconds(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut pos: HashMap<i32, Vec<usize>> = HashMap::new();
        for (i, &v) in nums.iter().enumerate() {
            pos.entry(v).or_default().push(i);
        }
        let mut res = n;
        for idxs in pos.values() {
            let mut max_gap = 0;
            for i in 0..idxs.len() {
                let j = (i+1)%idxs.len();
                let gap = (idxs[j]+n-idxs[i])%n;
                max_gap = max_gap.max(gap);
            }
            res = res.min(max_gap/2);
        }
        res as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    minimumSeconds(nums: number[]): number {
        const n = nums.length;
        const pos = new Map<number, number[]>();
        nums.forEach((v,i)=>{
            if (!pos.has(v)) pos.set(v,[]);
            pos.get(v)!.push(i);
        });
        let res = n;
        for (const idxs of pos.values()) {
            let maxGap = 0;
            for (let i = 0; i < idxs.length; i++) {
                const j = (i+1)%idxs.length;
                const gap = (idxs[j]-idxs[i]+n)%n;
                maxGap = Math.max(maxGap, gap);
            }
            res = Math.min(res, Math.floor(maxGap/2));
        }
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — One pass to collect positions, one pass to compute gaps.
  • 🧺 Space complexity: O(n) — For storing positions.