You are given an array Arr of size N. Replace every element with the next greatest element (greatest element on its right side) in the array. Also, since there is no element next to the last element, replace it with -1.
Example 1:
Input:
N = 6
Arr[] = {16, 17, 4, 3, 5, 2}
Output:
17 5 5 5 2 -1
Explanation: For 16 the greatest element 
on its right is 17. For 17 it's 5. 
For 4 it's 5. For 3 it's 5. For 5 it's 2. 
For 2 it's -1(no element to its right). 
So the answer is 17 5 5 5 2 -1
Example 2:
Input:
N = 4
Arr[] = {2, 3, 1, 9}
Output:
9 9 9 -1
Explanation: For each element except 9 the
greatest element on its right is 9.
So the answer is 9 9 9 -1
Your Task:  
You don't need to read input or print anything. Your task is to complete the function nextGreatest() which takes the array of integers arr and n as parameters and returns void. You need to change the array itself.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= Arr_{i} <= 10^{6}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3
class Solution:

	def nextGreatest(self,arr, n):
		# code  here

Solutions:
class Solution:

	def nextGreatest(self, arr, n):
		for i in range(n - 1, -1, -1):
			temp = arr[i]
			arr[i] = arr[n - 1]
			if temp >= arr[n - 1]:
				arr[n - 1] = temp
		arr[n - 1] = -1
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		maxx = arr[-1]
		arr[-1] = -1
		for i in range(n - 2, -1, -1):
			temp = arr[i]
			arr[i] = maxx
			maxx = max(temp, maxx)
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		m = arr[n - 1]
		arr[n - 1] = -1
		for i in range(n - 2, -1, -1):
			t = arr[i]
			arr[i] = m
			if t > m:
				m = t


class Solution:

	def nextGreatest(self, arr, n):
		max_right = -1
		for i in range(n - 1, -1, -1):
			temp = arr[i]
			arr[i] = max_right
			max_right = max(max_right, temp)
		arr[-1] = -1


class Solution:

	def nextGreatest(self, arr, n):
		cmax = -1
		for i in range(n - 1, -1, -1):
			x = cmax
			if arr[i] > cmax:
				cmax = arr[i]
			arr[i] = x
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		st = [-1]
		res = []
		for i in range(n - 1, -1, -1):
			res.append(st[-1])
			if arr[i] > st[-1]:
				st.append(arr[i])
		res = list(reversed(res))
		for i in range(n):
			arr[i] = res[i]


class Solution:

	def nextGreatest(self, arr, n):
		max_value = -1
		for i in range(n - 1, -1, -1):
			temp = arr[i]
			arr[i] = max_value
			max_value = max(max_value, temp)
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		max_n = arr[-1]
		for i in range(n - 2, -1, -1):
			max2 = arr[i]
			arr[i] = max_n
			if max2 > max_n:
				max_n = max2
		arr[-1] = -1
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		maxx = arr[n - 1]
		for i in range(n - 2, -1, -1):
			temp = arr[i]
			arr[i] = maxx
			if temp >= maxx:
				maxx = temp
		arr[n - 1] = -1


class Solution:

	def nextGreatest(self, arr, n):
		max_so_far = -1
		for i in range(len(arr) - 1, -1, -1):
			temp = arr[i]
			arr[i] = max_so_far
			max_so_far = max(max_so_far, temp)
		arr[-1] = -1


class Solution:

	def nextGreatest(self, arr, n):
		n = len(arr)
		max_element = -1
		for i in range(n - 1, -1, -1):
			temp = arr[i]
			arr[i] = max_element
			max_element = max(max_element, temp)
		arr[n - 1] = -1
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		x = -1
		for i in range(n):
			if x == -1:
				x = arr[n - i - 1]
				arr[n - i - 1] = -1
			elif x > arr[n - i - 1]:
				arr[n - i - 1] = x
			else:
				temp = x
				x = arr[n - i - 1]
				arr[n - i - 1] = temp


class Solution:

	def nextGreatest(self, arr, n):
		curr = arr[n - 1]
		for i in range(n - 2, -1, -1):
			if arr[i] < curr:
				arr[i] = curr
			else:
				(arr[i], curr) = (curr, arr[i])
		arr[-1] = -1


class Solution:

	def nextGreatest(self, arr, n):
		for i in range(n, 1, -1):
			if arr[i - 1] > arr[i - 2]:
				arr[i - 2] = arr[i - 1]
		arr.pop(0)
		arr.insert(n, -1)
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		li = [0] * n
		maxs = arr[-1]
		for i in range(n - 2, -1, -1):
			li[i] = maxs
			if maxs < arr[i]:
				maxs = arr[i]
		li[-1] = -1
		arr[:] = li[:]


class Solution:

	def nextGreatest(self, arr, n):
		b = arr[n - 1]
		n -= 2
		while n > -1:
			if arr[n] > b:
				(b, arr[n]) = (arr[n], b)
			else:
				arr[n] = b
			n -= 1
		arr[-1] = -1
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		maax = arr[n - 1]
		arr[n - 1] = -1
		for i in range(n - 2, -1, -1):
			temp = arr[i]
			arr[i] = maax
			maax = max(maax, temp)


class Solution:

	def nextGreatest(self, arr, n):
		arr.append(-1)
		for i in range(n, 1, -1):
			if arr[i] < arr[i - 1]:
				pass
			else:
				arr[i - 1] = arr[i]
		arr.pop(0)


class Solution:

	def nextGreatest(self, arr, n):
		n = len(arr)
		max_right = arr[n - 1]
		arr[n - 1] = -1
		for i in range(n - 2, -1, -1):
			temp = arr[i]
			arr[i] = max_right
			if max_right < temp:
				max_right = temp


class Solution:

	def nextGreatest(self, Arr, N):
		m = Arr[N - 1]
		Arr[N - 1] = -1
		for i in range(N - 2, -1, -1):
			t = Arr[i]
			Arr[i] = m
			if t > m:
				m = t
		return Arr


class Solution:

	def nextGreatest(self, Arr, N):
		max_so_far = Arr[N - 1]
		Arr[N - 1] = -1
		for i in range(N - 2, -1, -1):
			temp = Arr[i]
			Arr[i] = max_so_far
			if temp > max_so_far:
				max_so_far = temp
		return Arr


class Solution:

	def nextGreatest(self, arr, n):
		rightMax = -1
		for i in range(len(arr) - 1, -1, -1):
			curMax = max(rightMax, arr[i])
			arr[i] = rightMax
			rightMax = curMax
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		max = arr[n - 1]
		for i in range(n - 2, -1, -1):
			check = arr[i]
			arr[i] = max
			if check > max:
				max = check
		arr[n - 1] = -1


class Solution:

	def nextGreatest(self, arr, n):
		max = arr[n - 1]
		for i in range(n - 1, -1, -1):
			t = arr[i]
			arr[i] = max
			if t > max:
				max = t
			arr[n - 1] = -1


class Solution:

	def nextGreatest(self, arr, n):
		(max_val, j, arr[-1]) = (arr[n - 1], n - 2, -1)
		while j >= 0:
			(temp, arr[j]) = (arr[j], max_val)
			(max_val, j) = (max(max_val, temp), j - 1)


import heapq

class Solution:

	def nextGreatest(self, arr, n):
		q = []
		heapq.heappush(q, 1)
		for i in range(n - 1, 0, -1):
			ans = -q[0]
			heapq.heappush(q, -arr[i])
			arr[i] = ans
		arr[0] = -q[0]


class Solution:

	def nextGreatest(self, arr, n):
		maxVal = -1
		temp = 0
		for i in range(n - 1, -1, -1):
			if i == n - 1:
				temp = arr[i]
				arr[i] = -1
				maxVal = max(temp, maxVal)
				continue
			temp = arr[i]
			arr[i] = maxVal
			maxVal = max(temp, maxVal)


class Solution:

	def nextGreatest(self, arr, n):
		max = arr[-1]
		for i in range(len(arr) - 2, -1, -1):
			temp = arr[i]
			arr[i] = max
			if temp >= max:
				max = temp
		arr[-1] = -1
		return arr


import math

class Solution:

	def nextGreatest(self, arr, n):
		maximum = -math.inf
		value = arr[n - 1]
		for i in range(n - 2, -1, -1):
			item = max(value, maximum)
			maximum = item
			value = arr[i]
			arr[i] = item
		arr[n - 1] = -1


class Solution:

	def nextGreatest(self, arr, n):
		ans = arr[n - 1]
		for i in range(n - 2, -1, -1):
			a = arr[i]
			arr[i] = ans
			if a >= ans:
				ans = a
		arr[n - 1] = -1
		return arr[i]


class Solution:

	def nextGreatest(self, arr, n):
		m = max(arr[1:])
		for i in range(n - 1):
			if arr[i] != m:
				arr[i] = m
			else:
				m = max(arr[i + 1:])
				arr[i] = m
		arr[n - 1] = -1
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		temp1 = arr[-1]
		arr[-1] = -1
		temp = max(arr[-2], temp1)
		arr[-2] = temp1
		for i in range(n - 3, -1, -1):
			v = arr[i]
			arr[i] = temp
			temp = max(temp, v)
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		i = len(arr) - 1
		max = -1
		while i >= 0:
			temp = arr[i]
			arr[i] = max
			if temp > max:
				max = temp
			i -= 1


class Solution:

	def nextGreatest(self, arr, n):
		m = arr[n - 1]
		arr[n - 1] = -1
		for i in range(n - 2, -1, -1):
			x = arr[i]
			arr[i] = m
			if x > m:
				m = x
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		gtr = -1
		temp = 0
		for i in range(n - 1, -1, -1):
			temp = arr[i]
			arr[i] = gtr
			gtr = max(gtr, temp)
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		fun(arr)

def fun(lst):
	if len(lst) == 1:
		lst[len(lst) - 1] = -1
		return
	temp = lst[len(lst) - 1]
	for i in range(len(lst) - 2, -1, -1):
		kemp = lst[i]
		lst[i] = temp
		if kemp > temp:
			temp = kemp
	lst[len(lst) - 1] = -1


class Solution:

	def nextGreatest(self, arr, n):
		size = len(arr)
		max_from_right = arr[size - 1]
		arr[size - 1] = -1
		for i in range(size - 2, -1, -1):
			temp = arr[i]
			arr[i] = max_from_right
			if max_from_right < temp:
				max_from_right = temp


class Solution:

	def nextGreatest(self, arr, n):
		x = arr[-1]
		for i in range(n - 1, -1, -1):
			y = max(arr[i], x)
			arr[i] = x
			x = y
		arr[-1] = -1
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		curr = arr[-1]
		rmax = -1
		arr[-1] = -1
		i = n - 2
		while i >= 0:
			if curr > rmax:
				rmax = curr
			curr = arr[i]
			arr[i] = rmax
			i -= 1


class Solution:

	def nextGreatest(self, arr, n):
		a = []
		a.append(-1)
		max = arr[-1]
		i = n - 2
		while i >= 0:
			a.append(max)
			if arr[i] > max:
				max = arr[i]
			i -= 1
		arr.clear()
		arr.extend(a[::-1])


class Solution:

	def nextGreatest(self, arr, n):
		maxx = -1
		ans = []
		for i in range(n - 1, -1, -1):
			ans.append(maxx)
			maxx = max(maxx, arr[i])
		for i in range(n):
			arr[i] = ans[n - i - 1]
		return arr


class Solution:

	def nextGreatest(self, arr, n):
		aux = [0] * n
		aux[-1] = -1
		mx = -1
		for i in range(len(arr) - 1, 0, -1):
			if arr[i] > mx:
				mx = arr[i]
			aux[i - 1] = mx
		for i in range(len(aux)):
			arr[i] = aux[i]