Find the Value of the Partition

Medium
996.

Find the Value of the Partition

Find the Value of the Partition is a medium coding problem on arrays and sorting, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var findValueOfPartition = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Value of the Partition — Problem & Solution

Find the Value of the Partition solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find the Value of the Partition is a medium coding problem on arrays and sorting, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Find the Value of the Partition

  1. Hint 1

    The value only depends on two elements: one maximum and one minimum.

  2. Hint 2

    Sort, and the best pair must be adjacent in the sorted order.

  3. Hint 3

    So the answer is the smallest gap between neighbours.

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

Java

public static int findValueOfPartition(int[] nums) {
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    int best = sorted[1] - sorted[0];
    for (int i = 2; i < sorted.length; i++) {
        best = Math.min(best, sorted[i] - sorted[i - 1]);
    }
    return best;
}

C++

int findValueOfPartition(vector<int>& nums) {
    vector<int> sorted = nums;
    sort(sorted.begin(), sorted.end());
    int best = sorted[1] - sorted[0];
    for (size_t i = 2; i < sorted.size(); i++) {
        best = min(best, sorted[i] - sorted[i - 1]);
    }
    return best;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms