3357. Minimize the Maximum Adjacent Element Difference LeetCode Solution
In this guide, you will get 3357. Minimize the Maximum Adjacent Element Difference LeetCode Solution with the best time and space complexity. The solution to Minimize the Maximum Adjacent Element Difference problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimize the Maximum Adjacent Element Difference
You are given an array of integers nums. Some values in nums are missing and are denoted by -1.
You can choose a pair of positive integers (x, y) exactly once and replace each missing element with either x or y.
You need to minimize the maximum absolute difference between adjacent elements of nums after replacements.
Return the minimum possible difference.
Example 1:
Input: nums = [1,2,-1,10,8]
Output: 4
Explanation:
By choosing the pair as (6, 7), nums can be changed to [1, 2, 6, 10, 8].
The absolute differences between adjacent elements are:
Input: nums = [-1,-1,-1]
Output: 0
Explanation:
By choosing the pair as (4, 4), nums can be changed to [4, 4, 4].
Example 3:
Input: nums = [-1,10,-1,8]
Output: 1
Explanation:
By choosing the pair as (11, 9), nums can be changed to [11, 10, 9, 8].
Constraints:
2 <= nums.length <= 105
nums[i] is either -1 or in the range [1, 109].
Complexity Analysis
Time Complexity: O(n\log\max(\texttt{nums}))
Space Complexity: O(n)
3357. Minimize the Maximum Adjacent Element Difference LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
3357. Minimize the Maximum Adjacent Element Difference LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
3357. Minimize the Maximum Adjacent Element Difference LeetCode Solution in Python
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 # code by PROGIEZ
