💂Beginner's Guide to "Meeting Rooms III" - LeetCode 2163 (C++ | Python | JavaScript)

#programming #cpp #javascript #python

👋 Introduction

In today's guide, we'll tackle a complex array partitioning problem from LeetCode: Minimum Difference in Sums After Removal of Elements.

This problem challenges your understanding of heaps (priority queues) to dynamically track minimum and maximum sums, enabling you to calculate optimal differences efficiently.

💡 Problem Summary

Given a 3 * n length array nums.
Remove any subsequence of exactly n elements.
The remaining 2n elements split into:
- First half: sumfirst
- Second half: sumsecond
Return minimum possible value of sumfirst - sumsecond.

📁 Intuition

Use a max-heap to maintain the minimum possible sum of the first n elements up to index i.
Use a min-heap to maintain the maximum possible sum of the last n elements from index i to the end.
Iterate through valid split points to compute the minimum difference between left and right sums.

🛠️ C++ Code

class Solution {
public:
    void getMinSum(int n, vector<int>& arr, vector<long long>& left) {
        priority_queue<int> pq;
        long long sum = 0;

        for (int i = 0; i < arr.size(); i++) {
            if (pq.size() < n) {
                pq.push(arr[i]);
                sum += arr[i];
            } else if (arr[i] < pq.top()) {
                sum += arr[i] - pq.top();
                pq.pop();
                pq.push(arr[i]);
            }
            left[i] = sum;
        }
    }

    void getMaxSum(int n, vector<int>& arr, vector<long long>& right) {
        priority_queue<int, vector<int>, greater<int>> pq;
        long long sum = 0;

        for (int i = arr.size() - 1; i >= 0; i--) {
            if (pq.size() < n) {
                pq.push(arr[i]);
                sum += arr[i];
            } else if (arr[i] > pq.top()) {
                sum += arr[i] - pq.top();
                pq.pop();
                pq.push(arr[i]);
            }
            right[i] = sum;
        }
    }

    long long minimumDifference(vector<int>& nums) {
        int n = nums.size() / 3;
        vector<long long> leftSum(nums.size()), rightSum(nums.size());

        getMinSum(n, nums, leftSum);
        getMaxSum(n, nums, rightSum);

        long long ans = LLONG_MAX;
        for (int i = n - 1; i < nums.size() - n; ++i) {
            ans = min(ans, leftSum[i] - rightSum[i + 1]);
        }

        return ans;
    }
};

🐍 Python Code

import heapq

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums) // 3

        left = [0] * len(nums)
        max_heap, left_sum = [], 0
        for i in range(len(nums)):
            heapq.heappush(max_heap, -nums[i])
            left_sum += nums[i]
            if len(max_heap) > n:
                left_sum += heapq.heappop(max_heap)
            left[i] = left_sum

        right = [0] * len(nums)
        min_heap, right_sum = [], 0
        for i in range(len(nums)-1, -1, -1):
            heapq.heappush(min_heap, nums[i])
            right_sum += nums[i]
            if len(min_heap) > n:
                right_sum -= heapq.heappop(min_heap)
            right[i] = right_sum

        return min(left[i] - right[i+1] for i in range(n-1, len(nums)-n))

💻 JavaScript Code

var minimumDifference = function(nums) {
    const n = nums.length / 3;
    let left = Array(nums.length).fill(0);
    let right = Array(nums.length).fill(0);

    let maxHeap = new MinPriorityQueue({compare: (a, b) => b - a});
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        maxHeap.enqueue(nums[i]);
        sum += nums[i];
        if (maxHeap.size() > n) {
            sum -= maxHeap.dequeue().element;
        }
        left[i] = sum;
    }

    let minHeap = new MinPriorityQueue();
    sum = 0;
    for (let i = nums.length - 1; i >= 0; i--) {
        minHeap.enqueue(nums[i]);
        sum += nums[i];
        if (minHeap.size() > n) {
            sum -= minHeap.dequeue().element;
        }
        right[i] = sum;
    }

    let ans = Infinity;
    for (let i = n - 1; i < nums.length - n; i++) {
        ans = Math.min(ans, left[i] - right[i + 1]);
    }
    return ans;
};

📜 Key Takeaways

Use heaps to maintain dynamic sums.
The problem is a prefix-suffix optimization, where left tracks minimum sums and right tracks maximum sums.
Suitable for problems involving dynamic subsequence tracking.

✅ Final Thoughts

This problem is a classic example of applying greedy strategies combined with heaps for efficient segment optimization. The ability to dynamically manage the largest/smallest elements is key for advanced array manipulations.

Keep practicing such optimization patterns to handle similar competitive programming challenges effectively!