Given an array arr[ ] of size N having 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 Auxiliary Space : O(N)
Constraints:
1 ≤ N ≤ 10^{6}
0 ≤ A_{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):
		list1 = [-1] * n
		stack = []
		for i in range(n):
			while stack and arr[i] > arr[stack[-1]]:
				index = stack.pop()
				list1[index] = arr[i]
			stack.append(i)
		return list1


class Solution:

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


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):
		stack = []
		ans = []
		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 not stack:
					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):
		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):
		ans = []
		stack = []
		for i in range(len(arr) - 1, -1, -1):
			if len(stack) == 0:
				ans.append(-1)
			elif len(stack) > 0 and stack[-1] > arr[i]:
				ans.append(stack[-1])
			elif len(stack) > 0 and stack[-1] <= arr[i]:
				while len(stack) > 0 and stack[-1] <= arr[i]:
					stack.pop()
				if len(stack) == 0:
					ans.append(-1)
				else:
					ans.append(stack[-1])
			stack.append(arr[i])
		return ans[::-1]


class Solution:

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


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):
		s = []
		for i in range(len(arr)):
			while s and s[-1].get('value') < arr[i]:
				d = s.pop()
				arr[d.get('ind')] = arr[i]
			s.append({'value': arr[i], 'ind': i})
		while s:
			d = s.pop()
			arr[d.get('ind')] = -1
		return arr


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


from collections import deque

class Solution:

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


class Solution:

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


class Solution:

	def nextLargerElement(self, arr, n):
		stack = []
		ans_list = []
		for cur in arr[::-1]:
			while stack and cur >= stack[-1]:
				stack.pop(-1)
			if not stack:
				ans_list.append(-1)
			if stack:
				ans_list.append(stack[-1])
			stack.append(cur)
		return ans_list[::-1]


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


from collections import deque

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def nextLargerElement(self, arr, n):
		stack = [0 for _ in range(n)]
		ix = 0
		for i in range(0, n - 1):
			if arr[i + 1] > arr[i]:
				arr[i] = arr[i + 1]
				while ix > 0 and arr[i + 1] > arr[stack[ix - 1]]:
					arr[stack[ix - 1]] = arr[i + 1]
					ix -= 1
			else:
				stack[ix] = i
				ix += 1
		for i in range(ix):
			arr[stack[i]] = -1
		arr[n - 1] = -1
		return arr


class Solution:

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


class Solution:

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


class Solution:

	def nextLargerElement(self, arr, n):
		v = [-1] * n
		mx = arr[n - 1]
		for i in range(n - 2, -1, -1):
			if arr[i + 1] > arr[i]:
				v[i] = arr[i + 1]
			elif v[i + 1] > arr[i]:
				v[i] = v[i + 1]
			elif mx > arr[i]:
				k = i + 1
				while arr[k] <= arr[i]:
					k += 1
				v[i] = arr[k]
			else:
				v[i] = -1
			mx = max(arr[i], mx)
		return v


class Solution:

	def nextLargerElement(self, temp, n):
		n = len(temp)
		ans = [-1] * n
		st = []
		for i in range(len(temp)):
			while st and st[-1][0] < temp[i]:
				a = st.pop()
				ans[a[1]] = temp[i]
			st.append([temp[i], i])
		return ans