Find the Value of the Partition — Medium Problem & Solution

Problem statement

Split nums into two non-empty arrays nums1 and nums2, using every element exactly once. The value of a partition is |max(nums1) - min(nums2)|.

Return the minimum value over all partitions.

Example 1

Input: nums = [1,3,2,4]
Output: 1
Explanation: `nums1 = [1,2]` and `nums2 = [3,4]` give `|2 - 3| = 1`.

Example 2

Input: nums = [100,1,10]
Output: 9
Explanation: `nums1 = [10]` and `nums2 = [100,1]`… the closest pair is 1 and 10.

Example 3

Input: nums = [5,5]
Output: 0

Constraints

• 2 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

How to solve Find the Value of the Partition

Sort the array; the answer is the smallest difference between adjacent elements.

Approach

1. Sort nums.
2. Scan the adjacent differences and return the smallest.

Why it works

For any two values a <= b, the partition putting everything up to a in nums1 and the rest in nums2 achieves b - a — so every adjacent pair is reachable. And any partition's value is a difference between two elements, which is never smaller than the closest adjacent gap. Hence the minimum gap is both attainable and a lower bound.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Non-adjacent pairs can never beat the closest adjacent gap.
• Both parts must be non-empty, which the adjacent split always satisfies.
• Duplicates give a gap of 0, which is the smallest possible answer.

Reference solution

Python

from typing import List

def findValueOfPartition(nums: List[int]) -> int:
    s = sorted(nums)
    return min(s[i] - s[i - 1] for i in range(1, len(s)))

JavaScript

var findValueOfPartition = function(nums) {
    var sorted = nums.slice();
    sorted.sort(function(a, b) { return a - b; });
    var best = sorted[1] - sorted[0];
    for (var i = 2; i < sorted.length; i++) {
        var d = sorted[i] - sorted[i - 1];
        if (d < best) best = d;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium