Minimize the Maximum Adjacent Element Difference

1class Solution {2  public int minDifference(int[] nums) {3    int maxPositiveGap = 0;4    int mn = 1_000_000_000;5    int mx = 0;6 7    for (int i = 1; i < nums.length; ++i) {8      if ((nums[i - 1] == -1) != (nums[i] == -1)) {9        final int positive = Math.max(nums[i - 1], nums[i]);10        mn = Math.min(mn, positive);11        mx = Math.max(mx, positive);12      } else {13        maxPositiveGap = Math.max(maxPositiveGap, Math.abs(nums[i - 1] - nums[i]));14      }15    }16 17    int l = maxPositiveGap;18    int r = (mx - mn + 1) / 2;19 20    while (l < r) {21      final int m = (l + r) / 2;22      if (check(nums, m, mn + m, mx - m))23        r = m;24      else25        l = m + 1;26    }27 28    return l;29  }30 31  // Returns true if it's possible have `m` as maximum absolute difference32  // between adjacent numbers, where -1s are replaced with `x` or `y`.33  private boolean check(int[] nums, int m, int x, int y) {34    int gapLength = 0;35    int prev = 0;36 37    for (final int num : nums) {38      if (num == -1) {39        ++gapLength;40        continue;41      }42      if (prev > 0 && gapLength > 0) {43        if (gapLength == 1 && !checkSingleGap(prev, num, m, x, y))44          return false;45        if (gapLength > 1 && !checkMultipleGaps(prev, num, m, x, y))46          return false;47      }48      prev = num;49      gapLength = 0;50    }51 52    // Check leading gaps53    if (nums[0] == -1) {54      final int num = findFirstNumber(nums, 0, 1);55      if (num != -1 && !checkBoundaryGaps(num, m, x, y))56        return false;57    }58 59    // Check trailing gaps60    if (nums[nums.length - 1] == -1) {61      final int num = findFirstNumber(nums, nums.length - 1, -1);62      if (num != -1 && !checkBoundaryGaps(num, m, x, y))63        return false;64    }65 66    return true;67  }68 69  // Returns true if it's possible to have at most `m` as the minimized maximum70  // difference for a sequence with a single -1 between two numbers.71  // e.g. [a, -1, b] can be filled with either x or y.72  private boolean checkSingleGap(int a, int b, int m, int x, int y) {73    final int gapWithX = Math.max(Math.abs(a - x), Math.abs(b - x)); // [a, x, b]74    final int gapWithY = Math.max(Math.abs(a - y), Math.abs(b - y)); // [a, y, b]75    return Math.min(gapWithX, gapWithY) <= m;76  }77 78  // Returns true if it's possible to have at most `m` as the minimized maximum79  // difference for a sequence with multiple -1s between two numbers.80  // e.g. [a, -1, -1, ..., -1, b] can be filled with x and y.81  private boolean checkMultipleGaps(int a, int b, int m, int x, int y) {82    final int ax = Math.abs(a - x);83    final int ay = Math.abs(a - y);84    final int bx = Math.abs(b - x);85    final int by = Math.abs(b - y);86    final int xy = Math.abs(x - y);87    final int gapAllX = Math.max(ax, bx);               // [a, x, x, ..., x, b]88    final int gapAllY = Math.max(ay, by);               // [a, y, y, ..., y, b]89    final int gapXToY = Math.max(Math.max(ax, xy), by); // [a, x, ..., y, b]90    final int gapYToX = Math.max(Math.max(ay, xy), bx); // [a, y, ..., x, b]91    return Math.min(Math.min(gapAllX, gapAllY), Math.min(gapXToY, gapYToX)) <= m;92  }93 94  // Returns true if it's possible to have at most `m` as the minimized maximum95  // difference for a boundary sequence starting or ending with -1s.96  // e.g. [a, -1, -1, ...] or [..., -1, -1, a].97  private boolean checkBoundaryGaps(int a, int m, int x, int y) {98    final int gapAllX = Math.abs(a - x); // [x, x, ..., x, a]99    final int gapAllY = Math.abs(a - y); // [y, y, ..., y, a]100    return Math.min(gapAllX, gapAllY) <= m;101  }102 103  // Returns the first positive number starting from the given index or -1104  // if not found.105  private int findFirstNumber(int[] nums, int start, int step) {106    int i = start;107    while (i >= 0 && i < nums.length && nums[i] == -1)108      i += step;109    return i >= 0 && i < nums.length ? nums[i] : -1;110  }111}112