Minimize the Maximum Adjacent Element Difference

• 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.

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 -1s 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)).

1// The main binary search structure would call this check function.2private boolean checkSlow(int d, int[] nums) {3    int n = nums.length;4    // Steps 1 & 2: Constraint Propagation (O(N))5    // ... (This part is identical to the optimal approach's check function)6    long[][] ranges = new long[n][2];7    // ... initialization and propagation logic ...8 9    // Step 3: Collect intervals for -1s10    List<long[]> requiredIntervals = new ArrayList<>();11    for (int i = 0; i < n; i++) {12        if (nums[i] == -1) {13            if (ranges[i][0] > ranges[i][1]) return false; // Check from propagation14            requiredIntervals.add(ranges[i]);15        }16    }17 18    if (requiredIntervals.isEmpty()) {19        return true;20    }21 22    // O(N^2) check for two-stabber problem23    for (long[] p1 : requiredIntervals) {24        // Candidate 1 for x: left endpoint25        if (canStabWith(p1[0], d, requiredIntervals)) return true;26        // Candidate 2 for x: right endpoint27        if (canStabWith(p1[1], d, requiredIntervals)) return true;28    }29 30    return false;31}32 33private boolean canStabWith(long x, int d, List<long[]> intervals) {34    long[] intersection = {1L, 2_000_000_000L};35    for (long[] p : intervals) {36        if (x < p[0] || x > p[1]) { // If x doesn't stab p37            intersection[0] = Math.max(intersection[0], p[0]);38            intersection[1] = Math.min(intersection[1], p[1]);39        }40    }41 42    if (intersection[0] > intersection[1]) { // No common intersection for y43        // This means all intervals were stabbed by x44        return true; 45    }46 47    // Check if intersection for y overlaps with [x-d, x+d]48    long y_min = Math.max(intersection[0], x - d);49    long y_max = Math.min(intersection[1], x + d);50 51    return y_min <= y_max;52}

• 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 -1s, 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.

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.

1public int minimizeMaxDifference(int[] nums) {2    int low = 0, high = 1_000_000_000, ans = high;3    while (low <= high) {4        int mid = low + (high - low) / 2;5        if (check(mid, nums)) {6            ans = mid;7            high = mid - 1;8        } else {9            low = mid + 1;10        }11    }12    return ans;13}14 15private boolean check(int d, int[] nums) {16    int n = nums.length;17    for (int i = 0; i < n - 1; i++) {18        if (nums[i] != -1 && nums[i + 1] != -1 && Math.abs(nums[i] - nums[i + 1]) > d) {19            return false;20        }21    }22 23    long[][] ranges = new long[n][2];24    for (int i = 0; i < n; i++) {25        if (nums[i] != -1) {26            ranges[i][0] = ranges[i][1] = nums[i];27        } else {28            ranges[i][0] = 1;29            ranges[i][1] = 2_000_000_000L; // Large enough positive range30        }31    }32 33    for (int i = 1; i < n; i++) {34        ranges[i][0] = Math.max(ranges[i][0], ranges[i - 1][0] - d);35        ranges[i][1] = Math.min(ranges[i][1], ranges[i - 1][1] + d);36        if (ranges[i][0] > ranges[i][1]) return false;37    }38 39    for (int i = n - 2; i >= 0; i--) {40        ranges[i][0] = Math.max(ranges[i][0], ranges[i + 1][0] - d);41        ranges[i][1] = Math.min(ranges[i][1], ranges[i + 1][1] + d);42        if (ranges[i][0] > ranges[i][1]) return false;43    }44 45    List<long[]> requiredIntervals = new ArrayList<>();46    for (int i = 0; i < n; i++) {47        if (nums[i] == -1) {48            requiredIntervals.add(ranges[i]);49        }50    }51 52    if (requiredIntervals.isEmpty()) return true;53 54    requiredIntervals.sort(Comparator.comparingLong(a -> a[0]));55 56    List<long[]> components = new ArrayList<>();57    if (!requiredIntervals.isEmpty()) {58        components.add(requiredIntervals.get(0).clone());59        for (int i = 1; i < requiredIntervals.size(); i++) {60            long[] current = requiredIntervals.get(i);61            long[] lastComp = components.get(components.size() - 1);62            if (current[0] <= lastComp[1]) { // Merge overlapping intervals63                lastComp[1] = Math.max(lastComp[1], current[1]);64            } else {65                components.add(current.clone());66            }67        }68    }69 70    if (components.size() > 2) return false;71    if (components.size() <= 1) return true;72    73    return components.get(1)[0] - components.get(0)[1] <= d;74}