Minimize the Maximum Adjacent Element Difference

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