LeetCode 3357 - Minimize the Maximum Adjacent Element Difference

LeetCode Problem 3357

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Greedy

Solution

Problem Understanding

The problem gives us an integer array nums, where some positions contain -1. These -1 values represent missing elements that must be replaced.

The key restriction is that we are allowed to choose exactly two positive integers, x and y, one time globally for the entire array. Every missing value must then be replaced by either x or y.

After all replacements are made, we look at every adjacent pair in the array and compute their absolute differences:

$$|nums[i] - nums[i+1]|$$

Our goal is to minimize the maximum adjacent difference across the entire array.

This is a minimax optimization problem. We are not minimizing the sum of differences or the average difference. Instead, we want the worst adjacent gap to be as small as possible.

The array length can be as large as $10^5$, so any solution worse than roughly $O(n \log n)$ will likely time out. Since values can be up to $10^9$, we cannot brute force candidate values for x and y.

Several important observations immediately stand out:

• Adjacent pairs that already contain two known values are fixed forever. Their differences cannot change.
• Only pairs involving at least one -1 can be influenced.
• Consecutive runs of -1 values are especially important because we may choose different replacements inside the run.
• If the entire array consists of -1, we can replace everything with the same value, giving answer 0.
• Since we only have two global replacement values, we cannot independently optimize every missing position.

Some edge cases that can easily cause bugs are:

• All elements are -1
• No elements are -1
• A single missing element between two large numbers
• Long stretches of -1
• Missing values at the beginning or end of the array
• Alternating known and missing values

The challenge is discovering whether a target maximum difference is feasible, then finding the minimum feasible value.

Approaches

Brute Force Approach

A brute force strategy would attempt all possible values for x and y, replace the missing positions in every possible way, and compute the resulting maximum adjacent difference.

This is obviously infeasible.

Even if we restricted x and y to only values appearing near missing positions, there could still be up to $10^5$ distinct candidates. Trying all pairs would already require $O(n^2)$ combinations, and each combination might require another traversal of the array.

Additionally, for every pair (x, y), each missing position can independently choose either value, leading to exponential possibilities.

The brute force approach is correct because it explores all valid assignments, but it is computationally impossible for the given constraints.

Key Insight

The crucial observation is that the answer can be binary searched.

Suppose we guess a maximum allowed adjacent difference D.

The question becomes:

Is it possible to choose two values x and y so that every adjacent difference is at most D?

This transforms the optimization problem into a feasibility problem.

To check feasibility:

• Fixed adjacent pairs must already satisfy the limit.
• Every missing position imposes interval constraints on what values it may take.
• Since every missing value can only become x or y, we must determine whether two global numbers can cover all constraints.

The important reduction is:

• Every missing position that touches a known value constrains replacements into an interval.
• We need to determine whether all intervals can be covered using at most two points (x and y) such that every interval contains at least one chosen point.

This becomes a classic interval covering problem.

Because feasibility is monotonic:

• If D works, then any larger value also works.
• If D fails, any smaller value also fails.

That makes binary search applicable.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(n)	Tries all replacement possibilities
Optimal	O(n log 10^9)	O(n)	Binary search with interval feasibility check

Algorithm Walkthrough

Step 1: Compute fixed adjacent differences

First, scan all adjacent pairs where both values are known.

If:

$$nums[i] \neq -1 \quad \text{and} \quad nums[i+1] \neq -1$$

then their difference is fixed forever.

The final answer can never be smaller than the maximum of these fixed differences.

We store:

base_diff = maximum fixed adjacent difference

This immediately gives a lower bound for binary search.

Step 2: Binary search the answer

We binary search the minimum feasible maximum difference D.

The search range is:

• Low = base_diff
• High = $10^9$

For each midpoint D, we run a feasibility check.

Step 3: Build interval constraints

Suppose a missing position is adjacent to a known value v.

To keep the adjacent difference within D, the replacement must satisfy:

$$|replacement - v| \le D$$

This means the replacement must lie in:

$$[v-D, v+D]$$

For every missing position, intersect all such constraints from neighboring known values.

This produces an allowed interval for that missing position.

Example:

nums = [5, -1, 12]
D = 4

The missing position must satisfy:

$$[1,9] \cap [8,16] = [8,9]$$

So its replacement must be either 8 or 9.

Step 4: Reduce to interval covering

Each constrained missing position now has an interval.

We need to determine whether there exist at most two numbers x and y such that every interval contains at least one of them.

This is the central insight.

Step 5: Greedy covering with two points

Sort intervals by right endpoint.

Choose the right endpoint of the first uncovered interval as the first point.

Continue scanning:

• If an interval already contains the chosen point, it is covered.
• Otherwise, choose another point at its right endpoint.

If more than two points are required, feasibility fails.

Otherwise, feasibility succeeds.

Step 6: Return the minimum feasible value

Binary search continues until the smallest feasible D is found.

That value is the answer.

Why it works

Each missing position only cares whether its chosen replacement lies inside its feasible interval. Since every replacement must be either x or y, the problem becomes selecting at most two global points that hit every interval.

The greedy interval stabbing algorithm is optimal for minimizing the number of chosen points. Therefore, if the greedy method needs more than two points, no valid pair (x, y) exists for that D.

Because feasibility is monotonic, binary search correctly finds the minimum feasible maximum difference.

Python Solution

from typing import List

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)

        base_diff = 0

        for i in range(n - 1):
            if nums[i] != -1 and nums[i + 1] != -1:
                base_diff = max(base_diff, abs(nums[i] - nums[i + 1]))

        def feasible(limit: int) -> bool:
            intervals = []

            for i in range(n):
                if nums[i] != -1:
                    continue

                left = -10**18
                right = 10**18

                if i > 0 and nums[i - 1] != -1:
                    v = nums[i - 1]
                    left = max(left, v - limit)
                    right = min(right, v + limit)

                if i + 1 < n and nums[i + 1] != -1:
                    v = nums[i + 1]
                    left = max(left, v - limit)
                    right = min(right, v + limit)

                if left > right:
                    return False

                if left != -10**18:
                    intervals.append((left, right))

            if not intervals:
                return True

            intervals.sort(key=lambda x: x[1])

            used_points = 0
            current_point = -10**18

            for left, right in intervals:
                if left <= current_point <= right:
                    continue

                used_points += 1
                current_point = right

                if used_points > 2:
                    return False

            return True

        low = base_diff
        high = 10**9

        while low < high:
            mid = (low + high) // 2

            if feasible(mid):
                high = mid
            else:
                low = mid + 1

        return low

The implementation begins by computing base_diff, which represents adjacent differences that cannot be modified. This establishes the minimum possible answer.

The feasible() helper determines whether a candidate maximum difference can be achieved.

For every -1 position, the code builds a feasible interval based on neighboring known values. If both neighbors exist, the intervals are intersected. If the intersection becomes empty, the candidate limit is impossible.

After building all intervals, the algorithm solves the interval stabbing problem greedily. Intervals are sorted by right endpoint, and the algorithm repeatedly chooses the smallest possible covering point.

If more than two points are required, the candidate limit fails.

Finally, binary search repeatedly calls feasible() until the minimum valid limit is found.

Go Solution

package main

import (
	"math"
	"sort"
)

func minDifference(nums []int) int {
	n := len(nums)

	baseDiff := 0

	for i := 0; i < n-1; i++ {
		if nums[i] != -1 && nums[i+1] != -1 {
			diff := abs(nums[i] - nums[i+1])
			if diff > baseDiff {
				baseDiff = diff
			}
		}
	}

	feasible := func(limit int) bool {
		type Interval struct {
			left  int
			right int
		}

		intervals := []Interval{}

		for i := 0; i < n; i++ {
			if nums[i] != -1 {
				continue
			}

			left := math.MinInt64
			right := math.MaxInt64

			if i > 0 && nums[i-1] != -1 {
				v := nums[i-1]
				left = max(left, v-limit)
				right = min(right, v+limit)
			}

			if i+1 < n && nums[i+1] != -1 {
				v := nums[i+1]
				left = max(left, v-limit)
				right = min(right, v+limit)
			}

			if left > right {
				return false
			}

			if left != math.MinInt64 {
				intervals = append(intervals, Interval{left, right})
			}
		}

		if len(intervals) == 0 {
			return true
		}

		sort.Slice(intervals, func(i, j int) bool {
			return intervals[i].right < intervals[j].right
		})

		usedPoints := 0
		currentPoint := math.MinInt64

		for _, interval := range intervals {
			if interval.left <= currentPoint && currentPoint <= interval.right {
				continue
			}

			usedPoints++
			currentPoint = interval.right

			if usedPoints > 2 {
				return false
			}
		}

		return true
	}

	low := baseDiff
	high := int(1e9)

	for low < high {
		mid := (low + high) / 2

		if feasible(mid) {
			high = mid
		} else {
			low = mid + 1
		}
	}

	return low
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

The Go implementation follows the exact same logic as the Python solution.

A small difference is that Go does not have tuples, so an Interval struct is used. Sorting is handled with sort.Slice.

Go integer arithmetic is safe here because all values stay within 32 bit signed range, but math.MinInt64 and math.MaxInt64 are used as sentinel bounds for clarity.

Worked Examples

Example 1

Input:

nums = [1, 2, -1, 10, 8]

First compute fixed adjacent differences:

Pair	Difference
1,2	1
10,8	2

So:

base_diff = 2

Now binary search.

Suppose we test:

D = 4

For the missing position:

Adjacent to 2:

$$[2-4, 2+4] = [-2,6]$$

Adjacent to 10:

$$[10-4, 10+4] = [6,14]$$

Intersection:

$$[6,6]$$

Intervals:

Missing Index	Interval
2	[6,6]

One point is enough, choose:

x = 6

Maximum adjacent difference becomes:

Pair	Difference
1,2	1
2,6	4
6,10	4
10,8	2

Answer:

4

Example 2

Input:

nums = [-1,-1,-1]

There are no fixed adjacent pairs.

base_diff = 0

No constrained intervals exist because no missing position touches a known value.

Therefore any single value works.

Choose:

x = y = 4

All adjacent differences become 0.

Answer:

0

Example 3

Input:

nums = [-1,10,-1,8]

Fixed adjacent differences:

None.

base_diff = 0

Try:

D = 1

Intervals:

For index 0:

$$[9,11]$$

For index 2:

Adjacent to 10:

$$[9,11]$$

Adjacent to 8:

$$[7,9]$$

Intersection:

$$[9,9]$$

Intervals:

Index	Interval
0	[9,11]
2	[9,9]

One point 9 covers both intervals.

Possible assignment:

[11,10,9,8]

Maximum adjacent difference:

1

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log 10^9)	Binary search with linear feasibility checks
Space	O(n)	Stores interval constraints

The feasibility check scans the array once and sorts at most n intervals. Since the binary search range is bounded by $10^9$, it performs roughly 31 iterations.

Therefore the total complexity is:

$$O(31 \cdot n \log n)$$

which simplifies to:

$$O(n \log n)$$

for practical purposes.

Test Cases

sol = Solution()

assert sol.minDifference([1,2,-1,10,8]) == 4
# Standard mixed case

assert sol.minDifference([-1,-1,-1]) == 0
# All elements missing

assert sol.minDifference([-1,10,-1,8]) == 1
# Missing values between close numbers

assert sol.minDifference([5,5,5,5]) == 0
# No missing values, already equal

assert sol.minDifference([1,-1,100]) == 50
# Single missing value between far apart numbers

assert sol.minDifference([-1,1]) == 0
# Missing value at beginning

assert sol.minDifference([1,-1]) == 0
# Missing value at end

assert sol.minDifference([1,-1,-1,10]) == 3
# Consecutive missing values

assert sol.minDifference([1,100,-1,-1,1]) == 99
# Large unavoidable fixed difference

assert sol.minDifference([10,-1,20,-1,30]) == 10
# Alternating known and missing values

assert sol.minDifference([-1,50,-1,-1,60,-1]) == 5
# Multiple constrained regions

assert sol.minDifference([7,7,-1,7,7]) == 0
# Missing value surrounded by equal numbers

Test Summary

Test	Why
[1,2,-1,10,8]	Basic example with one missing value
[-1,-1,-1]	Entire array missing
[-1,10,-1,8]	Two missing positions with tight constraints
[5,5,5,5]	No replacements needed
[1,-1,100]	Single gap between distant values
[-1,1]	Missing value at start
[1,-1]	Missing value at end
[1,-1,-1,10]	Consecutive missing block
[1,100,-1,-1,1]	Existing fixed difference dominates
[10,-1,20,-1,30]	Alternating structure
[-1,50,-1,-1,60,-1]	Multiple interval interactions
[7,7,-1,7,7]	Zero-difference replacement

Edge Cases

One important edge case is when the entire array consists of -1. In this situation there are no constraints at all, because no missing position touches a known value. A naive implementation may accidentally fail interval construction or attempt invalid comparisons. The implementation handles this naturally because no intervals are generated, and the feasibility check immediately returns True for D = 0.

Another critical case is when a missing value lies between two very distant known values, such as [1, -1, 100]. The replacement must satisfy constraints from both sides simultaneously. Incorrect implementations may greedily match only one neighbor and ignore the other. The interval intersection logic correctly enforces both conditions simultaneously.

A third tricky case involves long runs of consecutive missing values. Since every position can independently choose either x or y, the optimal arrangement may alternate between them inside the run. The algorithm avoids explicitly constructing replacements and instead focuses on interval coverage, which correctly captures all possibilities without exponential branching.

A fourth subtle case occurs when the array already contains a large fixed adjacent difference between known values. Since these values cannot change, the answer can never be smaller than that difference. The implementation computes base_diff first and uses it as the lower bound for binary search, guaranteeing correctness.