We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Seconds to Equalize a Circular Array

Number: 2920

Difficulty: Medium

Paid? No

Companies: Apple, Amazon

Problem Description

Given a circular array of integers, in one second every position can adopt one of three values: its own, its left neighbor’s, or its right neighbor’s value. Find the minimum number of seconds needed to make all the array elements equal.

Key Insights

  • The operation allows a value to “propagate” one step per second in both directions, effectively filling gaps between indices containing the same value.
  • For a candidate value (one present initially), identify every index where it occurs.
  • In a circular array, the longest contiguous segment (gap) that does not contain the candidate value determines how long it takes for that value to propagate across the entire array.
  • The minimal seconds required for a candidate is ceil(max_gap/2), where max_gap is the maximum gap (considering circularity) between consecutive indices holding that candidate.
  • Evaluate all candidate values and return the minimum seconds required.

Space and Time Complexity

Time Complexity: O(n) – We traverse the array to build the mapping and then iterate over each candidate's indices. Space Complexity: O(n) – To store the indices for each unique value.

Solution

We solve this problem by considering each candidate value that initially appears in the array. For each candidate, we:

  1. Store the indices of its occurrence in sorted order.
  2. Compute the gaps between consecutive indices (adjusting for circularity with the wrap-around gap).
  3. The propagation time needed for that candidate is the ceiling of half of the maximum gap.
  4. The answer is the minimum propagation time among all candidates.

Key steps include:

  • Use a hash table (or dictionary) to group indices by their value.
  • For each group, determine the maximum gap between indices. Don’t forget the gap between the last occurrence and the first occurrence in the circular array.
  • Use the formula (max_gap + 1) // 2 for computing the number of seconds (this equals the ceiling of max_gap/2).
  • Return the smallest computed seconds among all candidates.

Code Solutions

# Python solution with detailed comments

def minimumSeconds(nums):
    # Dictionary to store indices for each candidate value
    value_indices = {}
    n = len(nums)
    for i, num in enumerate(nums):
        if num not in value_indices:
            value_indices[num] = []
        value_indices[num].append(i)
    
    # Initialize the answer with a large number
    min_seconds = float('inf')
    
    # Evaluate each candidate value
    for num, indices in value_indices.items():
        # Sort indices even though they are added in increasing order
        indices.sort()
        max_gap = 0
        
        # Check gaps between consecutive indices
        for i in range(len(indices) - 1):
            gap = indices[i+1] - indices[i] - 1  # gap between occurrences
            max_gap = max(max_gap, gap)
        
        # Check wrap-around gap (circular array)
        wrap_gap = indices[0] + n - indices[-1] - 1
        max_gap = max(max_gap, wrap_gap)
        
        # Calculate seconds needed using ceiling division for gap propagation
        seconds = (max_gap + 1) // 2
        min_seconds = min(min_seconds, seconds)
    
    return min_seconds

# Example usage:
print(minimumSeconds([1,2,1,2]))  # Expected output: 1
print(minimumSeconds([2,1,3,3,2]))  # Expected output: 2
print(minimumSeconds([5,5,5,5]))  # Expected output: 0
← Back to All Questions