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.
Your Task:  
You don't need to read input or print anything. Complete the function wineSelling() which takes the array Arr[] and its size N as input parameters and returns an integer as output.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^5
-10^6 ≤ Arr[i] ≤ 10^6

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Greedy algorithms

Starter code: #User function Template for python3





class Solution:	

	def wineSelling(self, Arr, N):

		# code here

Solutions:
class Solution:

	def wineSelling(self, Arr, N):
		(count, ans) = (0, 0)
		for i in Arr:
			ans += abs(count)
			count += i
		return ans


class Solution:

	def wineSelling(self, Arr, N):
		work = need = 0
		for i in Arr:
			work += abs(need)
			need += i
		return work


class Solution:

	def wineSelling(self, arr, N):
		buyarr = []
		sellarr = []
		for i in range(N):
			if arr[i] < 0:
				sellarr.append([arr[i], i])
			else:
				buyarr.append([arr[i], i])
		distance = 0
		i = 0
		j = 0
		while i < len(buyarr) and j < len(sellarr):
			x = min(buyarr[i][0], -sellarr[j][0])
			buyarr[i][0] -= x
			sellarr[j][0] += x
			distance += abs(buyarr[i][1] - sellarr[j][1]) * x
			if buyarr[i][0] == 0:
				i += 1
			elif sellarr[j][0] == 0:
				j += 1
		return distance


class Solution:

	def wineSelling(self, a, n):
		q1 = []
		q2 = []
		for i in range(n - 1, -1, -1):
			if a[i] >= 0:
				q1.append([a[i], i])
			else:
				q2.append([a[i], i])
		c = 0
		while q2:
			(x, y) = q2.pop()
			(f, h) = q1.pop()
			if -x <= f:
				c += -x * abs(y - h)
				f = f + x
				if f > 0:
					q1.append([f, h])
			else:
				c += f * abs(y - h)
				x = x + f
				q2.append([x, y])
		return c


import heapq

class Solution:

	def wineSelling(self, Arr, N):
		work = 0
		heap = []
		heapq.heapify(heap)
		for i in range(len(Arr)):
			if Arr[i] < 0:
				heapq.heappush(heap, i)
		for i in range(len(Arr)):
			while Arr[i] > 0:
				j = heapq.heappop(heap)
				if -Arr[j] > Arr[i]:
					Arr[j] += Arr[i]
					work += Arr[i] * abs(i - j)
					Arr[i] = 0
					heapq.heappush(heap, j)
				else:
					Arr[i] += Arr[j]
					work += -Arr[j] * abs(i - j)
					Arr[j] = 0
		return work


class Solution:

	def wineSelling(self, Arr, N):
		stack = []
		cost = 0
		for (i, qty) in enumerate(Arr):
			if not stack:
				stack.append([i, qty])
			elif stack[-1][1] < 0 and qty > 0 or (stack[-1][1] > 0 and qty < 0):
				remain = qty
				while stack and remain != 0:
					(last_i, last_q) = stack.pop()
					if abs(last_q) > abs(remain):
						cost += abs(remain) * abs(i - last_i)
						stack.append([last_i, last_q + remain])
						remain = 0
					elif abs(last_q) < abs(remain):
						cost += abs(last_q) * abs(i - last_i)
						remain += last_q
						if not stack:
							stack.append([i, remain])
							remain = 0
					else:
						cost += abs(last_q) * abs(i - last_i)
						remain = 0
			else:
				stack.append([i, qty])
		return cost


class Solution:

	def wineSelling(self, A, N):
		cnt = ans = 0
		for i in A:
			ans += abs(cnt)
			cnt += i
		return ans


from collections import deque

class Solution:

	def wineSelling(self, arr, n):
		b = deque()
		s = deque()
		count = 0
		for i in range(n):
			ele = [i, arr[i]]
			if ele[1] < 0:
				s.append(ele)
			else:
				b.append(ele)
			while len(b) != 0 and len(s) != 0:
				buy = b.popleft()
				sell = s.popleft()
				if abs(buy[1]) >= abs(sell[1]):
					buy[1] = buy[1] + sell[1]
					count += abs(buy[0] - sell[0]) * abs(sell[1])
					b.append(buy)
				else:
					sell[1] = buy[1] + sell[1]
					count += abs(buy[0] - sell[0]) * buy[1]
					s.append(sell)
		return count


class Solution:

	def wineSelling(self, Arr, N):
		buy = 0
		sell = 0
		cost = 0
		while buy < N and sell < N:
			while buy < N:
				if Arr[buy] > 0:
					break
				buy += 1
			while sell < N:
				if Arr[sell] < 0:
					break
				sell += 1
			if buy == N or sell == N:
				break
			if Arr[buy] < abs(Arr[sell]):
				cost += Arr[buy] * abs(sell - buy)
				Arr[sell] += Arr[buy]
				Arr[buy] = 0
				buy += 1
			else:
				cost += abs(Arr[sell]) * abs(sell - buy)
				Arr[buy] += Arr[sell]
				Arr[sell] = 0
				sell += 1
		return cost


class Solution:

	def wineSelling(self, Arr, N):
		positive = negative = ans = 0
		while 1:
			while positive < N and Arr[positive] <= 0:
				positive += 1
			while negative < N and Arr[negative] >= 0:
				negative += 1
			if positive >= N or negative >= N:
				break
			val2 = abs(Arr[negative])
			diff = abs(positive - negative)
			if Arr[positive] >= val2:
				ans += diff * val2
				Arr[positive] += Arr[negative]
				Arr[negative] = 0
			else:
				ans += diff * Arr[positive]
				Arr[negative] += Arr[positive]
				Arr[positive] = 0
		return ans


class Solution:

	def wineSelling(self, arr, n):
		buy = []
		sell = []
		work = 0
		for i in range(n):
			if arr[0] == 0:
				continue
			if arr[i] > 0:
				wine_buy = arr[i]
				while sell != [] and wine_buy > 0:
					(index, wines) = sell.pop()
					work += (i - index) * min(abs(wines), wine_buy)
					wine_buy = wine_buy + wines
					if wine_buy < 0:
						sell.append((index, wine_buy))
				if wine_buy > 0:
					buy.append((i, wine_buy))
			else:
				wine_sell = arr[i]
				while buy != [] and wine_sell < 0:
					(index, wines) = buy.pop()
					work += (i - index) * min(wines, abs(wine_sell))
					wine_sell = wine_sell + wines
					if wine_sell > 0:
						buy.append((index, wine_sell))
				if wine_sell < 0:
					sell.append((i, wine_sell))
		return work


class Solution:

	def wineSelling(self, Arr, N):
		sm = 0
		work = 0
		prev = 0
		for i in range(N):
			work += abs(prev)
			prev += Arr[i]
		return work


class Solution:

	def wineSelling(self, a, N):
		p = []
		n = []
		p_ind = []
		n_ind = []
		ans = 0
		for i in range(N):
			if a[i] > 0:
				p.append(a[i])
				p_ind.append(i)
			else:
				n.append(a[i])
				n_ind.append(i)
			while len(p) != 0 and len(n) != 0:
				if p[0] > abs(n[0]):
					p[0] -= abs(n[0])
					ans += abs((p_ind[0] - n_ind[0]) * n[0])
					n.pop(0)
					n_ind.pop(0)
				elif p[0] < abs(n[0]):
					n[0] += p[0]
					ans += abs((p_ind[0] - n_ind[0]) * p[0])
					p.pop(0)
					p_ind.pop(0)
				else:
					ans += abs((p_ind[0] - n_ind[0]) * n[0])
					n.pop(0)
					p.pop(0)
					p_ind.pop(0)
					n_ind.pop(0)
		return ans


class Solution:

	def wineSelling(self, arr, n):
		cost = 0
		b = 0
		s = 0
		while b < n and s < n:
			while arr[b] <= 0:
				b += 1
				if b == n:
					return cost
			while arr[s] >= 0:
				s += 1
				if s == n:
					return cost
			if abs(arr[b]) >= abs(arr[s]):
				cost += abs(b - s) * abs(arr[s])
				arr[b] += arr[s]
				arr[s] = 0
			else:
				cost += abs(b - s) * abs(arr[b])
				arr[s] += arr[b]
				arr[b] = 0
		return cost


class Solution:

	def wineSelling(self, A, N):
		(buy, sell) = ([], [])
		for i in range(N):
			if A[i] > 0:
				buy.append([A[i], i])
			else:
				sell.append([A[i], i])
		(ans, i, j) = (0, 0, 0)
		while i < len(buy) and j < len(sell):
			mn = min(buy[i][0], -1 * sell[j][0])
			buy[i][0] -= mn
			sell[j][0] += mn
			dist = abs(buy[i][1] - sell[j][1])
			ans += mn * dist
			if buy[i][0] == 0:
				i += 1
			if sell[j][0] == 0:
				j += 1
		return ans


class Solution:

	def wineSelling(self, Arr, N):
		c = 0
		s = 0
		for i in Arr:
			s += abs(c)
			c += i
		return s


class Solution:

	def wineSelling(self, Arr, N):
		i = j = 0
		cost = 0
		while True:
			while i < N and Arr[i] <= 0:
				i += 1
			while j < N and Arr[j] >= 0:
				j += 1
			if i == N or j == N:
				break
			diff = min(abs(Arr[j]), abs(Arr[i]))
			cost += diff * abs(i - j)
			Arr[i] -= diff
			Arr[j] += diff
		return cost


class Solution:

	def wineSelling(self, arr, n):
		ans = 0
		i = 0
		j = 0
		while True:
			while i < n and arr[i] <= 0:
				i += 1
			while j < n and arr[j] >= 0:
				j += 1
			if i == n or j == n:
				break
			change = min(arr[i], -arr[j])
			ans += abs(i - j) * change
			arr[i] -= change
			arr[j] += change
		return ans


class Solution:

	def wineSelling(self, Arr, N):
		buy = []
		sell = []
		for i in range(N):
			if Arr[i] > 0:
				buy.append([Arr[i], i])
			else:
				sell.append([Arr[i], i])
		ans = 0
		i = 0
		j = 0
		while i < len(buy) and j < len(sell):
			x = min(buy[i][0], -sell[j][0])
			buy[i][0] -= x
			sell[j][0] += x
			diff = abs(buy[i][1] - sell[j][1])
			ans += x * diff
			if buy[i][0] == 0:
				i += 1
			if sell[j][0] == 0:
				j += 1
		return ans


class Solution:

	def wineSelling(self, arr, N):
		buy = []
		sell = []
		for i in range(len(arr)):
			if arr[i] > 0:
				buy.append([arr[i], i])
		for i in range(len(arr)):
			if arr[i] < 0:
				sell.append([arr[i], i])
		i = 0
		j = 0
		ans = 0
		while i < len(buy) and j < len(sell):
			temp = min(buy[i][0], abs(sell[j][0]))
			buy[i][0] -= temp
			sell[j][0] += temp
			ans += temp * abs(buy[i][1] - sell[j][1])
			if sell[j][0] == 0:
				j += 1
			if buy[i][0] == 0:
				i += 1
		return ans


class Solution:

	def wineSelling(self, arr, n):
		(buy, sell) = ([], [])
		for i in range(n):
			if arr[i] > 0:
				buy.append([arr[i], i])
			else:
				sell.append([arr[i], i])
		(ans, i, j) = (0, 0, 0)
		while i < len(buy) and j < len(sell):
			m = min(buy[i][0], -1 * sell[j][0])
			buy[i][0] -= m
			sell[j][0] += m
			dis = abs(buy[i][1] - sell[j][1])
			ans += m * dis
			if buy[i][0] == 0:
				i += 1
			if sell[j][0] == 0:
				j += 1
		return ans


class Solution:

	def wineSelling(self, Arr, N):
		(b, s) = ([], [])
		for i in range(N):
			if Arr[i] > 0:
				b.append([Arr[i], i])
			else:
				s.append([Arr[i], i])
		(ans, i, j) = (0, 0, 0)
		while i < len(b) and j < len(s):
			m = min(b[i][0], -1 * s[j][0])
			b[i][0] -= m
			s[j][0] += m
			dist = abs(b[i][1] - s[j][1])
			ans += m * dist
			if b[i][0] == 0:
				i += 1
			if s[j][0] == 0:
				j += 1
		return ans


class Solution:

	def wineSelling(self, l, n):
		b = []
		s = []
		a = 0
		for i in l:
			if i > 0:
				b.append([i, a])
			else:
				s.append([i, a])
			a += 1
		(ans, i, j) = (0, 0, 0)
		mn = max(l)
		while i < len(b) and j < len(s):
			mn = min(b[i][0], abs(s[j][0]))
			b[i][0] -= mn
			s[j][0] += mn
			d = abs(b[i][1] - s[j][1])
			ans += mn * d
			if b[i][0] == 0:
				i += 1
			if s[j][0] == 0:
				j += 1
		return ans


class Solution:

	def wineSelling(self, arr, N):
		pfs = [0]
		sfs = [0]
		ans = 0
		for i in range(N):
			pfs.append(pfs[-1] + arr[i])
			if pfs[-1] > 0:
				ans += pfs[-1]
		arr = arr[::-1]
		for i in range(N):
			sfs.append(sfs[-1] + arr[i])
			if sfs[-1] > 0:
				ans += sfs[-1]
		return ans


class Solution:

	def wineSelling(self, Arr, N):
		ans = 0
		stack = []
		for i in range(N):
			stack.append([Arr[i], i])
			val = True
			while val:
				if not stack:
					val = False
				elif stack[-1][0] == 0:
					stack.pop()
					continue
				elif len(stack) == 1:
					val = False
				elif stack[-1][0] < 0 and stack[-2][0] < 0:
					val = False
				elif stack[-1][0] > 0 and stack[-2][0] > 0:
					break
				else:
					(lv, li) = stack.pop()
					(sv, si) = stack.pop()
					ans += min(abs(lv), abs(sv)) * abs(li - si)
					temp = lv + sv
					if abs(lv) >= abs(sv):
						stack.append([temp, li])
					else:
						stack.append([temp, si])
		return ans


class Solution:

	def wineSelling(self, Arr, N):
		count = 0
		summa = 0
		for item in Arr:
			summa += item
			count += abs(summa)
		return count


class Solution:

	def wineSelling(self, Arr, N):
		stack = []
		cost = 0
		for (i, e) in enumerate(Arr):
			if not stack:
				stack.append((e, i))
				continue
			while stack and stack[-1][0] * e < 0:
				(other, j) = stack.pop()
				cost += min(abs(other), abs(e)) * (i - j)
				if abs(e) > abs(other):
					e += other
				else:
					other += e
					e = 0
					if other != 0:
						stack.append((other, j))
			if e != 0:
				stack.append((e, i))
		return cost


class Solution:

	def wineSelling(self, a, N):
		b = 0
		s = 0
		ans = 0
		while b < N and s < N:
			while a[b] <= 0:
				b += 1
				if b == N:
					return ans
			while a[s] >= 0:
				s += 1
				if s == N:
					return ans
			if abs(a[b]) >= abs(a[s]):
				ans += abs(b - s) * abs(a[s])
				a[b] += a[s]
				a[s] = 0
			if abs(a[s]) > abs(a[b]):
				ans += abs(b - s) * abs(a[b])
				a[s] += a[b]
				a[b] = 0
		return ans


class Solution:

	def wineSelling(self, Arr, N):
		ans = 0
		test = Arr[0]
		for i in range(1, N):
			ans += abs(test)
			test += Arr[i]
		return ans


class Solution:

	def wineSelling(self, Arr, N):
		ret = 0
		Arr[1] += Arr[0]
		ret += abs(Arr[0])
		for i in range(1, N - 1):
			Arr[i + 1] += Arr[i]
			ret += abs(Arr[i])
		return ret


class Solution:

	def wineSelling(self, Arr, N):
		ans = 0
		i = 0
		j = 0
		while True:
			while i < N and Arr[i] <= 0:
				i += 1
			while j < N and Arr[j] >= 0:
				j += 1
			if i == N or j == N:
				break
			mini = min(Arr[i], -Arr[j])
			ans += abs(i - j) * mini
			Arr[i] -= mini
			Arr[j] += mini
		return ans


class Solution:

	def wineSelling(self, a, n):
		b = 0
		s = 0
		ans = 0
		while b < n and s < n:
			while a[b] <= 0:
				b += 1
				if b == n:
					return ans
			while a[s] >= 0:
				s += 1
				if s == n:
					return ans
			if abs(a[b]) >= abs(a[s]):
				ans += abs(b - s) * abs(a[s])
				a[b] += a[s]
				a[s] = 0
			else:
				ans += abs(b - s) * a[b]
				a[s] += a[b]
				a[b] = 0
		return ans


class Solution:

	def wineSelling(self, Arr, n):
		(b, s) = (0, 0)
		res = 0
		while b < n and s < n:
			while Arr[b] <= 0:
				b += 1
				if b == n:
					return res
			while Arr[s] >= 0:
				s += 1
				if s == n:
					return res
			if Arr[b] >= abs(Arr[s]):
				res += abs(b - s) * abs(Arr[s])
				Arr[b] += Arr[s]
				Arr[s] = 0
			else:
				res += abs(b - s) * Arr[b]
				Arr[s] += Arr[b]
				Arr[b] = 0
		return res


class Solution:

	def wineSelling(self, Arr, N):
		res = 0
		cur = 0
		for i in Arr:
			cur += i
			res += abs(cur)
		return res


class Solution:

	def wineSelling(self, arr, n):
		bottles = 0
		min_cost = 0
		for i in range(n):
			bottles += arr[i]
			min_cost += abs(bottles)
		return min_cost


class Solution:

	def wineSelling(self, Arr, N):
		buyArr = []
		sellArr = []
		distance = 0
		for i in range(N):
			if Arr[i] > 0:
				buyArr.append([Arr[i], i])
			elif Arr[i] < 0:
				sellArr.append([Arr[i], i])
		i = 0
		j = 0
		while i < len(buyArr) and j < len(sellArr):
			x = min(buyArr[i][0], -sellArr[j][0])
			buyArr[i][0] -= x
			sellArr[j][0] += x
			distance += abs(buyArr[i][1] - sellArr[j][1]) * x
			if buyArr[i][0] == 0:
				i += 1
			elif sellArr[j][0] == 0:
				j += 1
		return distance


class Solution:

	def wineSelling(self, Arr, N):
		(i, j) = (0, 0)
		ans = 0
		while i < N:
			if Arr[i] > 0:
				while j < N and Arr[j] >= 0:
					j += 1
			elif Arr[i] < 0:
				while j < N and Arr[j] <= 0:
					j += 1
			else:
				i += 1
				continue
			temp = Arr[i]
			Arr[i] = abs(Arr[i])
			Arr[j] = abs(Arr[j])
			if Arr[i] > Arr[j]:
				ans += (j - i) * Arr[j]
				Arr[i] = Arr[i] - Arr[j]
				Arr[j] = 0
			else:
				ans += (j - i) * Arr[i]
				Arr[j] = Arr[j] - Arr[i]
				Arr[i] = 0
			if temp < 0:
				Arr[i] = -Arr[i]
			else:
				Arr[j] = -Arr[j]
		return ans


class Solution:

	def wineSelling(self, Arr, N):
		buys = []
		sells = []
		for i in range(N):
			if Arr[i] >= 0:
				sells.append([i, Arr[i]])
			else:
				buys.append([i, -Arr[i]])
		index_s = 0
		index_b = 0
		work = 0
		while index_s < len(sells) and index_b < len(buys):
			distance = abs(buys[index_b][0] - sells[index_s][0])
			bottles = min(buys[index_b][1], sells[index_s][1])
			buys[index_b][1] -= bottles
			sells[index_s][1] -= bottles
			work += distance * bottles
			if buys[index_b][1] == 0:
				index_b += 1
			if sells[index_s][1] == 0:
				index_s += 1
		return work


class Solution:

	def wineSelling(self, a, N):
		sum = 0
		ans = 0
		for x in a:
			ans += abs(sum)
			sum += x
		return ans


from collections import OrderedDict

class Solution:

	def wineSelling(self, Arr, N):
		want_to_buy = OrderedDict()
		want_to_sell = OrderedDict()
		work_needed = 0
		for (index, wineNumb) in enumerate(Arr):
			if wineNumb < 0:
				want_to_sell[index] = abs(wineNumb)
			elif wineNumb > 0:
				want_to_buy[index] = wineNumb
		for (index_to_buy, to_buy) in want_to_buy.items():
			while to_buy > 0:
				(can_sell_index, sell_numb) = next(iter(want_to_sell.items()))
				index_diff = abs(index_to_buy - can_sell_index)
				can_sell_value = self.get_can_sell_value(to_buy, sell_numb)
				if to_buy > can_sell_value:
					want_to_sell.pop(can_sell_index)
					to_buy = to_buy - can_sell_value
				elif sell_numb > can_sell_value:
					to_buy = 0
					new_sell_value = sell_numb - can_sell_value
					want_to_sell[can_sell_index] = new_sell_value
				else:
					want_to_sell.pop(can_sell_index)
					to_buy = 0
				work_needed += index_diff * can_sell_value
		return work_needed

	@staticmethod
	def get_can_sell_value(to_buy, sell_numb):
		diff = sell_numb - to_buy
		return to_buy if diff >= 0 else sell_numb