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.

&nbsp;
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.


&nbsp;
Constraints:


	nums.length == 3 * n
	1 &lt;= n &lt;= 105
	1 &lt;= nums[i] &lt;= 105


class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        h=heapq
        k=len(nums)//3
        min_heap, max_heap, min_sol, max_sol, min_sum, max_sum, sol=[] , [] , [] , [] , 0 , 0, []
        h.heapify(max_heap) , h.heapify(min_heap)
        for x in nums[:-k]:
            h.heappush(min_heap,-x)
            min_sum+=x
            if len(min_heap)>k: min_sum+=h.heappop(min_heap)
            min_sol.append(min_sum)
        for x in nums[::-1][:-k]:
            h.heappush(max_heap,x)
            max_sum+=x
            if len(max_heap)>k: max_sum-=h.heappop(max_heap)
            max_sol.append(max_sum)
        min_sol =min_sol[k-1:]
        max_sol=max_sol[k-1:][::-1]
        return min( min_value - max_value for min_value , max_value in zip(min_sol,max_sol) )
class Solution {
    public long minimumDifference(int[] nums) {
        int n=nums.length; //length of nums
        int len3=n/3; // 1/3 length
        long res=Long.MAX_VALUE; // final result;
        //Try to make first part as min as possible;
        //first[m] store the value, the min value of the size=len3, from[0,1,..., m];
        long[] first=new long[n];
        //Try to make second part as max as possible;
        //second[m] store the value, the max value of the size=len3, from[m,...,n-1];
        long[] second=new long[n];

//--------------------for first part compute -------------------------------------
        //Build max heap for first part;
        PriorityQueue<Integer> max=new PriorityQueue<Integer>(Comparator.reverseOrder());

        long sum=0;

        // Initialize with the first 1/3 n part.
        for(int i=0;i<len3;i++){
            sum+=nums[i];
            max.add(nums[i]);
        }
        //For the second part between 1/3 ~ 2/3. When we move to next index.
        //we keep the sum as total 1/3n size: each time poll the max one and add the new one;
        //And we keep tracking the exchange by long[] first;
        //
        for(int i=len3;i<=2*len3;i++){
            first[i]=sum; //add sum from 1/3
            max.add(nums[i]); //put new one in queue;
            sum+=nums[i]; //sum + new one;
            sum-=max.poll(); //sum - max one;
        }
//--------------------for second part compute -----------------------
        sum=0;
        //Build min heap for first part;
        PriorityQueue<Integer> min=new PriorityQueue<Integer>();
        // Initialize with the last 1/3 n part.
        for(int i=0;i<len3;i++){
            sum+=nums[n-1-i];
            min.add(nums[n-1-i]);
        }
        //For the second part between 2/3~1/3 When we move to next index:
        // we keep update the sum with(+ new element, - min element), and update second;
        for(int i=len3;i<=2*len3;i++){
            second[n-i]=sum;
            min.add(nums[n-1-i]);
            sum+=nums[n-1-i];
            sum-=min.poll();
        }
//-----------------compute the final result------------

        //find the max value in second part [ i,..., n-1];
        //find the min value in first part [0,....,i];
        // find the result;
        for(int i=len3;i<=2*len3;i++){
            res=Math.min(res,first[i]-second[i]);
        }

        return res;
    }
}
class Solution {
public:
    long long minimumDifference(vector<int>& nums) {
        int N = nums.size();
        int n = N/3;
        priority_queue<int> pq;
        map<int, long long> m;
        long long sum = 0;
        for(int i=0;i<n;i++){
            sum += nums[i];
            pq.push(nums[i]);
        }
        for(int i=0;i<=n;i++){
            if(i == 0){
                m[i] = sum;
            }
            else{
                pq.push(nums[n+i-1]);
                sum += nums[i+n-1];
                sum -= pq.top();
                pq.pop();
                m[i] = sum;
            }
        }
        sum = 0;
        priority_queue<int, vector<int>, greater<int>> p;
        for(int i=N-1;i>N-1-n;i--){
            sum += nums[i];
            p.push(nums[i]);
        }
        for(int i=0;i<=n;i++){
            if(i == 0){
                m[n-i] -= sum;
            }
            else{
                p.push(nums[N-n-i]);
                sum += nums[N-n-i];
                sum -= p.top();
                p.pop();
                m[n-i] -= sum;
            }
        }
        long long ans = 9223372036854775807;
        for(auto it : m){
            ans = min(ans, it.second);
        }
        return ans;
    }
};
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumDifference = function(nums) {
//Creating heap 
    class Heap{
        constructor(type){
            this.type = type;
            this.data = [];
            this.data[0] = undefined;
        }
        print(){
            for(let i=1;i<this.data.length;i++){
                console.log(this.data[i])
            }
        }
        getSize(){
            return this.data.length-1;
        }
        insert(value){
            this.data.push(value);
            if(this.data.length==2){
                return ;
            }
            let lastIndex = this.data.length-1;
            while(this.data[Math.floor(lastIndex/2)]!==undefined && this.compare(this.data[lastIndex],this.data[Math.floor(lastIndex/2)])>0){
                let temp = this.data[Math.floor(lastIndex/2)];
                this.data[Math.floor(lastIndex/2)] = this.data[lastIndex];
                this.data[lastIndex] = temp;
                lastIndex = Math.floor(lastIndex/2);
            }
        }
        //This returns a positive number if a is greater than b. Here meaing of being greater depends on the type of heap. For max heap it will return positive number if a>b and for min heap it will return positive number if a<b . 
        compare(a,b){
            if(this.type==="min"){
                return b-a;
            }else{
                return a-b;
            }
        }
        removeTop(){
            let max = this.data[1];
            if(this.getSize()>1){
                this.data[1] = this.data.pop();
                this.heapify(1);
            }else{//If the size is 0 then just remove the element, no shifting and hipify will be applicable
                this.data.pop();
            }
            return max;
        }
        getTop(){
            let max = null;
            if(this.getSize()>=1){
                max = this.data[1];
            }
            return max;
        }
        heapify(pos){
            if(pos*2>this.data.length-1){
                //That means element at index 'pos' is not having any child
                return;
            }
            if(
                (this.data[pos*2]!==undefined && this.compare(this.data[pos*2],this.data[pos])>0)
              || (this.data[pos*2+1]!==undefined && this.compare(this.data[pos*2+1],this.data[pos])>0)
              ){
                if(this.data[pos*2+1]===undefined || this.compare(this.data[pos*2+1],this.data[pos*2])<=0){
                    let temp = this.data[pos*2];
                    this.data[pos*2] = this.data[pos];
                    this.data[pos] = temp;
                    this.heapify(pos*2);
                }else{
                    let temp = this.data[pos*2+1];
                    this.data[pos*2+1] = this.data[pos];
                    this.data[pos] = temp;
                    this.heapify(pos*2+1);
                }
            }
        }
    }
    let maxHeap=new Heap(),minHeap=new Heap('min'),sum=0;
    let n = nums.length/3,leftArr=[],rightArr=[];
    for(let i=0;i<2*n;i++){
        if(maxHeap.getSize()<n){
            sum += nums[i];
            maxHeap.insert(nums[i]);
        }else{
            if(maxHeap.getTop()>nums[i]){
                let top = maxHeap.removeTop();
                sum -= top;
                sum += nums[i];
                maxHeap.insert(nums[i]);
            }
            
        }
        if(maxHeap.getSize()===n){
            leftArr.push(sum);
        }
    }
    sum=0;
    for(let i=3*n-1;i>=n;i--){
        if(minHeap.getSize()<n){
            sum += nums[i];
            minHeap.insert(nums[i]);
        }else{
            if(minHeap.getTop()<nums[i]){
                let top = minHeap.removeTop();
                sum -= top;
                sum += nums[i];
                minHeap.insert(nums[i]);
            }
            
        }
        if(minHeap.getSize()===n){
            rightArr.push(sum);
        }
    }
    rightArr.reverse();
    let min = Number.MAX_SAFE_INTEGER;
    
    for(let i=0;i<leftArr.length;i++){
        min = Math.min(min,leftArr[i]-rightArr[i]);
    }
    return min;
};
Minimum Difference in Sums After Removal of Elements