Show problems as
Classic problem #2163HardArrayDynamic ProgrammingHeap (Priority Queue)

Minimum Difference in Sums After Removal of Elements

Real-world version: Auditor Discards from the Reading Ledger
Tracked in this browser only
Read Minimum Difference in Sums After Removal of Elements on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A meter has written down 3 * n readings in the order they were taken, given as nums.

An auditor strikes out exactly n of the readings, chosen freely. The 2 * n readings still standing keep their original order: the earlier half of them, meaning the first n that survive, is the opening block, and the later half, the last n that survive, is the closing block.

The score of a set of strike-outs is the total of the opening block minus the total of the closing block. This score may be negative. Return the smallest score the auditor can reach.

Examples

Example 1

Input
nums = [4, 9, 2]
Output
-5

Strike out the last reading, 2. The opening block is 4 and the closing block is 9, so the score is 4 - 9 = -5.

Example 2

Input
nums = [6, 2, 8, 3, 9, 4]
Output
-9

Strike out the 3 at position 3 and the 4 at position 5. The survivors in order are 6, 2, 8, 9, so the opening block totals 8 and the closing block totals 17, giving a score of -9.

Example 3

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

Every reading is 5, so whichever two are struck out both blocks total 10 and the score is 0.

Constraints

  • nums.length == 3 * n
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= 10^5
  • The score therefore lies between -10^10 and 10^10.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def minimum_difference(nums: list[int]) -> int:
Java
public long minimumDifference(int[] nums)

More on the same topics