Given an array arr[ ] of size n having distinct elements, the task is to find the next greater element for each element of the array in order of their appearance in the array.
Next greater element of an element in the array is the nearest element on the right which is greater than the current element.
If there does not exist next greater of current element, then next greater element for current element is -1. For example, next greater of the last element is always -1.
Example 1:
Input: 
n = 4, arr[] = [1 3 2 4]
Output:
3 4 4 -1
Explanation:
In the array, the next larger element 
to 1 is 3, 3 is 4, 2 is 4 and for 4? 
since it doesn't exist, it is -1.
Example 2:
Input: 
n = 5, arr[] = [6 8 0 1 3]
Output:
8 -1 1 3 -1
Explanation:
In the array, the next larger element to 
6 is 8, for 8 there is no larger elements 
hence it is -1, for 0 it is 1, for 1 it 
is 3 and then for 3 there is no larger 
element on right and hence -1.
Your Task:
This is a function problem. You only need to complete the function nextLargerElement() that takes list of integers arr[ ] and n as input parameters and returns list of integers of length N denoting the next greater elements for all the corresponding elements in the input array.
Expected Time Complexity : O(n)
Expected Auxilliary Space : O(n)
Constraints:
1 ≤ n ≤ 10^{6}
0 ≤ arr_{i} ≤ 10^{18}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3





class Solution:

    def nextLargerElement(self,arr,n):

        #code here

Solutions:
class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		res = [-1 for _ in range(n)]
		for i in range(n - 1, -1, -1):
			while stack != [] and stack[-1] <= arr[i]:
				stack.pop()
			if stack == []:
				res[i] = -1
			else:
				res[i] = stack[-1]
			stack.append(arr[i])
		return res


class Solution:

	def nextLargerElement(self, arr, n):
		ans = []
		stack = []
		for i in range(n - 1, -1, -1):
			if not stack:
				ans.append(-1)
			elif stack[-1] > arr[i]:
				ans.append(stack[-1])
			elif stack[-1] <= arr[i]:
				while stack and stack[-1] <= arr[i]:
					stack.pop()
				if len(stack) == 0:
					ans.append(-1)
				else:
					ans.append(stack[-1])
			stack.append(arr[i])
		realans = []
		while ans:
			realans.append(ans.pop())
		return realans


class Solution:

	def nextLargerElement(self, arr, n):
		st = [arr[-1]]
		ans = [-1 for i in range(n)]
		for i in range(n - 2, -1, -1):
			if arr[i] >= st[-1]:
				while len(st) > 0 and arr[i] >= st[-1]:
					st.pop()
				if len(st) != 0:
					ans[i] = st[-1]
				st.append(arr[i])
			else:
				ans[i] = st[-1]
				st.append(arr[i])
		return ans


class Solution:

	def nextLargerElement(self, arr, n):
		ans = []
		st = []
		for el in arr[::-1]:
			flag = True
			while len(st) != 0:
				if st[-1] <= el:
					st.pop()
				else:
					ans.append(st[-1])
					flag = False
					break
			if flag:
				ans.append(-1)
			st.append(el)
		return ans[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		st = []
		ans = [-1] * n
		for i in range(n - 1, -1, -1):
			while st and arr[i] >= st[-1]:
				st.pop()
			if st:
				ans[i] = st[-1]
			st.append(arr[i])
		return ans


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		res = [-1] * n
		for (i, j) in enumerate(arr):
			while stack and stack[-1][1] < j:
				(ind, val) = stack.pop()
				res[ind] = j
			stack.append([i, j])
		return res


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		ans = []
		ans.append(-1)
		i = n - 2
		stack.append(arr[-1])
		while i >= 0:
			if stack[-1] <= arr[i]:
				while len(stack) > 0 and stack[-1] <= arr[i]:
					stack.pop()
				if len(stack) == 0:
					ans.append(-1)
					stack.append(arr[i])
				else:
					ans.append(stack[-1])
					stack.append(arr[i])
			else:
				ans.append(stack[-1])
				stack.append(arr[i])
			i -= 1
		ans.reverse()
		return ans


class Solution:
	from collections import deque

	def nextLargerElement(self, arr, n):
		from collections import deque
		s = deque([])
		ans = []
		for i in range(n - 1, -1, -1):
			if not s:
				ans.append(-1)
			elif s and s[-1] > arr[i]:
				ans.append(s[-1])
			elif s and s[-1] < arr[i]:
				while s and s[-1] < arr[i]:
					s.pop()
				if not s:
					ans.append(-1)
				else:
					ans.append(s[-1])
			s.append(arr[i])
		return ans[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		nge = [-1] * n
		stack = []
		stack.append(0)
		for i in range(1, n):
			while stack and arr[i] > arr[stack[-1]]:
				nge[stack.pop()] = arr[i]
			stack.append(i)
		return nge


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		result = []
		for i in range(n - 1, -1, -1):
			cur = arr[i]
			while len(stack) > 0 and stack[-1] <= cur:
				stack.pop()
			if len(stack) > 0:
				result.append(stack[-1])
			else:
				result.append(-1)
			stack.append(cur)
		return result[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		s = []
		ans = []
		for i in arr[::-1]:
			while len(s) != 0 and i >= s[-1]:
				s.pop()
			if len(s) == 0:
				ans.append(-1)
			else:
				ans.append(s[-1])
			s.append(i)
		return ans[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		result = [-1] * n
		stack = []
		for i in range(n):
			while stack and arr[i] > arr[stack[-1]]:
				index = stack.pop()
				result[index] = arr[i]
			stack.append(i)
		return result


class Solution:

	def nextLargerElement(self, arr, n):
		arr = arr[::-1]
		stack = []
		stack.append(arr[0])
		returnee = [-1]
		for i in range(1, n):
			try:
				while stack[-1] <= arr[i]:
					stack.pop()
				returnee.append(stack[-1])
				stack.append(arr[i])
			except:
				returnee.append(-1)
				stack.append(arr[i])
		return returnee[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		st = []
		res = [0] * n
		for i in range(n - 1, -1, -1):
			while st and st[-1] <= arr[i]:
				st.pop()
			if st:
				res[i] = st[-1]
			else:
				res[i] = -1
			st.append(arr[i])
		return res


class Solution:

	def nextLargerElement(self, arr, n):
		a = []
		stack = []
		for i in arr[::-1]:
			if not stack:
				a.append(-1)
			elif stack and stack[-1] > i:
				a.append(stack[-1])
			elif stack and stack[-1] <= i:
				while stack and stack[-1] <= i:
					stack.pop()
				if not stack:
					a.append(-1)
				else:
					a.append(stack[-1])
			stack.append(i)
		return a[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		s = []
		x = [-1] * n
		for i in range(n):
			while len(s) > 0 and arr[s[-1]] < arr[i]:
				x[s[-1]] = arr[i]
				s.pop()
			s.append(i)
		return x


from collections import deque

class Solution:

	def nextLargerElement(self, arr, n):
		stack = deque()
		ans = [-1] * n
		for i in range(n - 1, -1, -1):
			while stack and arr[i] >= stack[-1]:
				stack.pop()
			if len(stack) == 0:
				ans[i] = -1
			else:
				ans[i] = stack[-1]
			stack.append(arr[i])
		return ans


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		list = []
		stack.append(a[n - 1])
		list.append('-1')
		for i in range(n - 2, -1, -1):
			while len(stack) > 0 and stack[-1] <= a[i]:
				stack.pop()
			if len(stack) == 0:
				list.append('-1')
			else:
				list.append(stack[-1])
			stack.append(arr[i])
		list.reverse()
		return list


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		ans = [-1 for _ in range(n)]
		for (i, num) in enumerate(arr):
			if not stack:
				stack.append(i)
			else:
				while stack and num > arr[stack[-1]]:
					index = stack.pop()
					ans[index] = num
				stack.append(i)
		return ans


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		i = 0
		ans = [-1 for i in arr]
		while i < n:
			if stack == []:
				stack.append(i)
			elif arr[stack[-1]] >= arr[i]:
				stack.append(i)
			elif arr[stack[-1]] < arr[i]:
				while stack and arr[stack[-1]] < arr[i]:
					x = stack.pop()
					ans[x] = arr[i]
				stack.append(i)
			i += 1
		return ans


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		nge = []
		for i in reversed(range(len(arr))):
			while len(stack) > 0 and stack[-1] <= arr[i]:
				stack.pop()
			if len(stack) < 1:
				nge.append(-1)
			else:
				nge.append(stack[-1])
			stack.append(arr[i])
		return nge[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		stack = [-1]
		res = []
		for i in range(n - 1, -1, -1):
			while len(stack) > 1 and arr[i] >= stack[-1]:
				stack.pop()
			res.append(stack[-1])
			stack.append(arr[i])
		for i in range(n):
			arr[i] = res[i]
		return arr[::-1]


class Solution:

	def nextLargerElement(self, a, n):
		stk = []
		res = []
		for i in range(n - 1, -1, -1):
			while len(stk) != 0 and a[i] >= stk[-1]:
				stk.pop()
			if len(stk) == 0:
				res.append(-1)
			else:
				res.append(stk[-1])
			stk.append(a[i])
		return res[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		output = [-1] * n
		stack = []
		for i in range(n):
			while len(stack) != 0 and arr[stack[-1]] < arr[i]:
				index = stack.pop(-1)
				output[index] = arr[i]
			stack.append(i)
		output[-1] = -1
		return output


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		res = []
		for i in range(len(arr) - 1, -1, -1):
			if not stack:
				res.append(-1)
			elif stack and arr[i] < stack[-1]:
				res.append(stack[-1])
			else:
				while stack and stack[-1] < arr[i]:
					stack.pop()
				if stack:
					res.append(stack[-1])
				else:
					res.append(-1)
			stack.append(arr[i])
		res.reverse()
		return res


class Solution:

	def nextLargerElement(self, arr, n):
		r = [-1]
		s = [arr[-1]]
		for i in range(n - 2, -1, -1):
			f = 0
			while len(s) != 0:
				if s[-1] > arr[i]:
					f = 1
					r.append(s[-1])
					break
				s.pop(-1)
			if not f:
				r.append(-1)
			s.append(arr[i])
		return r[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		v = []
		st = []
		st.append(arr[n - 1])
		v.append(-1)
		for i in range(n - 2, -1, -1):
			while st and st[-1] <= arr[i]:
				st.pop()
			if not st:
				v.append(-1)
			else:
				v.append(st[-1])
			st.append(arr[i])
		return v[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		l = []
		l1 = []
		for i in arr[::-1]:
			while len(l1) > 0 and l1[len(l1) - 1] <= i:
				l1.pop()
			if len(l1) == 0:
				l1.append(i)
				l.append(-1)
				continue
			l.append(l1[len(l1) - 1])
			l1.append(i)
		return l[::-1]


import math

class Solution:

	def nextLargerElement(self, arr, n):
		stack = [math.inf]
		ans = [] * len(arr)
		for i in range(len(arr) - 1, -1, -1):
			while arr[i] >= stack[-1]:
				stack.pop()
			ans.append(stack[-1])
			stack.append(arr[i])
		for i in range(len(ans)):
			if ans[i] == math.inf:
				ans[i] = -1
		return ans[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		z = []
		for ele in arr[::-1]:
			while len(stack) != 0 and ele >= stack[-1]:
				stack.pop()
			if len(stack) != 0:
				z.append(stack[-1])
			else:
				z.append(-1)
			stack.append(ele)
		return z[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		li = []
		for i in range(n - 1, -1, -1):
			while li and li[-1] < arr[i]:
				li.pop()
			curr = arr[i]
			if li:
				arr[i] = li[-1]
			else:
				arr[i] = -1
			li.append(curr)
		return arr


from collections import deque

class Solution:

	def nextLargerElement(self, arr, n):
		answer = list()
		tmp_list = list()
		for i in range(len(arr) - 1, -1, -1):
			if len(tmp_list) < 1:
				answer.append(-1)
				tmp_list.append(arr[i])
			elif arr[i] < tmp_list[-1]:
				answer.append(tmp_list[-1])
				tmp_list.append(arr[i])
			else:
				while len(tmp_list) > 0:
					if arr[i] < tmp_list[-1]:
						answer.append(tmp_list[-1])
						break
					else:
						tmp_list.pop()
				if len(tmp_list) < 1:
					answer.append(-1)
				tmp_list.append(arr[i])
		answer.reverse()
		return answer


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		result = []
		stack.append('$')
		for i in range(n - 1, -1, -1):
			if stack[-1] == '$':
				result.append(-1)
			elif stack[-1] != '$' and stack[-1] > arr[i]:
				result.append(stack[-1])
			elif stack[-1] != '$' and stack[-1] <= arr[i]:
				while stack[-1] != '$' and stack[-1] <= arr[i]:
					stack.pop()
				if stack[-1] != '$':
					result.append(stack[-1])
				else:
					result.append(-1)
			stack.append(arr[i])
		result.reverse()
		return result


class Solution:

	def nextLargerElement(self, arr, n):
		a = []
		st = [-1]
		for i in range(n - 1, -1, -1):
			while st[-1] != -1 and st[-1] < arr[i]:
				st.pop()
			a.append(st[-1])
			st.append(arr[i])
		a.reverse()
		return a


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		opt = [-1] * n
		i = 0
		while i < n:
			if not stack:
				stack.append(i)
			elif arr[stack[-1]] >= arr[i]:
				stack.append(i)
			while stack and arr[stack[-1]] < arr[i]:
				a = stack.pop()
				opt[a] = arr[i]
				i -= 1
			i += 1
		return opt


class Solution:

	def nextLargerElement(self, arr, n):
		arr.reverse()
		stack = [0] * n
		top = -1
		ans = []
		for i in range(0, n):
			while arr[i] >= stack[top] and top != -1:
				top -= 1
			if top == -1:
				ans.append(-1)
			else:
				ans.append(stack[top])
			top += 1
			stack[top] = arr[i]
		ans.reverse()
		return ans


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		new = [0] * n
		for i in range(n - 1, -1, -1):
			ans = -1
			cur = arr[i]
			while stack and stack[-1] < cur:
				stack.pop()
			if stack:
				ans = stack[-1]
			new[i] = ans
			stack.append(cur)
		return new


class Solution:

	def nextLargerElement(self, A, n):
		stack = []
		ans = [-1] * n
		for i in range(n - 1, -1, -1):
			while stack and stack[-1] <= A[i]:
				stack.pop()
			if stack:
				ans[i] = stack[-1]
			stack.append(A[i])
		return ans


class Solution:

	def nextLargerElement(self, arr, n):
		ans = [-1]
		last = [arr[-1]]
		arr = arr[:-1]
		for num in arr[::-1]:
			if last:
				flag = True
				while last:
					if num < last[-1]:
						ans.append(last[-1])
						last.append(num)
						flag = False
						break
					else:
						last.pop()
				if flag:
					ans.append(-1)
					last.append(num)
			else:
				ans.append(-1)
				last.append(num)
		return ans[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		ans = []
		st = []
		i = n - 1
		while i > -1:
			if len(st) == 0:
				ans.append(-1)
				st.append(arr[i])
				i -= 1
				continue
			if st[-1] > arr[i]:
				ans.append(st[-1])
				st.append(arr[i])
				i -= 1
			elif st[-1] <= arr[i]:
				st.pop()
		return ans[::-1]


class Solution:

	def nextLargerElement(self, arr, n):
		ans = [-1] * len(arr)
		stack = []
		for (i, num) in enumerate(arr):
			while stack and arr[stack[-1]] < num:
				ans[stack.pop()] = num
			stack.append(i)
		return ans


class Solution:

	def nextLargerElement(self, arr, n):
		ans = list()
		stack = list()
		for i in arr[::-1]:
			while stack and stack[-1] <= i:
				stack.pop()
			if not stack:
				ans.append(-1)
			else:
				ans.append(stack[-1])
			stack.append(i)
		return ans[::-1]