Professor X wants his students to help each other in the chemistry lab. He suggests that every student should help out a classmate who scored less marks than him in chemistry and whose roll number appears after him. But the students are lazy and they don't want to search too far. They each pick the first roll number after them that fits the criteria. Find the marks of the classmate that each student picks.
Note: one student may be selected by multiple classmates.
Example 1:
Input: N = 5, arr[] = {3, 8, 5, 2, 25}
Output: 2 5 2 -1 -1
Explanation: 
1. Roll number 1 has 3 marks. The first person 
who has less marks than him is roll number 4, 
who has 2 marks.
2. Roll number 2 has 8 marks, he helps student 
with 5 marks.
3. Roll number 3 has 5 marks, he helps student 
with 2 marks.
4. Roll number 4 and 5 can not pick anyone as 
no student with higher roll number has lesser 
marks than them. This is denoted by -1.
Output shows the marks of the weaker student that 
each roll number helps in order. ie- 2,5,2,-1,-1
Example 2:
Input: N = 4, a[] = {1, 2, 3, 4}
Output: -1 -1 -1 -1 
Explanation: As the marks ars in increasing order. 
None of the students can find a classmate who has 
a higher roll number and less marks than them.
Your Task:  
You don't need to read input or print anything. Complete the function help_classmate() which takes the array arr[] and size of array N as input parameters and returns a list of numbers. If a student is unable to find anyone then output is -1.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 5*10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def help_classmate(self, arr, n):
        # Your code goes here
        # Return the list

Solutions:
class Solution:

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


class Solution:

	def help_classmate(self, arr, n):
		stack = []
		list1 = [-1] * n
		for i in range(n):
			while stack and arr[i] < arr[stack[-1]]:
				popedindex = stack.pop()
				list1[popedindex] = arr[i]
			stack.append(i)
		return list1


class Solution:

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


class Solution:

	def help_classmate(self, arr, n):
		s = [-1]
		l = []
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] > s[-1]:
				l.append(s[-1])
				s.append(arr[i])
			else:
				while s[-1] >= arr[i]:
					s.pop()
				l.append(s[-1])
				s.append(arr[i])
		l.reverse()
		return l


class Solution:

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


class Solution:

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


class Solution:

	def help_classmate(self, arr, n):
		st = []
		result = []
		for i in reversed(range(0, n)):
			if len(st) == 0:
				result.append(-1)
				st.append(arr[i])
			elif st and st[-1] >= arr[i]:
				while st and st[-1] >= arr[i]:
					st.pop()
				if st:
					result.append(st[-1])
				else:
					result.append(-1)
				st.append(arr[i])
			else:
				result.append(st[-1])
				st.append(arr[i])
		return result[::-1]


class Solution:

	def help_classmate(self, arr, n):
		i = n - 1
		s = []
		result = []
		while i >= 0:
			while len(s) > 0:
				if s[-1] >= arr[i]:
					s.pop()
				else:
					result.append(s[-1])
					s.append(arr[i])
					break
			if len(s) == 0:
				result.append(-1)
				s.append(arr[i])
			i -= 1
		return result[::-1]


class Solution:

	def help_classmate(self, arr, n):
		ans = [-1] * n
		stack = []
		i = 0
		while i < n:
			while stack and arr[stack[-1]] > arr[i]:
				idx = stack.pop()
				ans[idx] = arr[i]
			stack.append(i)
			i += 1
		return ans


class Solution:

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


from collections import deque

class Solution:

	def help_classmate(self, arr, n):
		sol = [-1] * n
		stack = deque()
		stack.append(0)
		for j in range(1, n):
			if stack and arr[j] < arr[stack[-1]]:
				while stack and arr[j] < arr[stack[-1]]:
					idx = stack.pop()
					sol[idx] = arr[j]
				stack.append(j)
			else:
				stack.append(j)
		return sol


class Solution:

	def help_classmate(self, arr, n):
		stack = []
		ans = [-1] * n
		for (i, ele) in enumerate(arr):
			while stack and arr[stack[-1]] > ele:
				a = stack.pop()
				ans[a] = ele
			stack.append(i)
		return ans


class Solution:

	def help_classmate(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:

	def help_classmate(self, arr, n):
		stack = []
		if n == 0:
			return []
		if n == 1:
			return [-1]
		for i in range(0, n):
			if len(stack) == 0 or arr[i] > stack[-1][0]:
				stack.append([arr[i], i])
			else:
				while arr[i] < stack[-1][0]:
					temp = stack.pop()
					arr[temp[1]] = arr[i]
					if len(stack) == 0:
						break
				stack.append([arr[i], i])
		if len(stack) == 0:
			return arr
		for i in stack:
			arr[i[1]] = -1
		return arr


from collections import deque

class Solution:

	def help_classmate(self, arr, n):
		stack = deque()
		res = []
		for i in range(n - 1, -1, -1):
			if len(stack) == 0:
				res.append(-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:
					res.append(-1)
				else:
					res.append(stack[-1])
			elif len(stack) > 0 and stack[-1] < arr[i]:
				res.append(stack[-1])
			stack.append(arr[i])
		return list(reversed(res))


from collections import deque

class Solution:

	def help_classmate(self, arr, n):
		stack = deque()
		ret = [-1 for _ in range(n)]
		for i in range(n):
			while len(stack) and arr[i] < arr[stack[-1]]:
				ret[stack.pop()] = arr[i]
			stack.append(i)
		return ret


class Solution:

	def help_classmate(self, arr, n):
		stck = []
		stck.append(-1)
		ans = [0] * n
		i = len(arr) - 1
		while i >= 0:
			topE = stck[-1]
			if arr[i] <= topE:
				while topE >= arr[i]:
					stck.pop()
					topE = stck[-1]
			ans[i] = topE
			stck.append(arr[i])
			i -= 1
		return ans


class Solution:

	def help_classmate(self, arr, n):
		res = []
		stack = []
		for i in range(len(arr) - 1, -1, -1):
			if not stack:
				res.append(-1)
			else:
				while stack:
					if stack[-1] >= arr[i]:
						stack.pop()
					else:
						res.append(stack[-1])
						break
				else:
					res.append(-1)
			stack.append(arr[i])
		return reversed(res)


from collections import deque

class Solution:

	def help_classmate(self, nums, n):
		(a, z) = (deque(), [])
		for i in range(n - 1, -1, -1):
			while len(a):
				if nums[i] <= a[-1]:
					a.pop()
				else:
					z.append(a[-1])
					break
			if len(a) == 0:
				z.append(-1)
			a.append(nums[i])
		return z[::-1]


class Solution:

	def help_classmate(self, arr, n):
		stack = [arr[n - 1]]
		ans = [-1]
		for i in range(len(arr) - 2, -1, -1):
			if arr[i] > stack[-1]:
				ans.append(stack[-1])
				stack.append(arr[i])
			else:
				while True:
					stack.pop()
					if not stack:
						ans.append(-1)
						stack.append(arr[i])
						break
					if arr[i] > stack[-1]:
						ans.append(stack[-1])
						stack.append(arr[i])
						break
		left = 0
		right = len(ans) - 1
		while left < right:
			(ans[left], ans[right]) = (ans[right], ans[left])
			left += 1
			right -= 1
		return ans


class Solution:

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


class Solution:

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


class Solution:

	def help_classmate(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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def help_classmate(self, array, n):
		stack = []
		N = len(array)
		answer = [-1] * N
		index = 0
		while index < N:
			if len(stack) == 0:
				stack.append(index)
				index += 1
				continue
			while len(stack) > 0 and array[stack[-1]] > array[index]:
				popped = stack.pop()
				answer[popped] = array[index]
			stack.append(index)
			index += 1
		return answer


class Solution:

	def help_classmate(self, arr, n):
		stack = []
		temp = arr[::-1]
		nse = []
		for i in temp:
			if len(stack) == 0:
				stack.append(i)
				nse.append(-1)
			else:
				while len(stack) > 0 and stack[-1] >= i:
					stack.pop()
				if len(stack) == 0:
					stack.append(i)
					nse.append(-1)
				else:
					nse.append(stack[-1])
			stack.append(i)
		return nse[::-1]


class Solution:

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


class Solution:

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


class Solution:

	def help_classmate(self, arr, n):
		stack = []
		ret = [-1 for _ in range(n)]
		for i in range(n):
			while len(stack) and arr[i] < arr[stack[-1]]:
				ret[stack.pop()] = arr[i]
			stack.append(i)
		return ret


class Solution:

	def help_classmate(self, arr, n):
		stck = []
		nxtSmaller = []
		i = n - 1
		while i >= 0:
			if len(stck) == 0:
				nxtSmaller.append(-1)
				stck.append(arr[i])
				i -= 1
			elif arr[i] > stck[-1]:
				nxtSmaller.append(stck[-1])
				stck.append(arr[i])
				i -= 1
			else:
				stck.pop()
		return nxtSmaller[::-1]


class Solution:

	def help_classmate(self, arr, n):
		from collections import deque
		ans = []
		d = deque(ans)
		d.append(-1)
		stack = []
		stack.append(arr[-1])
		for i in range(len(arr) - 2, -1, -1):
			while len(stack) and arr[i] <= stack[-1]:
				stack.pop()
			if len(stack) == 0:
				stack.append(arr[i])
				d.appendleft(-1)
			else:
				d.appendleft(stack[-1])
				stack.append(arr[i])
		return d


class Solution:

	def help_classmate(self, a, n):
		b = [-1] * n
		i = n - 2
		stack = []
		stack.append(a[n - 1])
		while i >= 0:
			while stack and stack[-1] >= a[i]:
				stack.pop()
			if stack and stack[-1] < a[i]:
				b[i] = stack[-1]
			stack.append(a[i])
			i -= 1
		return b


class Solution:

	def help_classmate(self, arr, n):
		from collections import deque
		stack = deque()
		result = []
		for i in range(n - 1, -1, -1):
			num = arr[i]
			if len(stack) == 0:
				result.append(-1)
			else:
				while len(stack) != 0 and arr[i] <= stack[-1]:
					stack.pop()
				if len(stack) == 0:
					result.append(-1)
				else:
					result.append(stack[-1])
			stack.append(num)
		return result[::-1]


class Solution:

	def help_classmate(self, arr, n):
		stack = [-1]
		output = []
		for i in arr[::-1]:
			while stack[-1] >= i:
				stack.pop()
			output.append(stack[-1])
			stack.append(i)
		return output[::-1]


class Solution:

	def help_classmate(self, nums, n):
		n = len(nums)
		res = [-1] * n
		stk = []
		for i in range(n - 1, -1, -1):
			while stk and nums[stk[-1]] >= nums[i]:
				stk.pop()
			if stk and nums[stk[-1]] < nums[i]:
				res[i] = nums[stk[-1]]
			stk.append(i)
		return res


import bisect

class Solution:

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


class Solution:

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


class Solution:

	def help_classmate(self, arr, n):
		s = []
		arr = arr[::-1]
		res = []
		i = 0
		j = 0
		while j < n:
			if len(s) == 0:
				res.append(-1)
			elif arr[j] > s[-1]:
				res.append(s[-1])
			else:
				while len(s) != 0 and arr[j] <= s[-1]:
					s.pop()
				if len(s) == 0:
					res.append(-1)
				else:
					res.append(s[-1])
			s.append(arr[j])
			j += 1
		return res[::-1]


class Solution:

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


class Solution:

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


class Solution:

	def help_classmate(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 help_classmate(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 help_classmate(self, arr, n):
		stack = []
		result = [-1] * len(arr)
		for i in range(0, len(arr)):
			while stack and arr[stack[-1]] > arr[i]:
				result[stack.pop()] = arr[i]
			stack.append(i)
		return result


class Solution:

	def help_classmate(self, arr, n):
		s = [-1]
		ans = []
		for i in range(n - 1, -1, -1):
			curr = arr[i]
			while s[-1] >= curr:
				s.pop()
			ans.append(s[-1])
			s.append(curr)
		return ans[::-1]


class Solution:

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


class Solution:

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


class Solution:

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