2163. Minimum Difference in Sums After Removal of Elements Hard

1/**
2 * [2163] Minimum Difference in Sums After Removal of Elements
3 *
4 * You are given a 0-indexed integer array nums consisting of 3 * n elements.
5 * You are allowed to remove any subsequence of elements of size exactly n from nums. The remaining 2 * n elements will be divided into two equal parts:
6 * 
7 * 	The first n elements belonging to the first part and their sum is sumfirst.
8 * 	The next n elements belonging to the second part and their sum is sumsecond.
9 * 
10 * The difference in sums of the two parts is denoted as sumfirst - sumsecond.
11 * 
12 * 	For example, if sumfirst = 3 and sumsecond = 2, their difference is 1.
13 * 	Similarly, if sumfirst = 2 and sumsecond = 3, their difference is -1.
14 * 
15 * Return the minimum difference possible between the sums of the two parts after the removal of n elements.
16 *  
17 * Example 1:
18 * 
19 * Input: nums = [3,1,2]
20 * Output: -1
21 * Explanation: Here, nums has 3 elements, so n = 1. 
22 * Thus we have to remove 1 element from nums and divide the array into two equal parts.
23 * - If we remove nums[0] = 3, the array will be [1,2]. The difference in sums of the two parts will be 1 - 2 = -1.
24 * - If we remove nums[1] = 1, the array will be [3,2]. The difference in sums of the two parts will be 3 - 2 = 1.
25 * - If we remove nums[2] = 2, the array will be [3,1]. The difference in sums of the two parts will be 3 - 1 = 2.
26 * The minimum difference between sums of the two parts is min(-1,1,2) = -1. 
27 * 
28 * Example 2:
29 * 
30 * Input: nums = [7,9,5,8,1,3]
31 * Output: 1
32 * Explanation: Here n = 2. So we must remove 2 elements and divide the remaining array into two parts containing two elements each.
33 * If we remove nums[2] = 5 and nums[3] = 8, the resultant array will be [7,9,1,3]. The difference in sums will be (7+9) - (1+3) = 12.
34 * To obtain the minimum difference, we should remove nums[1] = 9 and nums[4] = 1. The resultant array becomes [7,5,8,3]. The difference in sums of the two parts is (7+5) - (8+3) = 1.
35 * It can be shown that it is not possible to obtain a difference smaller than 1.
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	nums.length == 3 * n
41 * 	1 <= n <= 10^5
42 * 	1 <= nums[i] <= 10^5
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/minimum-difference-in-sums-after-removal-of-elements/
48// discuss: https://leetcode.com/problems/minimum-difference-in-sums-after-removal-of-elements/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn minimum_difference(nums: Vec<i32>) -> i64 {
54        
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_2163() {
66    }
67}
68