[LeetCode 2163] Minimum Difference in Sums After Removal of Elements

문제 바로가기

Description

---

You are given a 0-indexed integer array nums consisting of 3 * n elements.

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:

• The first n elements belonging to the first part and their sum is sumfirst.
• The next n elements belonging to the second part and their sum is sumsecond.

The difference in sums of the two parts is denoted as sumfirst - sumsecond.

• For example, if sumfirst = 3 and sumsecond = 2, their difference is 1.
• Similarly, if sumfirst = 2 and sumsecond = 3, their difference is -1.

Return the minimum difference possible between the sums of the two parts after the removal of n elements.

Example 1

---

• Input: nums = [3,1,2]
• Output: -1
• Explanation:
  • Here, nums has 3 elements, so n = 1.

Thus we have to remove 1 element from nums and divide the array into two equal parts.

• 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.
• 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.
• 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. The minimum difference between sums of the two parts is min(-1,1,2) = -1.
  

Example 2

---

• Input: nums = [7,9,5,8,1,3]
• Output: 1
• Explanation:
  • Here n = 2. So we must remove 2 elements and divide the remaining array into two parts containing two elements each.
  • 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.
  • 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.
  • It can be shown that it is not possible to obtain a difference smaller than 1.

Constraints

---

• nums.length == 3 * n
• 1 <= n <= 10^5
• 1 <= nums[i] <= 10^5

Hint

---

Hint 1

  The lowest possible difference can be obtained when the sum of the first n elements in the resultant array is minimum, and the sum of the next n elements is maximum.
	

Hint 2

  For every index i, think about how you can find the minimum possible sum of n elements with indices lesser or equal to i, if possible.
	

Hint 3

  Similarly, for every index i, try to find the maximum possible sum of n elements with indices greater or equal to i, if possible.
	

Hint 4

  Now for all indices, check if we can consider it as the partitioning index and hence find the answer.
	

Code

---

내 제출

---

class Solution {
    public long minimumDifference(int[] nums) {
        int m = nums.length;
        int n = m / 3;
        long s = 0;
        long[] pre = new long[m + 1];
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int i = 1; i <= n * 2; ++i) {
            int x = nums[i - 1];
            s += x;
            pq.offer(x);
            if (pq.size() > n) {
                s -= pq.poll();
            }
            pre[i] = s;
        }
        s = 0;
        long[] suf = new long[m + 1];
        pq = new PriorityQueue<>();
        for (int i = m; i > n; --i) {
            int x = nums[i - 1];
            s += x;
            pq.offer(x);
            if (pq.size() > n) {
                s -= pq.poll();
            }
            suf[i] = s;
        }
        long ans = 1L << 60;
        for (int i = n; i <= n * 2; ++i) {
            ans = Math.min(ans, pre[i] - suf[i + 1]);
        }
        return ans;
    }
}

Runtime	Memory
157 ms	83.3 MB

다른 풀이

---

class Solution {
    public long minimumDifference(int[] nums) {

        int totallength = nums.length;
        int n = totallength/3;

        long[] leftMin = new long[totallength];
        long[] rightMin = new long[totallength];

       PriorityQueue<Integer> leftMaxHeap = new PriorityQueue<>(Collections.reverseOrder());
       long leftSum = 0;

       for(int i=0; i < 2*n; i++) {
         leftMaxHeap.offer(nums[i]);
         leftSum = leftSum + nums[i];
         if(leftMaxHeap.size() > n) {
            leftSum -= leftMaxHeap.poll();
         }
         if(leftMaxHeap.size() == n) {
            leftMin[i] = leftSum;
         }
       }

       PriorityQueue<Integer> rightMinHeap = new PriorityQueue<>();
      long rightSum = 0;

      for(int i = nums.length-1; i>= n; i--) {
            rightMinHeap.offer(nums[i]);
            rightSum += nums[i];
            if(rightMinHeap.size() > n) {
                rightSum -= rightMinHeap.poll();
            }
            if( rightMinHeap.size() == n) {
                rightMin[i] = rightSum;
            }
        }
        long result = Long.MAX_VALUE;
        for(int i = n-1; i< totallength-n;i++) {
            result = Math.min(result, leftMin[i]- rightMin[i+1]);
        }
        return result;



        
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/2100-2199/2163.Minimum%20Difference%20in%20Sums%20After%20Removal%20of%20Elements/Solution.java