Tightest Split

Medium

You are given an array of positive integers values. Distribute all of its elements into two **non-empty** groups A and B, with every element going into exactly one group. The score of a split is |max(A) − min(B)|. Return the smallest score you can achieve.

Example 1

values=[9, 2, 15, 4] → 2

Putting 2 and 4 in the first group and 9 and 15 in the second gives |4 − 9| = 5. Better: first group [2], second group [4, 9, 15], giving |2 − 4| = 2.

Example 2

values=[7, 7, 30] → 0

One 7 goes to the first group, the other 7 and 30 to the second: |7 − 7| = 0.

Constraints

2 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Sorting

Similar problems

Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Distinct Orderings With Repeats Medium Anagram Buckets Medium

Input

values=[9, 2, 15, 4]

Expected

Run checks the first 3 tests in your browser. Submit checks all 107 tests on the server, hidden ones included.