3357. Minimize the Maximum Adjacent Element Difference
SourceWeekly Contest 424 Q4DifficultyHardRating3077
Description
You are given an array of integers nums. Some values in nums are missing and are denoted by -1.
You must choose a pair of positive integers (x, y) exactly once and replace each missing element with either x or y.
You need to minimize the maximum absolute difference between adjacent elements of nums after replacements.
Return the minimum possible difference.
Example 1:
Input: nums = [1,2,-1,10,8]
Output: 4
Explanation:
By choosing the pair as (6, 7), nums can be changed to [1, 2, 6, 10, 8].
The absolute differences between adjacent elements are:
|1 - 2| == 1|2 - 6| == 4|6 - 10| == 4|10 - 8| == 2
Example 2:
Input: nums = [-1,-1,-1]
Output: 0
Explanation:
By choosing the pair as (4, 4), nums can be changed to [4, 4, 4].
Example 3:
Input: nums = [-1,10,-1,8]
Output: 1
Explanation:
By choosing the pair as (11, 9), nums can be changed to [11, 10, 9, 8].
Constraints:
2 <= nums.length <= 105nums[i]is either -1 or in the range[1, 109].
Solutions
Solution 1
Thinking
We replace every \(-1\) by a value in \([1,\textit{limit}]\) to minimize the maximum adjacent difference. With \(n \le 10^5\) we binary-search that maximum.
Filled neighbors give a lower bound. Gaps are runs of \(-1\) that we fill with at most two constants, and we test whether those constants can meet both ends under threshold \(d\).
A run that is too long or whose ends differ by more than \(2d\) rejects \(d\). The smallest feasible \(d\) is the answer.
1 | |
1 | |
1 | |
1 | |