Minimize the Maximum Adjacent Element Difference

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15



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

1
2
3
4
5
6
7
8



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

1
2
3
4
5
6
7
8



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^5
nums[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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


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 }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


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 M is the range of possible x and y, N is the array length, and maxV is the value bound.
🧺 Space complexity: O(N)
- For the working array.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Binary Search + Greedy#

Intuition#

Approach#

Code#

Complexity#