Skip to content

3357. Minimize the Maximum Adjacent Element Difference

  • Time: $O(n\log\max(\texttt{nums}))$
  • Space: $O(n)$
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
class Solution {
 public:
  int minDifference(vector<int>& nums) {
    int maxPositiveGap = 0;
    int mn = 1'000'000'000;
    int mx = 0;

    for (int i = 1; i < nums.size(); ++i)
      if ((nums[i - 1] == -1) != (nums[i] == -1)) {
        const int positive = max(nums[i - 1], nums[i]);
        mn = min(mn, positive);
        mx = max(mx, positive);
      } else {
        maxPositiveGap = max(maxPositiveGap, abs(nums[i - 1] - nums[i]));
      }

    int l = maxPositiveGap;
    int r = (mx - mn + 1) / 2;

    while (l < r) {
      const int m = (l + r) / 2;
      if (check(nums, m, mn + m, mx - m))
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

 private:
  // Returns true if it's possible have `m` as maximum absolute difference
  // between adjacent numbers, where -1s are replaced with `x` or `y`.
  bool check(const vector<int>& nums, int m, int x, int y) {
    int gapLength = 0;
    int prev = 0;

    for (const int num : nums) {
      if (num == -1) {
        ++gapLength;
        continue;
      }
      if (prev > 0 && gapLength > 0) {
        if (gapLength == 1 && !checkSingleGap(prev, num, m, x, y))
          return false;
        if (gapLength > 1 && !checkMultipleGaps(prev, num, m, x, y))
          return false;
      }
      prev = num;
      gapLength = 0;
    }

    // Check leading gaps.
    if (nums[0] == -1) {
      const int num = findFirstNumber(nums, 0, 1);
      if (num != -1 && !checkBoundaryGaps(num, m, x, y))
        return false;
    }

    // Check trailing gaps.
    if (nums.back() == -1) {
      const int num = findFirstNumber(nums, nums.size() - 1, -1);
      if (num != -1 && !checkBoundaryGaps(num, m, x, y))
        return false;
    }

    return true;
  }

  // Returns true if it's possible to have at most `m` as the minimized maximum
  // difference for a sequence with a single -1 between two numbers.
  // e.g. [a, -1, b] can be filled with either x or y.
  bool checkSingleGap(int a, int b, int m, int x, int y) {
    const int gapWithX = max(abs(a - x), abs(b - x));  // [a, x, b]
    const int gapWithY = max(abs(a - y), abs(b - y));  // [a, y, b]
    return min(gapWithX, gapWithY) <= m;
  }

  // Returns true if it's possible to have at most `m` as the minimized maximum
  // difference for a sequence with multiple -1s between two numbers.
  // e.g. [a, -1, -1, ..., -1, b] can be filled with x and y.
  bool checkMultipleGaps(int a, int b, int m, int x, int y) {
    const int ax = abs(a - x);
    const int ay = abs(a - y);
    const int bx = abs(b - x);
    const int by = abs(b - y);
    const int xy = abs(x - y);
    const int gapAllX = max(ax, bx);        // [a, x, x, ..., x, b]
    const int gapAllY = max(ay, by);        // [a, y, y, ..., y, b]
    const int gapXToY = max({ax, xy, by});  // [a, x, ..., y, b]
    const int gapYToX = max({ay, xy, bx});  // [a, y, ..., x, b]
    return min({gapAllX, gapAllY, gapXToY, gapYToX}) <= m;
  }

  // Returns true if it's possible to have at most `m` as the minimized maximum
  // difference for a boundary sequence starting or ending with -1s.
  // e.g. [a, -1, -1, ...] or [..., -1, -1, a].
  bool checkBoundaryGaps(int a, int m, int x, int y) {
    const int gapAllX = abs(a - x);  // [x, x, ..., x, a]
    const int gapAllY = abs(a - y);  // [y, y, ..., y, a]
    return min(gapAllX, gapAllY) <= m;
  }

  // Returns the first positive number starting from the given index or -1
  // if not found.
  int findFirstNumber(const vector<int>& nums, int start, int step) {
    int i = start;
    while (i >= 0 && i < nums.size() && nums[i] == -1)
      i += step;
    return i >= 0 && i < nums.size() ? nums[i] : -1;
  }
};

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
class Solution {
  public int minDifference(int[] nums) {
    int maxPositiveGap = 0;
    int mn = 1_000_000_000;
    int mx = 0;

    for (int i = 1; i < nums.length; ++i) {
      if ((nums[i - 1] == -1) != (nums[i] == -1)) {
        final int positive = Math.max(nums[i - 1], nums[i]);
        mn = Math.min(mn, positive);
        mx = Math.max(mx, positive);
      } else {
        maxPositiveGap = Math.max(maxPositiveGap, Math.abs(nums[i - 1] - nums[i]));
      }
    }

    int l = maxPositiveGap;
    int r = (mx - mn + 1) / 2;

    while (l < r) {
      final int m = (l + r) / 2;
      if (check(nums, m, mn + m, mx - m))
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

  // Returns true if it's possible have `m` as maximum absolute difference
  // between adjacent numbers, where -1s are replaced with `x` or `y`.
  private boolean check(int[] nums, int m, int x, int y) {
    int gapLength = 0;
    int prev = 0;

    for (final int num : nums) {
      if (num == -1) {
        ++gapLength;
        continue;
      }
      if (prev > 0 && gapLength > 0) {
        if (gapLength == 1 && !checkSingleGap(prev, num, m, x, y))
          return false;
        if (gapLength > 1 && !checkMultipleGaps(prev, num, m, x, y))
          return false;
      }
      prev = num;
      gapLength = 0;
    }

    // Check leading gaps
    if (nums[0] == -1) {
      final int num = findFirstNumber(nums, 0, 1);
      if (num != -1 && !checkBoundaryGaps(num, m, x, y))
        return false;
    }

    // Check trailing gaps
    if (nums[nums.length - 1] == -1) {
      final int num = findFirstNumber(nums, nums.length - 1, -1);
      if (num != -1 && !checkBoundaryGaps(num, m, x, y))
        return false;
    }

    return true;
  }

  // Returns true if it's possible to have at most `m` as the minimized maximum
  // difference for a sequence with a single -1 between two numbers.
  // e.g. [a, -1, b] can be filled with either x or y.
  private boolean checkSingleGap(int a, int b, int m, int x, int y) {
    final int gapWithX = Math.max(Math.abs(a - x), Math.abs(b - x)); // [a, x, b]
    final int gapWithY = Math.max(Math.abs(a - y), Math.abs(b - y)); // [a, y, b]
    return Math.min(gapWithX, gapWithY) <= m;
  }

  // Returns true if it's possible to have at most `m` as the minimized maximum
  // difference for a sequence with multiple -1s between two numbers.
  // e.g. [a, -1, -1, ..., -1, b] can be filled with x and y.
  private boolean checkMultipleGaps(int a, int b, int m, int x, int y) {
    final int ax = Math.abs(a - x);
    final int ay = Math.abs(a - y);
    final int bx = Math.abs(b - x);
    final int by = Math.abs(b - y);
    final int xy = Math.abs(x - y);
    final int gapAllX = Math.max(ax, bx);               // [a, x, x, ..., x, b]
    final int gapAllY = Math.max(ay, by);               // [a, y, y, ..., y, b]
    final int gapXToY = Math.max(Math.max(ax, xy), by); // [a, x, ..., y, b]
    final int gapYToX = Math.max(Math.max(ay, xy), bx); // [a, y, ..., x, b]
    return Math.min(Math.min(gapAllX, gapAllY), Math.min(gapXToY, gapYToX)) <= m;
  }

  // Returns true if it's possible to have at most `m` as the minimized maximum
  // difference for a boundary sequence starting or ending with -1s.
  // e.g. [a, -1, -1, ...] or [..., -1, -1, a].
  private boolean checkBoundaryGaps(int a, int m, int x, int y) {
    final int gapAllX = Math.abs(a - x); // [x, x, ..., x, a]
    final int gapAllY = Math.abs(a - y); // [y, y, ..., y, a]
    return Math.min(gapAllX, gapAllY) <= m;
  }

  // Returns the first positive number starting from the given index or -1
  // if not found.
  private int findFirstNumber(int[] nums, int start, int step) {
    int i = start;
    while (i >= 0 && i < nums.length && nums[i] == -1)
      i += step;
    return i >= 0 && i < nums.length ? nums[i] : -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class Solution:
  def minDifference(self, nums: list[int]) -> int:
    maxPositiveGap = 0
    mn = 1_000_000_000
    mx = 0

    for a, b in itertools.pairwise(nums):
      if (a == -1) != (b == -1):
        positive = max(a, b)
        mn = min(mn, positive)
        mx = max(mx, positive)
      else:
        maxPositiveGap = max(maxPositiveGap, abs(a - b))

    l = maxPositiveGap
    r = (mx - mn + 1) // 2
    return bisect.bisect_left(
        range(l, r), True,
        key=lambda m: self._check(nums, m, mn + m, mx - m)) + l

  def _check(self, nums: list[int], m: int, x: int, y: int) -> bool:
    """
    Returns True if it's possible have `m` as maximum absolute difference
    between adjacent numbers, where -1s are replaced with `x` or `y`.
    """
    gapLength = 0
    prev = 0

    for num in nums:
      if num == -1:
        gapLength += 1
        continue
      if prev > 0 and gapLength > 0:
        if gapLength == 1 and not self._checkSingleGap(prev, num, m, x, y):
          return False
        if gapLength > 1 and not self._checkMultipleGaps(prev, num, m, x, y):
          return False
      prev = num
      gapLength = 0

    # Check leading gaps
    if nums[0] == -1:
      num = next((num for num in nums if num != -1), -1)
      if num != -1 and not self._checkBoundaryGaps(num, m, x, y):
        return False

    # Check trailing gaps
    if nums[-1] == -1:
      num = next((num for num in reversed(nums) if num != -1), -1)
      if num != -1 and not self._checkBoundaryGaps(num, m, x, y):
        return False

    return True

  def _checkSingleGap(self, a: int, b: int, m: int, x: int, y: int) -> bool:
    """
    Returns true if it's possible to have at most `m` as the minimized maximum
    difference for a sequence with a single -1 between two numbers.
    e.g. [a, -1, b] can be filled with either x or y.
    """
    gapWithX = max(abs(a - x), abs(b - x))  # [a, x, b]
    gapWithY = max(abs(a - y), abs(b - y))  # [a, y, b]
    return min(gapWithX, gapWithY) <= m

  def _checkMultipleGaps(self, a: int, b: int, m: int, x: int, y: int) -> bool:
    """
    Returns true if it's possible to have at most `m` as the minimized maximum
    difference for a sequence with multiple -1s between two numbers.
    e.g. [a, -1, -1, ..., -1, b] can be filled with x and y.
    """
    ax = abs(a - x)
    ay = abs(a - y)
    bx = abs(b - x)
    by = abs(b - y)
    xy = abs(x - y)
    gapAllX = max(ax, bx)  # [a, x, x, ..., x, b]
    gapAllY = max(ay, by)  # [a, y, y, ..., y, b]
    gapXToY = max(ax, xy, by)  # [a, x, ..., y, b]
    gapYToX = max(ay, xy, bx)  # [a, y, ..., x, b]
    return min(gapAllX, gapAllY, gapXToY, gapYToX) <= m

  def _checkBoundaryGaps(self, a: int, m: int, x: int, y: int) -> bool:
    """
    Returns true if it's possible to have at most `m` as the minimized maximum
    difference for a boundary sequence starting or ending with -1s.
    e.g. [a, -1, -1, ...] or [..., -1, -1, a].
    """
    gapAllX = abs(a - x)  # [x, x, ..., x, a]
    gapAllY = abs(a - y)  # [y, y, ..., y, a]
    return min(gapAllX, gapAllY) <= m