Minimize the Maximum Adjacent Element Difference
HardUpdated: Aug 2, 2025
Practice on:
Problem
You are given an array of integers nums. Some values in nums are missing and are denoted by -1.
You can choose a pair of positive integers (x, y) exactly once and replace each missing element with either x or y.
You need to minimize**** themaximum absolute difference between adjacent elements of nums after replacements.
Return the minimum possible difference.
Examples
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 <= 10^5nums[i]is either -1 or in the range[1, 109].
Solution
Method 1 – Binary Search + Greedy
Intuition
We want to minimize the maximum adjacent difference after filling all -1s with either x or y (chosen once). The best way is to try all possible values for x and y, and for each, use binary search to find the minimum possible maximum difference.
Approach
- For each possible value of x and y (from 1 to max in nums or reasonable bound), try all pairs (x, y).
- For each pair, use binary search to find the minimum possible maximum adjacent difference after filling -1s with x or y.
- For each candidate difference, check if it is possible to fill -1s such that the maximum adjacent difference does not exceed this value.
- For each -1, try both x and y and check adjacent differences.
- Return the minimum found.
Code
C++
class Solution {
public:
int minimizeMaxDiff(vector<int>& nums) {
int n = nums.size();
int mx = 0;
for (int v : nums) if (v != -1) mx = max(mx, v);
int ans = INT_MAX;
for (int x = 1; x <= mx + 1; ++x) {
for (int y = x; y <= mx + 1; ++y) {
int lo = 0, hi = 1e9;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
bool ok = true;
vector<int> arr = nums;
for (int i = 0; i < n; ++i) {
if (arr[i] == -1) {
int left = (i > 0) ? arr[i-1] : -1;
int right = (i < n-1) ? arr[i+1] : -1;
int best = -1;
for (int v : {x, y}) {
bool valid = true;
if (left != -1 && abs(left - v) > mid) valid = false;
if (right != -1 && abs(right - v) > mid) valid = false;
if (valid) best = v;
}
if (best == -1) { ok = false; break; }
arr[i] = best;
}
}
for (int i = 1; i < n; ++i) {
if (abs(arr[i] - arr[i-1]) > mid) ok = false;
}
if (ok) hi = mid;
else lo = mid + 1;
}
ans = min(ans, lo);
}
}
return ans;
}
};
Go
func minimizeMaxDiff(nums []int) int {
n := len(nums)
mx := 0
for _, v := range nums {
if v != -1 && v > mx {
mx = v
}
}
ans := 1 << 30
for x := 1; x <= mx+1; x++ {
for y := x; y <= mx+1; y++ {
lo, hi := 0, 1e9
for lo < hi {
mid := lo + (hi-lo)/2
arr := make([]int, n)
copy(arr, nums)
ok := true
for i := 0; i < n; i++ {
if arr[i] == -1 {
left := -1
if i > 0 {
left = arr[i-1]
}
right := -1
if i < n-1 {
right = arr[i+1]
}
best := -1
for _, v := range []int{x, y} {
valid := true
if left != -1 && abs(left-v) > mid {
valid = false
}
if right != -1 && abs(right-v) > mid {
valid = false
}
if valid {
best = v
}
}
if best == -1 {
ok = false
break
}
arr[i] = best
}
}
for i := 1; i < n; i++ {
if abs(arr[i]-arr[i-1]) > mid {
ok = false
}
}
if ok {
hi = mid
} else {
lo = mid + 1
}
}
if lo < ans {
ans = lo
}
}
}
return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
Java
class Solution {
public int minimizeMaxDiff(int[] nums) {
int n = nums.length, mx = 0, ans = Integer.MAX_VALUE;
for (int v : nums) if (v != -1) mx = Math.max(mx, v);
for (int x = 1; x <= mx + 1; ++x) {
for (int y = x; y <= mx + 1; ++y) {
int lo = 0, hi = (int)1e9;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int[] arr = nums.clone();
boolean ok = true;
for (int i = 0; i < n; ++i) {
if (arr[i] == -1) {
int left = (i > 0) ? arr[i-1] : -1;
int right = (i < n-1) ? arr[i+1] : -1;
int best = -1;
for (int v2 : new int[]{x, y}) {
boolean valid = true;
if (left != -1 && Math.abs(left - v2) > mid) valid = false;
if (right != -1 && Math.abs(right - v2) > mid) valid = false;
if (valid) best = v2;
}
if (best == -1) { ok = false; break; }
arr[i] = best;
}
}
for (int i = 1; i < n; ++i) {
if (Math.abs(arr[i] - arr[i-1]) > mid) ok = false;
}
if (ok) hi = mid;
else lo = mid + 1;
}
ans = Math.min(ans, lo);
}
}
return ans;
}
}
Kotlin
class Solution {
fun minimizeMaxDiff(nums: IntArray): Int {
val n = nums.size
var mx = 0
for (v in nums) if (v != -1) mx = maxOf(mx, v)
var ans = Int.MAX_VALUE
for (x in 1..mx+1) {
for (y in x..mx+1) {
var lo = 0
var hi = 1_000_000_000
while (lo < hi) {
val mid = lo + (hi-lo)/2
val arr = nums.copyOf()
var ok = true
for (i in 0 until n) {
if (arr[i] == -1) {
val left = if (i > 0) arr[i-1] else -1
val right = if (i < n-1) arr[i+1] else -1
var best = -1
for (v2 in listOf(x, y)) {
var valid = true
if (left != -1 && abs(left-v2) > mid) valid = false
if (right != -1 && abs(right-v2) > mid) valid = false
if (valid) best = v2
}
if (best == -1) { ok = false; break }
arr[i] = best
}
}
for (i in 1 until n) {
if (abs(arr[i]-arr[i-1]) > mid) ok = false
}
if (ok) hi = mid
else lo = mid + 1
}
ans = minOf(ans, lo)
}
}
return ans
}
fun abs(x: Int) = if (x < 0) -x else x
}
Python
def minimize_max_adjacent_diff(nums: list[int]) -> int:
n = len(nums)
mx = max((v for v in nums if v != -1), default=1)
ans = float('inf')
for x in range(1, mx+2):
for y in range(x, mx+2):
lo, hi = 0, int(1e9)
while lo < hi:
mid = (lo + hi) // 2
arr = nums[:]
ok = True
for i in range(n):
if arr[i] == -1:
left = arr[i-1] if i > 0 else -1
right = arr[i+1] if i < n-1 else -1
best = -1
for v in (x, y):
valid = True
if left != -1 and abs(left-v) > mid:
valid = False
if right != -1 and abs(right-v) > mid:
valid = False
if valid:
best = v
if best == -1:
ok = False
break
arr[i] = best
for i in range(1, n):
if abs(arr[i]-arr[i-1]) > mid:
ok = False
if ok:
hi = mid
else:
lo = mid + 1
ans = min(ans, lo)
return ans
Rust
impl Solution {
pub fn minimize_max_adjacent_diff(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mx = nums.iter().filter(|&&v| v != -1).max().cloned().unwrap_or(1);
let mut ans = i32::MAX;
for x in 1..=mx+1 {
for y in x..=mx+1 {
let mut lo = 0;
let mut hi = 1_000_000_000;
while lo < hi {
let mid = lo + (hi-lo)/2;
let mut arr = nums.clone();
let mut ok = true;
for i in 0..n {
if arr[i] == -1 {
let left = if i > 0 { arr[i-1] } else { -1 };
let right = if i < n-1 { arr[i+1] } else { -1 };
let mut best = -1;
for &v in &[x, y] {
let mut valid = true;
if left != -1 && (left-v).abs() > mid { valid = false; }
if right != -1 && (right-v).abs() > mid { valid = false; }
if valid { best = v; }
}
if best == -1 { ok = false; break; }
arr[i] = best;
}
}
for i in 1..n {
if (arr[i]-arr[i-1]).abs() > mid { ok = false; }
}
if ok { hi = mid; } else { lo = mid+1; }
}
if lo < ans { ans = lo; }
}
}
ans
}
}
TypeScript
class Solution {
minimizeMaxAdjacentDiff(nums: number[]): number {
const n = nums.length;
const mx = Math.max(...nums.filter(v => v !== -1), 1);
let ans = Number.MAX_SAFE_INTEGER;
for (let x = 1; x <= mx+1; ++x) {
for (let y = x; y <= mx+1; ++y) {
let lo = 0, hi = 1e9;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
const arr = nums.slice();
let ok = true;
for (let i = 0; i < n; ++i) {
if (arr[i] === -1) {
const left = i > 0 ? arr[i-1] : -1;
const right = i < n-1 ? arr[i+1] : -1;
let best = -1;
for (const v of [x, y]) {
let valid = true;
if (left !== -1 && Math.abs(left-v) > mid) valid = false;
if (right !== -1 && Math.abs(right-v) > mid) valid = false;
if (valid) best = v;
}
if (best === -1) { ok = false; break; }
arr[i] = best;
}
}
for (let i = 1; i < n; ++i) {
if (Math.abs(arr[i]-arr[i-1]) > mid) ok = false;
}
if (ok) hi = mid;
else lo = mid + 1;
}
if (lo < ans) ans = lo;
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(M^2 * N * log(maxV))- Where
Mis the range of possible x and y,Nis the array length, andmaxVis the value bound.
- Where
- 🧺 Space complexity:
O(N)- For the working array.