Minimize the Maximum Adjacent Element Difference

1class Solution:2  def minDifference(self, nums: list[int]) -> int:3    maxPositiveGap = 04    mn = 1_000_000_0005    mx = 06 7    for a, b in itertools.pairwise(nums):8      if (a == -1) != (b == -1):9        positive = max(a, b)10        mn = min(mn, positive)11        mx = max(mx, positive)12      else:13        maxPositiveGap = max(maxPositiveGap, abs(a - b))14 15    l = maxPositiveGap16    r = (mx - mn + 1) // 217    return bisect.bisect_left(18        range(l, r), True,19        key=lambda m: self._check(nums, m, mn + m, mx - m)) + l20 21  def _check(self, nums: list[int], m: int, x: int, y: int) -> bool:22    """23    Returns True if it's possible have `m` as maximum absolute difference24    between adjacent numbers, where -1s are replaced with `x` or `y`.25    """26    gapLength = 027    prev = 028 29    for num in nums:30      if num == -1:31        gapLength += 132        continue33      if prev > 0 and gapLength > 0:34        if gapLength == 1 and not self._checkSingleGap(prev, num, m, x, y):35          return False36        if gapLength > 1 and not self._checkMultipleGaps(prev, num, m, x, y):37          return False38      prev = num39      gapLength = 040 41    # Check leading gaps42    if nums[0] == -1:43      num = next((num for num in nums if num != -1), -1)44      if num != -1 and not self._checkBoundaryGaps(num, m, x, y):45        return False46 47    # Check trailing gaps48    if nums[-1] == -1:49      num = next((num for num in reversed(nums) if num != -1), -1)50      if num != -1 and not self._checkBoundaryGaps(num, m, x, y):51        return False52 53    return True54 55  def _checkSingleGap(self, a: int, b: int, m: int, x: int, y: int) -> bool:56    """57    Returns true if it's possible to have at most `m` as the minimized maximum58    difference for a sequence with a single -1 between two numbers.59    e.g. [a, -1, b] can be filled with either x or y.60    """61    gapWithX = max(abs(a - x), abs(b - x))  # [a, x, b]62    gapWithY = max(abs(a - y), abs(b - y))  # [a, y, b]63    return min(gapWithX, gapWithY) <= m64 65  def _checkMultipleGaps(self, a: int, b: int, m: int, x: int, y: int) -> bool:66    """67    Returns true if it's possible to have at most `m` as the minimized maximum68    difference for a sequence with multiple -1s between two numbers.69    e.g. [a, -1, -1, ..., -1, b] can be filled with x and y.70    """71    ax = abs(a - x)72    ay = abs(a - y)73    bx = abs(b - x)74    by = abs(b - y)75    xy = abs(x - y)76    gapAllX = max(ax, bx)  # [a, x, x, ..., x, b]77    gapAllY = max(ay, by)  # [a, y, y, ..., y, b]78    gapXToY = max(ax, xy, by)  # [a, x, ..., y, b]79    gapYToX = max(ay, xy, bx)  # [a, y, ..., x, b]80    return min(gapAllX, gapAllY, gapXToY, gapYToX) <= m81 82  def _checkBoundaryGaps(self, a: int, m: int, x: int, y: int) -> bool:83    """84    Returns true if it's possible to have at most `m` as the minimized maximum85    difference for a boundary sequence starting or ending with -1s.86    e.g. [a, -1, -1, ...] or [..., -1, -1, a].87    """88    gapAllX = abs(a - x)  # [x, x, ..., x, a]89    gapAllY = abs(a - y)  # [y, y, ..., y, a]90    return min(gapAllX, gapAllY) <= m91