Problem Description

You have a 0-indexed array nums containing n integers.

Every second, you perform an operation where each element in the array gets replaced simultaneously. For each index i (from 0 to n-1), you can replace nums[i] with one of three values:

• Keep it as nums[i] (no change)
• Replace it with nums[(i - 1 + n) % n] (the element to its left, wrapping around)
• Replace it with nums[(i + 1) % n] (the element to its right, wrapping around)

The key point is that all replacements happen at the same time - you're making decisions for all positions simultaneously based on the current state of the array.

Your goal is to find the minimum number of seconds needed to make all elements in the array equal to the same value.

For example, if you have an array like [1, 2, 1, 2], you want to determine how many seconds it takes to transform it into an array where all elements are the same, like [1, 1, 1, 1] or [2, 2, 2, 2].

The solution works by recognizing that the final value must be one of the values already present in the array. Each value can "spread" to adjacent positions each second. The strategy involves finding which value can spread to cover the entire array in the least amount of time. This depends on the maximum gap between consecutive occurrences of each value in the array.

Intuition

Think about what happens when we want all elements to become the same value. That target value must already exist somewhere in the array - we can't create a new value out of thin air.

Each second, a value at position i can either stay the same or copy from its neighbors. This means if we have a value x at some position, it can "spread" to adjacent positions. In one second, x can spread one position to the left and one position to the right.

If we have multiple occurrences of the same value x in the array, they all spread simultaneously. Picture it like multiple sources of the same color paint spreading outward at the same rate. The entire array will be covered when the paint from adjacent sources meets in the middle.

The key insight is that the bottleneck is the largest gap between consecutive occurrences of x. If we have x at positions [1, 3, 7] in a circular array, the gaps are the distances between consecutive positions (including the wrap-around from position 7 back to position 1).

For each gap of distance d, it takes d // 2 seconds for the values to spread from both ends and meet in the middle. The maximum gap determines the total time needed because that's the last region to be filled.

Therefore, our strategy is:

1. For each unique value in the array, find all its positions
2. Calculate the maximum gap between consecutive occurrences (remembering the array is circular)
3. The time needed for this value is max_gap // 2
4. The answer is the minimum time across all possible values

This transforms the problem from simulating the spreading process to a geometric problem of finding maximum gaps between positions.

Solution Approach

The implementation follows the strategy of finding the maximum gap between consecutive occurrences for each unique value:

Step 1: Group positions by value

d = defaultdict(list)
for i, x in enumerate(nums):
    d[x].append(i)

We create a dictionary where each key is a unique value from the array, and the value is a list of all positions where this value appears. For example, if nums = [1, 2, 1, 2], then d = {1: [0, 2], 2: [1, 3]}.

Step 2: Calculate maximum gap for each value For each unique value and its list of positions:

for idx in d.values():
    t = idx[0] + n - idx[-1]  # wrap-around gap
    for i, j in pairwise(idx):
        t = max(t, j - i)      # consecutive gaps

• First, we calculate the wrap-around gap: idx[0] + n - idx[-1]. This represents the distance from the last occurrence back to the first occurrence, going around the circular array.
• Then we check all consecutive pairs of positions using pairwise(idx) to find gaps between adjacent occurrences.
• We keep track of the maximum gap t for this value.

Step 3: Calculate minimum time

ans = min(ans, t // 2)

For each value's maximum gap t, we need t // 2 seconds for the values to spread and meet in the middle. We use integer division because the values spread from both ends simultaneously.

Step 4: Return the minimum

return ans

We return the minimum time across all possible target values.

Example walkthrough: If nums = [1, 2, 3, 1]:

• Value 1 appears at positions [0, 3]: gaps are 3-0=3 and 0+4-3=1, max gap is 3, time needed is 3//2=1
• Value 2 appears at position [1]: only one occurrence, gap is 4 (entire array), time needed is 4//2=2
• Value 3 appears at position [2]: only one occurrence, gap is 4, time needed is 4//2=2
• Minimum time is 1 second

Example Walkthrough

Let's trace through the algorithm with nums = [2, 1, 3, 3, 2]:

Step 1: Group positions by value

• Value 1 appears at position [1]
• Value 2 appears at positions [0, 4]
• Value 3 appears at positions [2, 3]

So our dictionary is: {1: [1], 2: [0, 4], 3: [2, 3]}

Step 2: Calculate maximum gap for each value

For value 1 (positions [1]):

• Only one occurrence, so the gap is the entire array length: 5
• Time needed: 5 // 2 = 2 seconds

For value 2 (positions [0, 4]):

• Wrap-around gap: 0 + 5 - 4 = 1 (from position 4 to 0 going clockwise)
• Gap between consecutive positions: 4 - 0 = 4
• Maximum gap: max(1, 4) = 4
• Time needed: 4 // 2 = 2 seconds

For value 3 (positions [2, 3]):

• Wrap-around gap: 2 + 5 - 3 = 4 (from position 3 to 2 going clockwise)
• Gap between consecutive positions: 3 - 2 = 1
• Maximum gap: max(4, 1) = 4
• Time needed: 4 // 2 = 2 seconds

Step 3: Find minimum time

• Minimum across all values: min(2, 2, 2) = 2 seconds

Verification: Let's see how value 2 spreads (one possible solution):

• Second 0: [2, 1, 3, 3, 2] - value 2 at positions 0 and 4
• Second 1: [2, 2, 3, 2, 2] - value 2 spreads to positions 1 and 3
• Second 2: [2, 2, 2, 2, 2] - value 2 spreads to position 2

The array becomes uniform after 2 seconds, confirming our answer.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. The algorithm iterates through the array once to build the dictionary (O(n)), then for each unique value, it processes its indices. Since each index appears exactly once across all lists in the dictionary, the total work done in the second loop is also O(n). The pairwise operation for each value's indices processes consecutive pairs, and across all values, this totals to at most n pairs.

The space complexity is O(n), where n is the length of the array. The dictionary d stores at most n indices distributed across different keys. In the worst case where all elements are the same, one list contains all n indices. In the best case where all elements are unique, we have n lists each containing one index. Either way, the total space used is proportional to n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting the Circular Nature of the Array

The most common mistake is not accounting for the wrap-around gap between the last and first occurrence of a value. Many solutions only check gaps between consecutive occurrences in the linear array.

Incorrect approach:

# WRONG: Only checking linear gaps
for indices in value_to_indices.values():
    max_gap = 0
    for curr_index, next_index in pairwise(indices):
        max_gap = max(max_gap, next_index - curr_index)
    min_seconds = min(min_seconds, max_gap // 2)

Why it fails: For nums = [1, 2, 2, 1], value 2 appears at positions [1, 2]. The linear gap is only 1, suggesting time needed is 0. But the wrap-around gap is 1 + 4 - 2 = 3, requiring 1 second.

Correct approach:

# Include wrap-around gap calculation
max_gap = indices[0] + n - indices[-1]  # Don't forget this!
for curr_index, next_index in pairwise(indices):
    max_gap = max(max_gap, next_index - curr_index)

2. Handling Single Occurrence Values Incorrectly

When a value appears only once in the array, there are no "consecutive" occurrences, but the value still needs to spread across the entire array.

Incorrect approach:

# WRONG: Skipping values that appear only once
if len(indices) == 1:
    continue  # This would miss valid solutions!

Why it fails: A value appearing once can still be the optimal choice. It needs n // 2 seconds to spread across the entire array.

Correct approach:

# Handle single occurrences properly
if len(indices) == 1:
    max_gap = n  # The gap is the entire array
else:
    max_gap = indices[0] + n - indices[-1]
    for curr_index, next_index in pairwise(indices):
        max_gap = max(max_gap, next_index - curr_index)

3. Using Ceiling Division Instead of Floor Division

Some might think we need to round up when calculating seconds from gaps.

Incorrect approach:

# WRONG: Using ceiling division
import math
min_seconds = min(min_seconds, math.ceil(max_gap / 2))

Why it fails: Values spread from both ends simultaneously. For a gap of size g, they meet after exactly g // 2 steps. Using ceiling division would overestimate the time needed.

Example: Gap of 5 requires 5 // 2 = 2 seconds (values spread 2 steps from each end, covering 4 positions, with 1 position overlap).