Practice/Amazon/Leetcode 2808. Minimum Seconds to Equalize a Circular Array

Leetcode 2808. Minimum Seconds to Equalize a Circular Array

CodingOptional

Problem

You are given a circular array nums where each element can spread its value to adjacent positions. In each second, every element can simultaneously become either its current value or the value of one of its neighbors (left or right). Because the array is circular, the first and last elements are considered neighbors.

Your task is to determine the minimum number of seconds required to make all elements in the array equal to the same value.

Requirements

1. Calculate the minimum time needed for any single value to propagate throughout the entire array
2. Consider that values spread outward from their initial positions at a rate of one position per second
3. Handle the circular nature of the array where the first and last positions are adjacent
4. Return the optimal result across all possible target values

Constraints

• 1 ≤ nums.length ≤ 105
• 1 ≤ nums[i] ≤ 109
• You may assume the answer fits in a 32-bit integer

Examples

Example 1:

Input: nums = [1, 2, 1, 2] Output: 1 Explanation: Value 1 appears at indices 0 and 2. After 1 second, positions 1 and 3 can adopt the value 1 from their neighbors, making the entire array [1, 1, 1, 1].

Example 2:

Input: nums = [5, 5, 5, 5] Output: 0 Explanation: All elements are already equal.

Example 3:

Input: nums = [2, 1, 3, 3, 2] Output: 2 Explanation: If we choose value 3 (at indices 2 and 3), the maximum distance any position needs to travel is 2 steps. Similarly for value 2. The minimum across all choices is 2 seconds.