Practice/Amazon/Leetcode 2163. Minimum Difference in Sums After Removal of Elements

Leetcode 2163. Minimum Difference in Sums After Removal of Elements

CodingOptional

Problem

You are given an integer array nums of length 3n. Your task is to remove exactly n elements from this array such that the remaining 2n elements can be split into two consecutive parts of size n each, and the absolute difference between the sum of the first part and the sum of the second part is minimized.

After removing n elements, the remaining elements maintain their relative order from the original array. These 2n elements are then divided into:

• The first n elements (left partition)
• The last n elements (right partition)

Return the minimum possible absolute difference between the sum of the left partition and the sum of the right partition.

Requirements

1. Remove exactly n elements from the array
2. The remaining 2n elements must maintain their original relative order
3. Split the remaining elements into two consecutive groups of size n
4. Minimize the absolute difference between the sums of these two groups

Constraints

• nums.length == 3 * n where 1 <= n <= 10^5
• 1 <= nums[i] <= 10^5
• The array always has exactly 3n elements

Examples

Example 1:

Input: nums = [1, 2, 3] Output: 1 Explanation: We can remove element 2. The remaining elements are [1, 3]. Split into [1] and [3]. Difference = |1 - 3| = 2. Or remove 1, keeping [2, 3]: difference = |2 - 3| = 1. Or remove 3, keeping [1, 2]: difference = |1 - 2| = 1. Minimum difference is 1.

Example 2:

Input: nums = [3, 1, 2, 5, 4, 6] Output: 1 Explanation: With n=2, we need to remove 2 elements. One optimal strategy results in partitions with sums that differ by only 1.

Example 3:

Input: nums = [5, 5, 5, 5, 5, 5] Output: 0 Explanation: All elements are equal, so any valid removal gives equal sums.