Problem

You are given a positive integer array nums.

Partition nums into two arrays, nums1 and nums2, such that:

  • Each element of the array nums belongs to either the array nums1 or the array nums2.
  • Both arrays are non-empty.
  • The value of the partition is minimized.

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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7

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 <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Sort and Partition at the Minimum Gap

Intuition

To minimize the value |max(nums1) - min(nums2)|, we want max(nums1) and min(nums2) to be as close as possible. If we sort the array, the optimal partition is between two consecutive elements with the smallest difference.

Approach

  1. Sort nums in ascending order.
  2. For each i from 0 to n-2, compute the difference nums[i+1] - nums[i].
  3. The minimum difference is the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int findValueOfPartition(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = INT_MAX;
        for (int i = 0; i + 1 < nums.size(); ++i) {
            ans = min(ans, nums[i+1] - nums[i]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func findValueOfPartition(nums []int) int {
    sort.Ints(nums)
    ans := 1<<31 - 1
    for i := 0; i+1 < len(nums); i++ {
        if nums[i+1]-nums[i] < ans {
            ans = nums[i+1] - nums[i]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int findValueOfPartition(int[] nums) {
        Arrays.sort(nums);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i + 1 < nums.length; ++i) {
            ans = Math.min(ans, nums[i+1] - nums[i]);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun findValueOfPartition(nums: IntArray): Int {
        nums.sort()
        var ans = Int.MAX_VALUE
        for (i in 0 until nums.size - 1) {
            ans = minOf(ans, nums[i+1] - nums[i])
        }
        return ans
    }
}
1
2
3
4

class Solution:
    def findValueOfPartition(self, nums: list[int]) -> int:
        nums.sort()
        return min(nums[i+1] - nums[i] for i in range(len(nums)-1))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn find_value_of_partition(nums: Vec<i32>) -> i32 {
        let mut nums = nums;
        nums.sort();
        let mut ans = i32::MAX;
        for i in 0..nums.len()-1 {
            ans = ans.min(nums[i+1] - nums[i]);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    findValueOfPartition(nums: number[]): number {
        nums.sort((a, b) => a - b);
        let ans = Number.MAX_SAFE_INTEGER;
        for (let i = 0; i + 1 < nums.length; ++i) {
            ans = Math.min(ans, nums[i+1] - nums[i]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) — For sorting the array.
  • 🧺 Space complexity: O(1) — Sorting in-place, only a few variables used.