mediumArraysPattern: Basic Traversal
Max Absolute Difference of Partition Extremes Solution
Problem Statement
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: Score(i) = |max(nums[0...i]) - min(nums[i+1...n-1])|. Return the maximum possible value of Score(i) among all valid partitions.
Examples
Example 1:
Input:nums = [3, 8, 2, 9, 4]
Output:6
Explanation: The optimal split is at index i = 1, partitioning the array into [3, 8] and [2, 9, 4]. The maximum of the left partition is 8 and the minimum of the right partition is 2, yielding a score of |8 - 2| = 6.
Example 2:
Input:nums = [10, 3, 5, 1]
Output:9
Explanation: Splitting the array at any valid index always results in 10 being in the left partition and 1 being in the right partition. The maximum absolute difference is therefore |10 - 1| = 9.
Constraints
- 2 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Time: O(n) Space: O(n)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from typing import List
class Solution:
def max_absolute_difference(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
right_min = [0] * n
right_min[-1] = nums[-1]
for i in range(n - 2, -1, -1):
right_min[i] = nums[i] if nums[i] < right_min[i + 1] else right_min[i + 1]
max_diff = 0
left_max = nums[0]
for i in range(n - 1):
if nums[i] > left_max:
left_max = nums[i]
diff = abs(left_max - right_min[i + 1])
if diff > max_diff:
max_diff = diff
return max_diff