Find the Value of the Partition

Problem Description

Given an array of positive integers, partition it into two non-empty arrays nums1 and nums2 such that the value |max(nums1) - min(nums2)| is minimized. Return this minimum partition value.

Key Insights

• The optimal partition will come from selecting a threshold where all numbers less than or equal to a chosen number form nums1 and the rest form nums2.
• Sorting the array makes it easier to pick such a threshold. After sorting, the best partition will be between two adjacent elements.
• The minimum partition value is the smallest difference between consecutive sorted elements.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(n) for storing the sorted array (depending on sorting implementation).

Solution

The approach is as follows:

1. Sort the input array.
2. Iterate over the sorted array and compute the difference between every pair of consecutive elements.
3. The minimum of these differences is the answer, as partitioning the array between these two elements minimizes |max(nums1) - min(nums2)|.
4. This works since once sorted, any valid partition will have its maximum element in the left partition and minimum in the right partition, and the smallest adjacent difference guarantees the minimum possible partition value.

Data structures:

• Sorted array

Algorithmic approach:

• Use sorting and linear iteration to determine the optimal partition point.

Code Solutions