Note: This POTD is a part of Geek Summer Carnival. Solve all POTD consecutively from 5th to 10th April and get a chance to win exclusive discount vouchers on our GfG courses.
Given an array a of length n, find the minimum number of operations required to make it non-increasing. You can select any one of the following operations and preform it any number of times on an array element.
	increment the array element by 1.
	decrement the array element by 1. 
Example 1:
Input:
N = 4 
array = {3, 1, 2, 1}
Output: 1
Explanation: 
Decrement array[2] by 1. 
New array becomes {3,1,1,1} which is non-increasing. 
Therefore, only 1 step is required. 
Example 2:
Input:
N = 4 
array = {3, 1, 5, 1}
Output: 4
Your Task:
You don't need to read input or print anything. Complete the function minOperations() that takes n and array a as input parameters and returns the minimum number of operations required. 
Expected time complexity: O(nlogn)
Expected space complexity: O(n)
Constraints:
1 <= n <= 10^4
1 <= a[i] <= 10^4

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def minOperations(self,a,n):

        # code here





Solutions:
import heapq

class Solution:

	def minOperations(self, a, n):
		operations = 0
		minheap = []
		diff = 0
		for i in range(0, n):
			if minheap and a[i] > minheap[0]:
				diff = a[i] - minheap[0]
				operations = operations + diff
				heapq.heappop(minheap)
				heapq.heappush(minheap, a[i])
			heapq.heappush(minheap, a[i])
		return operations


import heapq

class Solution:

	def minOperations(self, a, n):
		pq = []
		ans = 0
		for elem in a:
			if len(pq) > 0 and pq[0] < elem:
				ans += elem - pq[0]
				heapq.heapreplace(pq, elem)
			heapq.heappush(pq, elem)
		return ans


class Solution:

	def minOperations(self, a, n):
		import heapq
		hp = []
		ret = 0
		heapq.heapify(hp)
		for i in range(n):
			if hp and hp[0] < a[i]:
				d = a[i] - heapq.heappop(hp)
				ret += d
				heapq.heappush(hp, a[i])
			heapq.heappush(hp, a[i])
		return ret


from heapq import heapify, heappush, heappop

class Solution:

	def minOperations(self, a, n):
		Sum = 0
		heap = []
		heapify(heap)
		for i in range(n):
			if len(heap) and heap[0] < a[i]:
				diff = a[i] - heappop(heap)
				Sum += diff
				heappush(heap, a[i])
			heappush(heap, a[i])
		return Sum


import heapq

class Solution:

	def minOperations(self, a, n):
		h = []
		heapq.heapify(h)
		res = 0
		for i in range(len(a)):
			if len(h) != 0 and h[0] < a[i]:
				res += a[i] - h[0]
				heapq.heappop(h)
				heapq.heappush(h, a[i])
			heapq.heappush(h, a[i])
		return res


import heapq

class Solution:

	def minOperations(self, a, n):
		pq = []
		steps = 0
		for i in range(n):
			if pq and pq[0] < a[i]:
				steps += a[i] - pq[0]
				heapq.heappush(pq, a[i])
				heapq.heappop(pq)
			heapq.heappush(pq, a[i])
		return steps


import heapq

class Solution:

	def minOperations(self, a, n):
		data = []
		res = 0
		for i in range(n):
			if data and data[0] < a[i]:
				res += a[i] - data[0]
				heapq.heappush(data, a[i])
				heapq.heappop(data)
			heapq.heappush(data, a[i])
		return res


import heapq

class Solution:

	def minOperations(self, a, n):
		heap = []
		count = 0
		for i in range(n):
			if heap and heap[0] < a[i]:
				count += a[i] - heap[0]
				heapq.heappush(heap, a[i])
				heapq.heappop(heap)
			heapq.heappush(heap, a[i])
		return count


import heapq

class Solution:

	def minOperations(self, a, n):
		count = 0
		b = []
		for i in range(n):
			if len(b) != 0 and b[0] < a[i]:
				x = b[0]
				count += abs(x - a[i])
				heapq.heappop(b)
				heapq.heappush(b, a[i])
			heapq.heappush(b, a[i])
		return count


import heapq

class Solution:

	def minOperations(self, a, n):
		pq = [a[0]]
		count = 0
		for i in range(1, n):
			if a[i] > pq[0]:
				count += a[i] - pq[0]
				heapq.heappop(pq)
				heapq.heappush(pq, a[i])
			heapq.heappush(pq, a[i])
		return count


import heapq

class Solution:

	def minOperations(self, a, n):
		d = []
		res = 0
		for x in range(n):
			if d and d[0] < a[x]:
				res += a[x] - d[0]
				heapq.heappush(d, a[x])
				heapq.heappop(d)
			heapq.heappush(d, a[x])
		return res


import heapq

class Solution:

	def minOperations(self, a, n):
		heap = [a[0]]
		ops = 0
		for num in a[1:]:
			if heap and heap[0] < num:
				ops += num - heapq.heappop(heap)
				heapq.heappush(heap, num)
			heapq.heappush(heap, num)
		return ops


from heapq import *

class Solution:

	def minOperations(self, a, n):
		q = []
		c = 0
		for v in a:
			if not q or q[0] >= v:
				heappush(q, v)
			else:
				c += v - heappop(q)
				heappush(q, v)
				heappush(q, v)
		return c


import heapq

class Solution:

	def minOperations(self, a, n):
		ans = 0
		heap = []
		heapq.heapify(heap)
		for i in range(n - 1, -1, -1):
			if heap and -1 * heap[0] > a[i]:
				ans += abs(a[i] - -1 * heap[0])
				heapq.heappop(heap)
				heapq.heappush(heap, -1 * a[i])
			heapq.heappush(heap, -1 * a[i])
		return ans


import heapq

class Solution:

	def minOperations(self, a, n):
		d = []
		r = 0
		for i in range(n):
			if d and d[0] < a[i]:
				r = r + a[i] - d[0]
				heapq.heappush(d, a[i])
				heapq.heappop(d)
			heapq.heappush(d, a[i])
		return r


from heapq import heapify, heappush, heappop

class Solution:

	def minOperations(self, a, n):
		heap = []
		su = 0
		for i in range(n):
			if heap and heap[0] < a[i]:
				su += a[i] - heap[0]
				heappush(heap, a[i])
				heappop(heap)
			heappush(heap, a[i])
		return su


import heapq

class Solution:

	def minOperations(self, arr, n):
		ans = 0
		pq = []
		heapq.heapify(pq)
		for i in range(n):
			mini = 0
			if pq and pq[0] < arr[i]:
				mini = heapq.heappop(pq)
				ans += arr[i] - mini
				heapq.heappush(pq, arr[i])
			heapq.heappush(pq, arr[i])
		return ans


import heapq

class Solution:

	def minOperations(self, a, n):
		p = []
		re = 0
		for i in range(n):
			if p and p[0] < a[i]:
				l = heapq.heappop(p)
				re += a[i] - l
				heapq.heappush(p, a[i])
			heapq.heappush(p, a[i])
		return re


import heapq
from queue import PriorityQueue

class Solution:

	def minOperations(self, a, n):
		min_heap = []
		sum_ = 0
		for i in range(n):
			if len(min_heap) > 0 and a[i] > min_heap[0]:
				val = heapq.heappop(min_heap)
				diff = a[i] - val
				sum_ += diff
				heapq.heappush(min_heap, a[i])
			heapq.heappush(min_heap, a[i])
		return sum_

	def minOperations1(self, a, n):
		ss = 0
		pq = PriorityQueue()
		for i in range(n):
			tmp = 0
			if not pq.empty():
				tmp = pq.get()
				pq.put(tmp)
			if not pq.empty() and tmp < a[i]:
				dif = a[i] - tmp
				ss += dif
				pq.get()
				pq.put(a[i])
			pq.put(a[i])
		return ss


import heapq

class Solution:

	def minOperations(self, a, n):
		res = 0
		pq = []
		heapq.heapify(pq)
		for i in range(n):
			if pq and pq[0] < a[i]:
				diff = a[i] - pq[0]
				heapq.heappop(pq)
				heapq.heappush(pq, a[i])
				res += diff
			heapq.heappush(pq, a[i])
		return res


import heapq

class Solution:

	def minOperations(self, a, n):
		op = 0
		mh = []
		for i in range(n):
			if mh and a[i] > mh[0]:
				dif = a[i] - mh[0]
				op += dif
				heapq.heappop(mh)
				heapq.heappush(mh, a[i])
				heapq.heappush(mh, a[i])
			else:
				heapq.heappush(mh, a[i])
		return op


import heapq

class Solution:

	def minOperations(self, a, n):
		h = []
		ans = 0
		for i in a:
			if h and h[0] < i:
				diff = i - h[0]
				ans += diff
				heapq.heappop(h)
				heapq.heappush(h, i)
			heapq.heappush(h, i)
		return ans


from heapq import *

class Solution:

	def minOperations(self, a, n):
		(res, ans) = ([], 0)
		for i in range(n):
			if res:
				q = heappop(res)
				if q < a[i]:
					ans += a[i] - q
					heappush(res, a[i])
				else:
					heappush(res, q)
			heappush(res, a[i])
		return ans


from heapq import heapify, heappush, heappop

class Solution:

	def minOperations(self, arr, n):
		heap = []
		steps = 0
		for i in range(len(arr)):
			if heap and heap[0] < arr[i]:
				steps += arr[i] - heap[0]
				heappush(heap, arr[i])
				heappop(heap)
			heappush(heap, arr[i])
		return steps


import heapq as hq

class Solution:

	def minOperations(self, a, n):
		list = []
		count = 0
		for i in range(n):
			if list and list[0] < a[i]:
				count = count + a[i] - list[0]
				hq.heappush(list, a[i])
				hq.heappop(list)
			hq.heappush(list, a[i])
		return count


import heapq

class Solution:

	def minOperations(self, A, N):
		data = []
		result = 0
		for i in range(N):
			if data and data[0] < A[i]:
				result += A[i] - data[0]
				heapq.heappush(data, A[i])
				heapq.heappop(data)
			heapq.heappush(data, A[i])
		return result


import heapq

class Solution:

	def minOperations(self, a, n):
		data = []
		res = 0
		for i in range(n):
			if data and data[0] < a[i]:
				res += a[i] - data[0]
				heapq.heappush(data, a[i])
				heapq.heappop(data)
			heapq.heappush(data, a[i])
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		obj = Solution()
		print(obj.minOperations(a, n))


import heapq

class Solution:

	def minOperations(self, a, n):
		h = []
		c = 0
		for i in range(n):
			if h and h[0] < a[i]:
				c += a[i] - h[0]
				heapq.heappush(h, a[i])
				heapq.heappop(h)
			heapq.heappush(h, a[i])
		return c