MEET DEMANDS OF NEIGBOURING ELEMENTS (IMPORTANT OA)

https://practice.geeksforgeeks.org/problems/wine-buying-and-selling/1

Given an array, Arr[] of size N represents N house built along a straight line with equal distance between adjacent houses. Each house has a certain number of wine and they want to buy/sell those wines to other houses. Transporting one bottle of wine from one house to an adjacent house results in one unit of work. The task is to find the minimum number of work is required to fulfill all the demands of those N houses.

if arr[i] < 0, then ith house wants to sell arr[i] number of a wine bottle to other houses.
if arr[i] > 0, then ith house wants to buy arr[i] number of a wine bottle from other houses.
Note: One have to print the minimum number such that, all the house can buy/sell wine to each other.
It is guaranteed that sum of all the elements of the array will be 0.

Example 1:

Input: N = 5,
Arr[] = {5, -4, 1, -3, 1}
Output: 9
Explanation:
1th house can sell 4 wine bottles to 0th house,
total work needed 4*(1-0) = 4, new arr[] = 1,0,1,-3,1
now 3rd house can sell wine to 0th, 2th and 4th.
so total work needed = 1*(3-0)+1*(3-2)+1*(4-3) = 5
So total work will be 4+5 = 9
Example 2:

Input: N = 6,
Arr[]={-1000, -1000, -1000, 1000, 1000, 1000}
Output: 9000
Explanation:
0th house sell 1000 wine bottles to 3rd house,
total work needed 1000*(3-0) = 3000.
1st house sell 1000 wine bottles to 4th house,
total work needed 3000 + 1000*(3-0) = 6000.
2nd house sell 1000 wine bottles to 5th house,
total work needed 6000 + 1000*(3-0) = 9000.
So total work will be 9000 unit.

Constraints:
1 ≤ N ≤ 10^5
-10^6 ≤ Arr[i] ≤ 10^6

---------------------------------------------------------------------------------------------------------------------------------------

MY SOLUTION -
class Solution{
  public:
  long long int wineSelling(vector<int>& arr, int n){
      stack<pair<int,int>> s;
      long long int res=0;
      for(int i=0;i<n;i++){
          while(!s.empty() && ((arr[i]<0 && s.top().first>0) || (arr[i]>0 && s.top().first<0))){
             //   (arr[i]<0 && s.top().first>0) --- current index wanna sell and prev wanna buy
            //    (arr[i]>0 && s.top().first<0) --- current index wanna buy and prev wanna sell
              int transfer=min(abs(s.top().first),abs(arr[i]));  // this is the trade amount
              res+=(transfer*(i-s.top().second)); // work done calculated between trades

              arr[i]>0 ? (arr[i]-=transfer) : (arr[i]+=transfer); // do the neccessary arithmetic

              auto prevhouse=s.top();
              s.pop();

              prevhouse.first>0 ? (prevhouse.first-=transfer) : (prevhouse.first+=transfer); // do the neccessary arithmetic

              if(prevhouse.first!=0){
                  s.push(prevhouse);
              }
          }
          if(arr[i]!=0){
              s.push({arr[i],i});
          }
      }
      return res;
  }
};

---------------------------------------------------------------------------------------------------------------------------------------

WEBSITE SOLUTION -

class Solution{
  public:
  long long int wineSelling(vector<int>& Arr, int N){

        vector<pair<int,int> > buy;
        vector<pair<int,int> > sell;
        for(int i=0;i<N;i++){
            if(Arr[i]>0) buy.push_back({Arr[i],i});
            else sell.push_back({Arr[i],i});
        }
        long long int ans = 0;
        int i=0,j=0;
        while(i<buy.size() and j<sell.size()){
            long long int x = min(buy[i].first,-sell[j].first);
            buy[i].first -= x;
            sell[j].first += x;
            long long int diff = abs(buy[i].second - sell[j].second);
            ans += (x * diff);
            if(buy[i].first == 0) i++;
            if(sell[j].first == 0) j++;
        }
        return ans;
  }
};