Minimum Difference in Sums After Removal of Elements - Video Solutions

Problem Overview: You get an array of length 3n. Remove exactly n elements so the remaining 2n elements form two groups of n each (left and right). The goal is to minimize sum(left) - sum(right). The challenge is choosing which n elements to remove so the left side stays as small as possible while the right side becomes as large as possible.

Approach 1: Prefix and Suffix Analysis with Priority Queues (O(n log n) time, O(n) space)

Split the thinking into two independent goals. From the left side, you want the smallest possible sum of n elements among the first 2n positions. From the right side, you want the largest possible sum of n elements among the last 2n positions. Use a max-heap to keep the n smallest elements while scanning left to right. Store the running minimum sums in a prefix array. Then scan right to left using a min-heap to keep the n largest elements and store those sums as suffix values. For every valid split point between the two regions, compute prefix[i] - suffix[i+1] and track the minimum difference. Heap push/pop operations keep the selected set optimal at every step. This approach relies heavily on heap (priority queue) operations and sequential array traversal.

Approach 2: Sliding Window with Unordered Removal (O(n log n) time, O(n) space)

Another way to model the same decision process is maintaining two dynamic windows that track which elements currently belong to the left group and the right group. Balanced containers such as multiset or indexed heaps maintain the chosen n elements while allowing arbitrary removal when the window shifts. As the boundary moves across the middle section of the array, elements can migrate between candidate sets. Each update adjusts the running sum of the selected elements. The structure guarantees that the left container always holds the smallest possible n values and the right container keeps the largest n values. Conceptually this behaves like a sliding optimization layer over the array while maintaining optimal subsets. The reasoning resembles state tracking often seen in dynamic programming, but implemented with ordered structures.

Recommended for interviews: The prefix–suffix heap approach is the expected solution. It clearly separates the two optimization goals and runs in O(n log n) time with simple heap operations. Interviewers usually look for the insight that the first half should minimize its sum while the second half maximizes its sum, and that both can be computed independently using priority queues.