Minimum Seconds to Equalize a Circular Array

Minimum Seconds to Equalize a Circular Array - 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.

Input & Output

Example 1 — Mixed Values

$ Input: nums = [1,2,1,3,1]

› Output: 1

💡 Note: Value 1 is at positions [0,2,4]. It can spread to adjacent positions in 1 second, covering the entire array fastest.

Example 2 — Two Values

$ Input: nums = [2,1,1,2]

› Output: 1

💡 Note: Both values 1 and 2 are well distributed. Each takes 1 second to spread completely.

Example 3 — All Same

$ Input: nums = [5,5,5,5]

› Output: 0

💡 Note: All elements are already equal, no spreading needed.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 25 M Meta 20 A Amazon 15

The key insight is that each value spreads outward from its initial positions. We need to find which value can cover the entire circular array fastest by analyzing the maximum gap between its positions. Best approach calculates gap distances directly. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n³)	O(n)	Try each unique value and simulate the spreading process step by step
Optimized Distance Calculation	O(n²)	O(n)	Calculate spreading time mathematically for each value without simulation

Brute Force Simulation — Algorithm Steps

Step 1: Find all unique values in the array
Step 2: For each unique value, simulate spreading from its initial positions
Step 3: Count seconds until the value covers all positions
Step 4: Return the minimum seconds across all values

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Unique Values

Extract all unique values: 1, 2, 3

Simulate Value 1

Start from positions with 1, spread each second

Find Minimum

Compare seconds needed for each value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int* nums, int n) {
    int uniqueVals[1000];
    int uniqueCount = 0;
    
    // Find unique values
    for (int i = 0; i < n; i++) {
        bool found = false;
        for (int j = 0; j < uniqueCount; j++) {
            if (uniqueVals[j] == nums[i]) {
                found = true;
                break;
            }
        }
        if (!found) {
            uniqueVals[uniqueCount++] = nums[i];
        }
    }
    
    int minSeconds = 1000000;
    
    for (int u = 0; u < uniqueCount; u++) {
        int target = uniqueVals[u];
        bool current[1000];
        
        for (int i = 0; i < n; i++) {
            current[i] = (nums[i] == target);
        }
        
        int seconds = 0;
        bool allDone = false;
        
        while (!allDone && seconds <= n) {
            allDone = true;
            for (int i = 0; i < n; i++) {
                if (!current[i]) {
                    allDone = false;
                    break;
                }
            }
            
            if (allDone) break;
            
            bool nextState[1000];
            for (int i = 0; i < n; i++) {
                nextState[i] = current[i] || current[(i-1+n)%n] || current[(i+1)%n];
            }
            
            memcpy(current, nextState, sizeof(bool) * n);
            seconds++;
        }
        
        if (allDone && seconds < minSeconds) {
            minSeconds = seconds;
        }
    }
    
    return minSeconds;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each unique value (up to n), simulate up to n seconds, each taking O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Store current state and next state arrays during simulation

⚡ Linearithmic Space

29.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler