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

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 (n ≥ 2), select an index i (0 ≤ i < n − 1) that partitions the array into two contiguous segments: the left segment consists of elements nums[0] through nums[i], and the right segment consists of elements nums[i+1] through nums[n−1]. For each possible partition, compute the absolute difference between the maximum value in the left segment and the minimum value in the right segment. Your task is to determine the largest such difference over all valid partitions and output that value.

Input format:

- The first line contains a single integer n, the number of elements in the array.

- The second line contains n space‑separated integers representing the array nums.

Output format:

- Output a single integer: the maximum absolute difference described above.

DSA Pattern Breakdown

"Max Absolute Difference of Partition Extremes"

medium

WHY DOES IT MATTER?

Prefix/suffix preprocessing is a classic linear‑time pattern for problems that require repeated range queries on static arrays. It transforms a quadratic brute‑force into a single pass, making the algorithm scalable to millions of elements, which is essential in production systems that process large datasets.

OPTIMIZATION CHALLENGE

The key insight is that the maximum of the left segment and the minimum of the right segment can be precomputed independently of each other. Once you have these two arrays, the absolute difference for any partition is a constant‑time lookup, eliminating nested loops.

REAL-WORLD CONNECTION

Think of a streaming analytics pipeline where you need to compute the maximum sales up to each day and the minimum sales after each day to identify the largest swing. Precomputing the running maximum and the future minimum allows the pipeline to emit the swing metric in real time without re‑scanning the data.

When explaining this in an interview, emphasize that the algorithm is essentially two linear scans: one forward to build prefix maxima, one backward to build suffix minima. Highlight that the space can be reduced to O(1) if you compute the suffix minima on the fly during the final pass, but the O(n) auxiliary arrays keep the code clean and avoid subtle bugs.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem reduces to computing, for every partition index i, the maximum value in the left subarray nums[0..i] and the minimum value in the right subarray nums[i+1..n-1]. A naive double‑loop would recompute these extrema for each i, leading to O(n^2) time and unacceptable for large n. The optimal solution precomputes two auxiliary arrays: a prefix maximum array where prefixMax[i] = max(nums[0..i]) and a suffix minimum array where suffixMin[i] = min(nums[i..n-1]). With these in place, each partition’s difference can be evaluated in O(1), yielding an overall O(n) time algorithm. Space can be reduced to O(1) by computing the suffix minima on the fly while iterating from the end, but the O(n) auxiliary arrays keep the implementation straightforward and cache‑friendly.

Interview Questions on This Problem

Q1How would you modify the algorithm if the array could contain duplicate values and you needed the maximum difference between the maximum of the left segment and the minimum of the right segment, but only when the left maximum is strictly greater than the right minimum?

You would still compute prefixMax and suffixMin as before. After computing the difference, you would check the condition prefixMax[i] > suffixMin[i+1] before considering it for the maximum. If the condition fails, you skip that partition. This ensures you only consider partitions where the left maximum strictly exceeds the right minimum.

Q2A fintech company asks: can you solve this problem in O(n) time and O(1) additional space? What trade‑offs would you make?

Yes. Compute prefixMax on the fly while iterating from left to right, storing the current maximum. Simultaneously, compute suffixMin in a second pass from right to left, storing the current minimum. Then perform a single forward pass again, combining the stored prefix maximum and the precomputed suffix minimum array (or recompute suffix minima on the fly if you store them in a stack). The trade‑off is that you need two passes instead of one, but you avoid the extra O(n) array for prefixMax if you recompute it during the final pass.

Q3During a coding interview, a candidate suggests using a segment tree to answer each partition query. Why is this approach overkill?

A segment tree would allow range maximum and minimum queries in O(log n) time, but building the tree itself takes O(n) time and space, and you would still need to query for each of the n-1 partitions, resulting in O(n log n) time. The simple prefix/suffix arrays achieve the same goal in O(n) time and O(n) space, which is asymptotically better and easier to implement.

Examples

Example 1

Input

5
1 3 2 5 4

Output

Explanation: All possible splits: - i=0: left max=1, right min=2 → |1−2|=1 - i=1: left max=3, right min=2 → |3−2|=1 - i=2: left max=3, right min=4 → |3−4|=1 - i=3: left max=5, right min=4 → |5−4|=1 The maximum difference is 1.

Example 2

Input

5
10 -5 7 3 8

Output

Explanation: Splits: - i=0: left max=10, right min=-5 → |10−(−5)|=15 - i=1: left max=10, right min=3 → |10−3|=7 - i=2: left max=10, right min=3 → |10−3|=7 - i=3: left max=10, right min=8 → |10−8|=2 Maximum is 15.

Example 3

Input

4
4 4 4 4

Output

Explanation: For any split, left max=4 and right min=4, so |4−4|=0. The maximum difference is 0.

Example 4

Input

5
-2 -3 -1 -5 -4

Output

Explanation: Splits: - i=0: left max=-2, right min=-5 → |-2−(−5)|=3 - i=1: left max=-2, right min=-5 → 3 - i=2: left max=-1, right min=-5 → |-1−(−5)|=4 - i=3: left max=-1, right min=-4 → |-1−(−4)|=3 Maximum difference is 4.

Constraints

1 ≤ nums.length ≤ 10^5
-10^9 ≤ nums[i] ≤ 10^9
n ≥ 2

Optimal Approach & Strategy

Precompute prefix maximums and suffix minimums in two linear passes, then evaluate each partition’s difference in O(1), achieving O(n) time and O(n) space.

Brute Force Approach

For each partition index i, recompute the maximum of nums[0..i] and the minimum of nums[i+1..n-1] by scanning the subarrays, then take the absolute difference. This takes O(n^2) time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

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_diff

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;
}

Asked in Top Tech Interviews

PaytmSalesforce

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.