Review the fundamentals: Arrays guide and time complexities.

Minimum Absolute Difference of Partition Extremes — Problem Statement & Solution Guide

Q: How would you modify this solution if the array was circular, allowing the partition to wrap around?

For a circular array, you would need to consider partitions that cross the index 0 boundary. This typically involves duplicating the array or using a sliding window approach with a deque to maintain max/min over a fixed window size, adjusting the logic to handle the wrap-around indices correctly.

Q: What if the array is extremely large and cannot fit in memory? How would you handle streaming data?

In a streaming context, you cannot precompute the right suffix minimums in a single pass without storing the entire array or using a two-pass approach if the stream is seekable. If the stream is not seekable, you might need to use approximate algorithms or maintain a summary structure, though exact solutions for streaming partitions are complex and often require multiple passes or significant memory for buffering.

Q: Can you extend this to find the partition that minimizes the sum of the absolute differences of all elements in the left and right subarrays?

This changes the problem significantly. You would need to maintain prefix sums and potentially use a different metric. The 'max of left' and 'min of right' logic no longer applies directly. You would likely need to track prefix sums and use a different optimization strategy, possibly involving binary search or dynamic programming depending on the specific cost function.

ArraysMediumBasic Traversal

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Iterating arrays and tracking min/max

TopicArrays

PatternBasic Traversal

TimeO(n)

SpaceO(n)

Problem Description

Given an integer array nums of length n, you need to partition the array into two non-empty contiguous subarrays: a left subarray nums[0...i] and a right subarray nums[i+1...n-1], where 0 <= i < n - 1.

For each possible partition, calculate the absolute difference between the maximum element in the left subarray and the minimum element in the right subarray.

Return the minimum absolute difference obtained among all possible partitions.

DSA Pattern Breakdown

"Minimum Absolute Difference of Partition Extremes"

medium

WHY DOES IT MATTER?

This problem exemplifies the 'Prefix-Suffix' or 'Left-Right' precomputation pattern. It is essential for optimizing problems where a global property depends on local subarray properties, allowing $O(n^2)$ brute force solutions to be reduced to $O(n)$ by leveraging the overlapping substructure of prefixes and suffixes.

OPTIMIZATION CHALLENGE

The key insight is recognizing that the maximum of the left subarray only depends on elements to its left, and the minimum of the right subarray only depends on elements to its right. By precomputing these values in two separate passes (one forward, one backward), you avoid redundant calculations for each partition index.

REAL-WORLD CONNECTION

This pattern is analogous to load balancing in distributed systems, where you might partition a dataset across two servers. You want to minimize the 'imbalance' or 'difference' in load (represented here by max/min extremes) between the two partitions. Precomputing load metrics for prefixes and suffixes allows for rapid evaluation of partition points during dynamic rebalancing.

In an interview, explicitly state that you are using 'prefix maximums' and 'suffix minimums'. This demonstrates a clear understanding of the data structure and the time complexity improvement. Always verify edge cases like $n=2$ where only one partition exists.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem requires finding the minimum absolute difference between the maximum of a left prefix and the minimum of a right suffix across all possible partition points. A naive approach would iterate through each partition index $i$, compute the maximum of $nums[0...i]$ and the minimum of $nums[i+1...n-1]$ from scratch, and track the global minimum. This results in $O(n^2)$ time complexity, which is infeasible for large arrays (e.g., $n = 10^5$). The key insight is that the maximum of the left prefix and the minimum of the right suffix are monotonic properties that can be precomputed in linear time.

Interview Questions on This Problem

Q1How would you modify this solution if the array was circular, allowing the partition to wrap around?

For a circular array, you would need to consider partitions that cross the index 0 boundary. This typically involves duplicating the array or using a sliding window approach with a deque to maintain max/min over a fixed window size, adjusting the logic to handle the wrap-around indices correctly.

Q2What if the array is extremely large and cannot fit in memory? How would you handle streaming data?

In a streaming context, you cannot precompute the right suffix minimums in a single pass without storing the entire array or using a two-pass approach if the stream is seekable. If the stream is not seekable, you might need to use approximate algorithms or maintain a summary structure, though exact solutions for streaming partitions are complex and often require multiple passes or significant memory for buffering.

Q3Can you extend this to find the partition that minimizes the sum of the absolute differences of all elements in the left and right subarrays?

This changes the problem significantly. You would need to maintain prefix sums and potentially use a different metric. The 'max of left' and 'min of right' logic no longer applies directly. You would likely need to track prefix sums and use a different optimization strategy, possibly involving binary search or dynamic programming depending on the specific cost function.

Examples

Example 1

Input

nums = [4, 2, 3, 1, 5]

Output

Explanation: Splitting at index i = 3 gives a left subarray [4, 2, 3, 1] (max = 4) and a right subarray [5] (min = 5). The absolute difference is |4 - 5| = 1, which is the minimum possible.

Example 2

Input

nums = [1, 10, 4, 7, 3]

Output

Explanation: Splitting at index i = 0 gives a left subarray [1] (max = 1) and a right subarray [10, 4, 7, 3] (min = 3). The absolute difference is |1 - 3| = 2, which is the minimum possible.

Constraints

2 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Optimal Approach & Strategy

Precompute an array of prefix maximums and an array of suffix minimums in linear time. Then, iterate through each partition index, using the precomputed values to calculate the difference in constant time, tracking the minimum difference.

Brute Force Approach

Iterate through each possible partition index $i$. For each $i$, scan the left subarray to find its maximum and the right subarray to find its minimum, then compute the absolute difference and update the global minimum.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function minAbsoluteDifferenceOfPartitionExtremes(nums) {
  const n = nums.length;
  const suffixMin = new Array(n);
  suffixMin[n - 1] = nums[n - 1];
  
  for (let i = n - 2; i >= 0; i--) {
    suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);
  }
  
  let minDiff = Infinity;
  let currMax = -Infinity;
  
  for (let i = 0; i < n - 1; i++) {
    currMax = Math.max(currMax, nums[i]);
    const diff = Math.abs(currMax - suffixMin[i + 1]);
    if (diff < minDiff) {
      minDiff = diff;
    }
  }
  
  return minDiff;
}

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <climits>

class Solution {
public:
    int minAbsoluteDifferenceOfPartitionExtremes(std::vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return 0;
        std::vector<int> suffixMin(n);
        suffixMin[n - 1] = nums[n - 1];
        
        for (int i = n - 2; i >= 0; --i) {
            suffixMin[i] = std::min(nums[i], suffixMin[i + 1]);
        }
        
        long long minDiff = -1;
        int currMax = INT_MIN;
        
        for (int i = 0; i < n - 1; ++i) {
            currMax = std::max(currMax, nums[i]);
            long long diff = std::abs((long long)currMax - suffixMin[i + 1]);
            if (minDiff == -1 || diff < minDiff) {
                minDiff = diff;
            }
        }
        
        return (int)minDiff;
    }
};

int main() {
    std::string line;
    while (std::getline(std::cin, line)) {
        if (line.empty()) continue;
        size_t start = line.find('[');
        size_t end = line.find(']');
        if (start != std::string::npos && end != std::string::npos && end > start) {
            std::string array_str = line.substr(start + 1, end - start - 1);
            std::replace(array_str.begin(), array_str.end(), ',', ' ');
            std::stringstream ss(array_str);
            std::vector<int> nums;
            int val;
            while (ss >> val) {
                nums.push_back(val);
            }
            if (!nums.empty()) {
                Solution solver;
                std::cout << solver.minAbsoluteDifferenceOfPartitionExtremes(nums) << std::endl;
            }
        }
    }
    return 0;
}

import java.util.*;

class Solution {
    public int minAbsoluteDifferenceOfPartitionExtremes(int[] nums) {
        int n = nums.length;
        int[] suffixMin = new int[n];
        suffixMin[n - 1] = nums[n - 1];
        
        for (int i = n - 2; i >= 0; i--) {
            suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);
        }
        
        long minDiff = Long.MAX_VALUE;
        long currMax = Long.MIN_VALUE;
        
        for (int i = 0; i < n - 1; i++) {
            currMax = Math.max(currMax, (long) nums[i]);
            long diff = Math.abs(currMax - (long) suffixMin[i + 1]);
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
        
        return (int) minDiff;
    }
}

from typing import List

class Solution:
    def minAbsoluteDifferenceOfPartitionExtremes(self, nums: List[int]) -> int:
        n = len(nums)
        suffix_min = [0] * n
        suffix_min[-1] = nums[-1]
        
        for i in range(n - 2, -1, -1):
            suffix_min[i] = min(nums[i], suffix_min[i + 1])
            
        min_diff = float('inf')
        curr_max = float('-inf')
        
        for i in range(n - 1):
            curr_max = max(curr_max, nums[i])
            diff = abs(curr_max - suffix_min[i + 1])
            if diff < min_diff:
                min_diff = diff
                
        return int(min_diff)

function minAbsoluteDifferenceOfPartitionExtremes(nums) {
  const n = nums.length;
  const suffixMin = new Array(n);
  suffixMin[n - 1] = nums[n - 1];
  
  for (let i = n - 2; i >= 0; i--) {
    suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);
  }
  
  let minDiff = Infinity;
  let currMax = -Infinity;
  
  for (let i = 0; i < n - 1; i++) {
    currMax = Math.max(currMax, nums[i]);
    const diff = Math.abs(currMax - suffixMin[i + 1]);
    if (diff < minDiff) {
      minDiff = diff;
    }
  }
  
  return minDiff;
}

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.