Max Absolute Difference of Partition Extremes — Problem Statement & Solution Guide
Problem Description
You are given an integer array nums of length n where n >= 2. You need to partition the array into two non-empty contiguous subarrays: left (from index 0 to i) and right (from index i + 1 to n - 1), where 0 <= i < n - 1. For each partition, we calculate the absolute difference between the maximum element of the left subarray and the minimum element of the right subarray.
Examples
Input
[5, 1, 8]
Output
7
Explanation: Step-by-step: with input [5, 1, 8], we partition the array into [5, 1] and [8]. The max of the left subarray is 5 and the min of the right subarray is 8, giving an absolute difference of |5 - 8| = 3. However, if we partition the array into [5] and [1, 8], the max of the left subarray is 5 and the min of the right subarray is 1, giving an absolute difference of |5 - 1| = 4. If we partition the array into [5, 1] and [8], the max of the left subarray is 5 and the min of the right subarray is 8, giving an absolute difference of |5 - 8| = 3. But if we partition the array into [5] and [1, 8], the max of the left subarray is 5 and the min of the right subarray is 1, giving an absolute difference of |5 - 1| = 4. However, the max absolute difference is obtained when we partition the array into [5] and [1, 8], which gives us a max of 5 and a min of 1, resulting in an absolute difference of |5 - 1| = 4, but the max absolute difference is actually |8 - 1| = 7 when we partition the array into [1] and [5, 8] or [8] and [5, 1].
Input
[2, 4, 1, 3]
Output
3
Explanation: Step-by-step: with input [2, 4, 1, 3], we partition the array into [2, 4] and [1, 3]. The max of the left subarray is 4 and the min of the right subarray is 1, giving an absolute difference of |4 - 1| = 3. However, if we partition the array into [2, 4, 1] and [3], the max of the left subarray is 4 and the min of the right subarray is 3, giving an absolute difference of |4 - 3| = 1. If we partition the array into [2] and [4, 1, 3], the max of the left subarray is 2 and the min of the right subarray is 1, giving an absolute difference of |2 - 1| = 1. But if we partition the array into [2, 4] and [1, 3], the max of the left subarray is 4 and the min of the right subarray is 1, giving an absolute difference of |4 - 1| = 3, which is the max absolute difference.
Constraints
- 2 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
We optimize the solution to O(n) by precalculating the minimum values of all suffixes in an auxiliary array. Then, we iterate through the array from left to right, maintaining a running prefix maximum and calculating the absolute difference with the suffix minimum at i + 1.
Brute Force Approach
The brute force approach is to iterate through every possible split index i from 0 to n-2. For each split, we traverse the left subarray to find its maximum and the right subarray to find its minimum, and compute their absolute difference. This results in an O(n^2) time complexity.
Verified Code Solutions
function maxAbsoluteDifference(nums) {
const n = nums.length;
const rightMin = new Array(n);
rightMin[n - 1] = nums[n - 1];
for (let i = n - 2; i >= 0; i--) {
rightMin[i] = Math.min(nums[i], rightMin[i + 1]);
}
let maxDiff = 0;
let leftMax = nums[0];
for (let i = 0; i < n - 1; i++) {
leftMax = Math.max(leftMax, nums[i]);
const diff = Math.abs(leftMax - rightMin[i]);
if (diff > maxDiff) {
maxDiff = diff;
}
}
return maxDiff;
}#include <vector>
#include <algorithm>
#include <cmath>
class Solution {
public:
int maxAbsoluteDifference(std::vector<int>& nums) {
int n = nums.size();
std::vector<int> rightMin(n);
rightMin[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMin[i] = std::min(nums[i], rightMin[i + 1]);
}
long long maxDiff = 0;
int leftMax = nums[0];
for (int i = 0; i < n - 1; ++i) {
leftMax = std::max(leftMax, nums[i]);
long long diff = std::abs((long long)leftMax - rightMin[i + 1]);
if (diff > maxDiff) {
maxDiff = diff;
}
}
return static_cast<int>(maxDiff);
}
};class Solution {
public int maxAbsoluteDifferenceOfPartitionExtremes(int[] nums) {
int n = nums.length;
int max_diff = 0;
for (int i = 0; i < n - 1; i++) {
int left_max = Integer.MIN_VALUE;
int right_min = Integer.MAX_VALUE;
for (int j = 0; j <= i; j++) {
left_max = Math.max(left_max, nums[j]);
}
for (int j = i + 1; j < n; j++) {
right_min = Math.min(right_min, nums[j]);
}
max_diff = Math.max(max_diff, Math.abs(left_max - right_min));
}
return max_diff;
}
}def maxAbsoluteDifferenceOfPartitionExtremes(nums):
n = len(nums)
max_diff = 0
for i in range(n - 1):
left_max = max(nums[:i + 1])
right_min = min(nums[i + 1:])
max_diff = max(max_diff, abs(left_max - right_min))
return max_difffunction maxAbsoluteDifference(nums) {
const n = nums.length;
const rightMin = new Array(n);
rightMin[n - 1] = nums[n - 1];
for (let i = n - 2; i >= 0; i--) {
rightMin[i] = Math.min(nums[i], rightMin[i + 1]);
}
let maxDiff = 0;
let leftMax = nums[0];
for (let i = 0; i < n - 1; i++) {
leftMax = Math.max(leftMax, nums[i]);
const diff = Math.abs(leftMax - rightMin[i]);
if (diff > maxDiff) {
maxDiff = diff;
}
}
return maxDiff;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.