# Minimize the Maximum Adjacent Element Difference
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimize-the-maximum-adjacent-element-difference)
Canonical: https://scaleengineer.com/dsa/problems/minimize-the-maximum-adjacent-element-difference
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
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 <= 105`
* `nums[i]` is either -1 or in the range `[1, 109]`.

# Approaches
## Binary Search with O(N^2) Check
This approach uses binary search on the answer. The core of the problem is to create a `check(d)` function to determine if a given maximum difference `d` is achievable. This function first determines the valid range for each missing value by propagating constraints from its neighbors. Then, it solves the resulting "two-stabber" problem: finding two points `x` and `y` (with `|x-y| <= d`) that intersect all the required value ranges. This version of `check(d)` solves the two-stabber problem by iterating through all potential stabbing points, leading to a quadratic time complexity.
**Time:** O(N^2 * log(MAX_VAL)), where N is the length of `nums` and MAX_VAL is the upper bound of the search space (10^9). The `check` function takes O(N^2) and it's called O(log(MAX_VAL)) times. · **Space:** O(N) to store the ranges for each element.
**Pros:** The binary search framework is correct for this type of minimization problem.; The constraint propagation logic correctly narrows down the possibilities for replacement values.
**Cons:** The `check(d)` function has a time complexity of `O(N^2)`, which is too slow given the constraints (`N <= 10^5`).; The overall time complexity of `O(N^2 * log(MAX_VAL))` will likely result in a Time Limit Exceeded error.
### Explanation
The problem asks to minimize a maximum value, which strongly suggests binary searching on the answer. Let the answer be `d`. Our goal is to find the smallest `d` for which we can replace the `-1`s and satisfy the condition.

The `check(d)` function works as follows:
1.  **Base Case Check**: First, iterate through the array and check if any pair of adjacent non-`-1` elements `nums[i]` and `nums[i+1]` has a difference greater than `d`. If so, `d` is impossible, and `check(d)` returns `false`.
2.  **Constraint Propagation**: We determine the valid range of values for each `-1`. An elegant way to do this is by propagating constraints. We maintain a `range[i] = [min_val, max_val]` for each position `i`.
    *   For `nums[i] != -1`, `range[i] = [nums[i], nums[i]]`.
    *   For `nums[i] == -1`, we initialize `range[i]` to a very large range, e.g., `[1, 2*10^9]`.
    *   We then do two passes:
        *   **Left-to-right**: For `i` from 1 to `n-1`, `range[i]` is constrained by `range[i-1]`. Any value in `range[i]` must be at most `d` away from some value in `range[i-1]`. This means the new `range[i]` is the intersection of the old `range[i]` and `[range[i-1].min - d, range[i-1].max + d]`.
        *   **Right-to-left**: A similar pass from `n-2` down to `0` further tightens the ranges.
    *   If at any point a range becomes empty (`min > max`), `d` is impossible.
3.  **Two-Stabber Problem (O(N^2) solution)**: After propagation, we have a list of `m` required intervals for the `m` missing numbers. We need to find if there exist `x, y` with `|x-y| <= d` that stab all these intervals. We can test this by picking a candidate for `x` from the endpoints of the intervals. For each candidate `x`:
    *   Identify all intervals not stabbed by `x`.
    *   Calculate the intersection of these unstabbed intervals.
    *   If this intersection `[L, R]` is valid, check if it overlaps with `[x-d, x+d]`. If it does, a valid `y` exists, and `check(d)` is `true`.
    *   If we exhaust all candidates for `x` without success, `check(d)` is `false`.

This `check` function is `O(N^2)` because of the nested loops in the two-stabber part. The overall complexity is `O(N^2 * log(MAX_VAL))`. 

```java
// The main binary search structure would call this check function.
private boolean checkSlow(int d, int[] nums) {
    int n = nums.length;
    // Steps 1 & 2: Constraint Propagation (O(N))
    // ... (This part is identical to the optimal approach's check function)
    long[][] ranges = new long[n][2];
    // ... initialization and propagation logic ...

    // Step 3: Collect intervals for -1s
    List<long[]> requiredIntervals = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (nums[i] == -1) {
            if (ranges[i][0] > ranges[i][1]) return false; // Check from propagation
            requiredIntervals.add(ranges[i]);
        }
    }

    if (requiredIntervals.isEmpty()) {
        return true;
    }

    // O(N^2) check for two-stabber problem
    for (long[] p1 : requiredIntervals) {
        // Candidate 1 for x: left endpoint
        if (canStabWith(p1[0], d, requiredIntervals)) return true;
        // Candidate 2 for x: right endpoint
        if (canStabWith(p1[1], d, requiredIntervals)) return true;
    }

    return false;
}

private boolean canStabWith(long x, int d, List<long[]> intervals) {
    long[] intersection = {1L, 2_000_000_000L};
    for (long[] p : intervals) {
        if (x < p[0] || x > p[1]) { // If x doesn't stab p
            intersection[0] = Math.max(intersection[0], p[0]);
            intersection[1] = Math.min(intersection[1], p[1]);
        }
    }

    if (intersection[0] > intersection[1]) { // No common intersection for y
        // This means all intervals were stabbed by x
        return true; 
    }

    // Check if intersection for y overlaps with [x-d, x+d]
    long y_min = Math.max(intersection[0], x - d);
    long y_max = Math.min(intersection[1], x + d);

    return y_min <= y_max;
}
```
### Algorithm
*   The main idea is to binary search on the answer, which is the minimum possible maximum adjacent difference, let's call it `d`.
*   The range for binary search would be from `0` to `10^9`.
*   For each `d` in the binary search, we need a function `check(d)` that verifies if it's possible to choose `(x, y)` such that the maximum adjacent difference is at most `d`.
*   The `check(d)` function first calculates the possible range of values for each missing element. This is done by propagating constraints from neighbors.
    1.  Initialize a range `[min_val, max_val]` for each element. For non-missing elements `v`, the range is `[v, v]`. For missing elements, it's a wide range like `[1, 2*10^9]`.
    2.  Perform a left-to-right pass. For each element `i`, its range is updated by intersecting its current range with `[range[i-1].min - d, range[i-1].max + d]`.
    3.  Perform a right-to-left pass, updating `range[i]` based on `range[i+1]` similarly.
    4.  If any range becomes invalid (`min > max`), `d` is not possible.
*   After propagation, we have a set of required intervals for all missing elements. We need to find if there exist two numbers `x` and `y` with `|x - y| <= d` that can "stab" all these intervals (i.e., for each interval, at least one of `x` or `y` is inside it).
*   This subproblem can be solved by trying out candidate values for `x`. The endpoints of the required intervals are good candidates. For each candidate `x`, we find all intervals not stabbed by `x`. We then compute the intersection of these unstabbed intervals. If this intersection is non-empty, say `[L, R]`, we check if we can pick a `y` from `[L, R]` such that `|x - y| <= d`. This means checking if `[L, R]` and `[x-d, x+d]` overlap.
*   Since there can be `O(N)` intervals and for each candidate `x` we check all other intervals, this check takes `O(N^2)` time.

## Binary Search with O(N log N) Check
This is the optimal approach, which also employs binary search on the answer `d`. It features a much more efficient `check(d)` function. The constraint propagation part remains the same. The improvement lies in solving the two-stabber problem in `O(N log N)` time. Instead of testing individual points, we analyze the structure of the required intervals. By sorting the intervals and merging them, we can find the connected components of their union. A valid solution with two points `x` and `y` exists if and only if there are at most two such components and, in the case of two, their separation is no more than `d`.
**Time:** O(N log N * log(MAX_VAL)). The `check` function is dominated by sorting the `m` intervals (where `m <= N`), which takes `O(m log m)`. This is called `O(log(MAX_VAL))` times by the binary search. · **Space:** O(N) to store the ranges and the list of required intervals.
**Pros:** This approach is highly efficient and passes within the given time limits.; It correctly models the problem and breaks it down into standard subproblems (binary search, interval manipulation).; The logic for solving the two-stabber problem by analyzing connected components is robust.
**Cons:** The logic is more complex to implement correctly compared to the naive check.; Requires careful handling of edge cases and interval manipulations.
### Explanation
This approach refines the `check(d)` function to achieve a better time complexity, making it feasible for the given constraints. The overall structure of binary searching on the answer `d` remains.

**Optimized `check(d)` function:**

The first two steps (checking fixed neighbors and constraint propagation) are identical to the previous approach and run in `O(N)` time.

**1. & 2. Constraint Propagation**: Same as before. We generate the final required intervals for all `-1` positions.

**3. Efficient Two-Stabber Solution (O(N log N))**:
Let `S` be the list of `m` required intervals. The problem is to find if `x, y` exist with `|x-y| <= d` that stab all intervals in `S`.
*   **Key Insight**: If a set of intervals can be stabbed by two points, their union cannot have more than two disjoint parts (connected components). If there were three, say `C1, C2, C3`, we would need at least three points to stab one interval from each.
*   **Algorithm**:
    a. Collect the list of `m` required intervals from the propagation step.
    b. If the list is empty, return `true`.
    c. Sort the intervals by their starting points. This costs `O(m log m)`.
    d. Find the connected components by merging overlapping/adjacent intervals. This can be done in a single pass (`O(m)`) over the sorted intervals.
    e. Analyze the number of components:
        *   If there is 1 or 0 component, it means all intervals are connected (or there are no intervals). A single point can stab them all. We can choose `x=y`, so `|x-y|=0 <= d`. Return `true`.
        *   If there are more than 2 components, it's impossible. Return `false`.
        *   If there are exactly 2 components, `[L1, R1]` and `[L2, R2]`, we must pick one point from each component. To satisfy `|x-y| <= d`, the minimum distance between the components must be at most `d`. The distance is `L2 - R1` (assuming sorted components). So, we return `true` if `L2 - R1 <= d`, and `false` otherwise.

This optimized check runs in `O(N log N)` time, dominated by sorting the intervals. The total time complexity of the solution is `O(N log N * log(MAX_VAL))`, which is efficient enough.

```java
public int minimizeMaxDifference(int[] nums) {
    int low = 0, high = 1_000_000_000, ans = high;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (check(mid, nums)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return ans;
}

private boolean check(int d, int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n - 1; i++) {
        if (nums[i] != -1 && nums[i + 1] != -1 && Math.abs(nums[i] - nums[i + 1]) > d) {
            return false;
        }
    }

    long[][] ranges = new long[n][2];
    for (int i = 0; i < n; i++) {
        if (nums[i] != -1) {
            ranges[i][0] = ranges[i][1] = nums[i];
        } else {
            ranges[i][0] = 1;
            ranges[i][1] = 2_000_000_000L; // Large enough positive range
        }
    }

    for (int i = 1; i < n; i++) {
        ranges[i][0] = Math.max(ranges[i][0], ranges[i - 1][0] - d);
        ranges[i][1] = Math.min(ranges[i][1], ranges[i - 1][1] + d);
        if (ranges[i][0] > ranges[i][1]) return false;
    }

    for (int i = n - 2; i >= 0; i--) {
        ranges[i][0] = Math.max(ranges[i][0], ranges[i + 1][0] - d);
        ranges[i][1] = Math.min(ranges[i][1], ranges[i + 1][1] + d);
        if (ranges[i][0] > ranges[i][1]) return false;
    }

    List<long[]> requiredIntervals = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (nums[i] == -1) {
            requiredIntervals.add(ranges[i]);
        }
    }

    if (requiredIntervals.isEmpty()) return true;

    requiredIntervals.sort(Comparator.comparingLong(a -> a[0]));

    List<long[]> components = new ArrayList<>();
    if (!requiredIntervals.isEmpty()) {
        components.add(requiredIntervals.get(0).clone());
        for (int i = 1; i < requiredIntervals.size(); i++) {
            long[] current = requiredIntervals.get(i);
            long[] lastComp = components.get(components.size() - 1);
            if (current[0] <= lastComp[1]) { // Merge overlapping intervals
                lastComp[1] = Math.max(lastComp[1], current[1]);
            } else {
                components.add(current.clone());
            }
        }
    }

    if (components.size() > 2) return false;
    if (components.size() <= 1) return true;
    
    return components.get(1)[0] - components.get(0)[1] <= d;
}
```
### Algorithm
*   This approach also uses binary search on the answer `d`.
*   The `check(d)` function is optimized. The initial steps of checking fixed neighbors and propagating constraints are the same as the previous approach and take `O(N)` time.
*   The key improvement is in solving the two-stabber subproblem more efficiently.
*   After getting the list of `m` required intervals for the `-1`s, we analyze their geometric structure.
*   The core idea is that a set of intervals can be stabbed by two points only if the union of these intervals forms at most two connected components.
*   To find the connected components:
    1.  Sort the `m` intervals based on their start points.
    2.  Iterate through the sorted intervals and merge any that overlap or are adjacent. This process yields the connected components of the union.
*   After finding the components:
    1.  If there are 0 or 1 components, all intervals can be stabbed by a single point (e.g., `x=y`), so `d` is achievable. Return `true`.
    2.  If there are more than 2 components, it's impossible to stab them all with two points. Return `false`.
    3.  If there are exactly 2 components, say `[L1, R1]` and `[L2, R2]` (with `R1 < L2`), we must pick one stabbing point from each. This is possible if the distance between them is at most `d`. We check if `L2 - R1 <= d`. If it is, return `true`; otherwise, `false`.
*   This check, dominated by sorting, takes `O(m log m)` or `O(N log N)` time.