Watch 7 video solutions for Find the Value of the Partition, a medium level problem involving Array, Sorting. This walkthrough by Prakhar Agrawal has 477 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a positive integer array nums.
Partition nums into two arrays, nums1 and nums2, such that:
nums belongs to either the array nums1 or the array nums2.The value of the partition is |max(nums1) - min(nums2)|.
Here, max(nums1) denotes the maximum element of the array nums1, and min(nums2) denotes the minimum element of the array nums2.
Return the integer denoting the value of such partition.
Example 1:
Input: nums = [1,3,2,4] Output: 1 Explanation: 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 Explanation: 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 <= 1051 <= nums[i] <= 109Problem Overview: You are given an integer array and must split it into two non‑empty partitions. The partition value is defined as |max(left) - min(right)|. The goal is to choose the split that minimizes this value.
The key observation: if the array is ordered, the optimal split always happens between two adjacent numbers. Once sorted, the maximum of the left side becomes nums[i] and the minimum of the right side becomes nums[i+1]. The problem reduces to finding the smallest difference between neighboring elements.
Approach 1: Sort and Partition Using Breakpoint (O(n log n) time, O(1) extra space)
Sort the array first using any comparison sort. After sorting, iterate once through the array and compute nums[i+1] - nums[i] for every adjacent pair. Each pair represents a potential partition where the left side contains elements up to i and the right side starts at i+1. Track the minimum difference encountered during the scan. Sorting ensures that all elements in the left partition are less than or equal to those in the right partition, so the absolute value is unnecessary. This approach is straightforward and relies on properties of ordered data, making it the most common interview solution when working with arrays and sorting.
Approach 2: Two-Pointer Scan on the Sorted Array (O(n log n) time, O(1) space)
After sorting the array, maintain two pointers left and right where right = left + 1. Move both pointers forward while computing the difference between the two positions. The pointers effectively represent the boundary between the two partitions. This framing highlights the partition boundary explicitly and mirrors common two‑pointer patterns used in array problems. The minimum difference found during this linear scan is the final answer.
Recommended for interviews: The expected approach is sorting followed by a single pass to check adjacent differences. Explaining the reasoning behind why the optimal partition must occur between neighboring elements in the sorted array demonstrates strong algorithmic intuition. A brute force check of every possible partition shows understanding, but recognizing the sorted adjacency insight and reducing the problem to a single pass shows stronger problem‑solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Partition Check | O(n^2) | O(1) | Educational baseline to verify logic by checking every split |
| Sort and Adjacent Difference | O(n log n) | O(1) or O(n) depending on sort | General case; simplest and most common solution |
| Two-Pointer Scan After Sorting | O(n log n) | O(1) | When emphasizing partition boundaries using two pointers |