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.
When the array is sorted, the differences between adjacent elements determine potential partitions. The optimal partition can be found by assessing the smallest difference between consecutive elements, which ensures both partitions are non-empty.
The C solution first sorts the input array. Then, it iterates through the sorted array, calculating differences between consecutive elements, and returns the smallest difference, which would represent the optimal partition value.
Time Complexity: O(n log n) due to sorting, and Space Complexity: O(1) for in-place operations.
This approach utilizes two pointers after sorting the array. Begin with the two pointers dividing the array into two parts, adjusting the pointers as necessary to minimize the partition value. The approach ensures each partition is non-empty while calculating the optimal value.
The C solution sorts the array and uses two pointers to find the minimum difference between consecutive elements after sorting, ensuring the partitions always remain valid and non-empty.
Time Complexity: O(n log n), Space Complexity: O(1).
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.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array.
| Approach | Complexity |
|---|---|
| Sort and Partition Using Breakpoint | Time Complexity: O(n log n) due to sorting, and Space Complexity: O(1) for in-place operations. |
| Two-Pointer Technique on Array | Time Complexity: O(n log n), Space Complexity: O(1). |
| Sorting | — |
| 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 |
Leetcode Weekly contest 350 - Medium - Find the Value of the Partition • Prakhar Agrawal • 477 views views
Watch 6 more video solutions →Practice Find the Value of the Partition with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor