#2740

Medium

LeetCode Problem Workspace

Find the Value of the Partition

Find the minimum partition value by dividing a positive integer array into two subarrays using sorting for efficiency.

Problem Statement

You are given a positive integer array nums. Partition nums into two non-empty subarrays nums1 and nums2 such that the value of the partition, defined as |max(nums1) - min(nums2)|, is minimized.

Return the minimum value of the partition. The array can be reordered through sorting to simplify the partitioning and guarantee that the difference between max(nums1) and min(nums2) is as small as possible.

Examples

Example 1

Input: nums = [1,3,2,4]

Output: 1

We can partition the array nums into nums1 = [1,2] and nums2 = [3,4].

The maximum element of the array nums1 is equal to 2.
The minimum element of the array nums2 is equal to 3. The value of the partition is |2 - 3| = 1. It can be proven that 1 is the minimum value out of all partitions.

Example 2

Input: nums = [100,1,10]

Output: 9

We can partition the array nums into nums1 = [10] and nums2 = [100,1].

The maximum element of the array nums1 is equal to 10.
The minimum element of the array nums2 is equal to 1. The value of the partition is |10 - 1| = 9. It can be proven that 9 is the minimum value out of all partitions.

Constraints

2 <= nums.length <= 105
1 <= nums[i] <= 109

Solution Approach

Sort the Array

Sorting nums places elements in ascending order. After sorting, the minimum partition value can only occur between two consecutive elements, reducing the search space from all possible splits to a single linear scan.

Check Consecutive Differences

Iterate through the sorted array and compute the difference between each consecutive pair. Track the smallest difference as it represents the optimal partition value, since max(nums1) and min(nums2) will always be consecutive after sorting.

Return Minimum Partition Value

After scanning all consecutive differences, return the smallest difference found. This guarantees the correct minimum value for the partition without needing to test every subset combination.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n) time and O(1) or O(n) space depending on the sorting implementation. The linear scan for consecutive differences adds O(n) time. Overall, the solution efficiently reduces potential partition comparisons from exponential to linear after sorting.

What Interviewers Usually Probe

Ask if sorting simplifies the partition calculation.
Check understanding of Array plus Sorting pattern.
Probe knowledge of minimizing difference between subarray extremes.

Common Pitfalls or Variants

Common pitfalls

Not sorting before checking partitions leads to incorrect minimum values.
Attempting all subset splits results in time limit exceeded for large arrays.
Forgetting that the array must be split into two non-empty subarrays.

Follow-up variants

Find the partition value in a descending array without sorting first.
Compute maximum partition value instead of minimum.
Handle arrays with duplicate elements while minimizing partition value.

FAQ

What is the main strategy to solve Find the Value of the Partition?

The main strategy is to sort the array and check consecutive differences to find the minimum partition value efficiently.

Why is sorting important in this problem?

Sorting guarantees that the minimal partition difference occurs between consecutive elements, simplifying the solution to a linear scan.

Can this problem be solved without sorting?

Technically yes, but checking all partitions without sorting is inefficient and impractical for large arrays.

How does Array plus Sorting pattern help here?

It reduces the problem from examining all splits to just consecutive elements, leveraging sorted order to find the minimum partition value.

What should I watch out for when implementing the solution?

Ensure the array is sorted, only consider consecutive differences, and remember both subarrays must be non-empty to avoid invalid partitions.

terminal

Solution

Solution 1: Sorting

The problem requires us to minimize the partition value. Therefore, we can sort the array and then take the minimum difference between two adjacent numbers.

1

2

3

4

class Solution:
    def findValueOfPartition(self, nums: List[int]) -> int:
        nums.sort()
        return min(b - a for a, b in pairwise(nums))

Continue Practicing

#2736 maximum sum queries #2733 neither minimum nor maximum #2747 count zero request servers