We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Find the Value of the Partition

Difficulty: Medium

Problem Description

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)|.

Return the integer denoting the value of such partition.

Key Insights

We need to partition the array into two non-empty subsets.
The optimal partition minimizes the absolute difference between the maximum of one subset and the minimum of the other.
Sorting the array helps in easily finding the minimum and maximum values of the subsets formed by partitioning the sorted array.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(1) - if we sort in place, otherwise O(n) for the sorted array.

Solution

To solve the problem, we can follow these steps:

Sort the input array nums.
The best way to partition the sorted array is to take the last element of nums1 (the maximum of nums1) and the first element of nums2 (the minimum of nums2).
The value of the partition can then be computed as |nums[i] - nums[i+1]| for the partition between the elements at index i and i+1 in the sorted array.
Return the minimum value obtained from these differences.

Code Solutions

def find_value_of_partition(nums):
    # Sort the array
    nums.sort()
    # Initialize a variable to hold the minimum partition value
    min_partition_value = float('inf')
    
    # Iterate through the sorted array to find the minimum partition value
    for i in range(len(nums) - 1):
        # Calculate the partition value
        partition_value = abs(nums[i] - nums[i + 1])
        # Update the minimum partition value
        min_partition_value = min(min_partition_value, partition_value)
    
    return min_partition_value

← Back to All Questions