Given an array arr[] of N integers and replace every element with the least greater element on its right side in the array. If there are no greater elements on the right side, replace it with -1. 
Example 1:
Input:
arr[] = {8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28}
Output: {18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1}
Explanation: 
The least next greater element of 8 is 18.
The least next greater element of 58 is 63 and so on.
Example 2:
Input:
arr[] = {2, 6, 9, 1, 3, 2}
Output: {3, 9, -1, 2, -1, -1}
Explanation: 
The least next greater element of 2 is 3. 
The least next greater element of 6 is 9.
least next greater element for 9 does not
exist and so on.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findLeastGreater() which takes an array arr[] of size N and returns a list as an output.
Expected Time Complexity: O(N* log N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{5}
1 <= A[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Starter code: 



from typing import List

class Solution:

    def findLeastGreater(self, n : int, arr : List[int]) -> List[int]:

        # code here

        



Solutions:
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:

		class Node:

			def __init__(self, val):
				self.data = val
				self.right = None
				self.left = None

		def insert(root, val):
			global succ
			if not root:
				return Node(val)
			if val < root.data:
				succ = root
				root.left = insert(root.left, val)
			elif val >= root.data:
				root.right = insert(root.right, val)
			return root

		def replace(arr, n):
			global succ
			root = None
			for i in range(n - 1, -1, -1):
				succ = None
				root = insert(root, arr[i])
				if succ:
					arr[i] = succ.data
				else:
					arr[i] = -1
			return arr
		arr = replace(arr, n)
		return arr


from typing import List
from bisect import insort, bisect_right
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		res = [-1] * n
		temp = []
		for i in range(n - 1, -1, -1):
			insort(temp, arr[i])
			idx = bisect_right(temp, arr[i])
			if idx < len(temp):
				res[i] = temp[idx]
		return res


from typing import List
from bisect import bisect_right
from sortedcontainers import SortedSet

def bs_last(arr, l, r, x):
	if l > r:
		return -1
	if x >= arr[-1]:
		return bisect_right(arr, x, l, r)
	return bisect_right(arr, x, l, r) - 1

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		s = SortedSet([])
		ans = [0] * n
		for i in range(n - 1, -1, -1):
			ind = s.bisect_right(arr[i])
			if ind == len(s):
				ans[i] = -1
			else:
				ans[i] = s[ind]
			s.add(arr[i])
		return ans


from typing import List
from bisect import bisect_right
from sortedcontainers import SortedList

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		s = SortedList([])
		ans = [0] * n
		for i in range(n - 1, -1, -1):
			ind = s.bisect_right(arr[i])
			if ind == len(s):
				ans[i] = -1
			else:
				ans[i] = s[ind]
			s.add(arr[i])
		return ans


from collections import defaultdict
from heapq import heappush, heappop, heapify
from typing import List

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:

		def BST(root, x, succ):
			if root is None:
				return Node(x)
			if root.data > x:
				succ[0] = root
				root.left = BST(root.left, x, succ)
			else:
				root.right = BST(root.right, x, succ)
			return root
		root = Node(arr[-1])
		arr[-1] = -1
		for i in range(n - 2, -1, -1):
			succ = [None]
			BST(root, arr[i], succ)
			if succ[0]:
				arr[i] = succ[0].data
			else:
				arr[i] = -1
		return arr

def nextGreaterIndex(temp):
	n = len(temp)
	res = [-1 for i in range(n)]
	stack = []
	for i in range(n):
		if len(stack) == 0 or temp[i][1] < stack[-1]:
			stack.append(temp[i][1])
		else:
			while len(stack) > 0 and temp[i][1] > stack[-1]:
				res[stack[-1]] = temp[i][1]
				stack.pop()
			stack.append(temp[i][1])
	return res

def replaceByLeastGreaterUsingStack(arr, n):
	temp = []
	for i in range(n):
		temp.append([arr[i], i])
	temp.sort()
	indexes = nextGreaterIndex(temp)
	res = [-1 for i in range(n)]
	for i in range(n):
		if indexes[temp[i][1]] != -1:
			res[temp[i][1]] = arr[indexes[temp[i][1]]]
	return res


from typing import List
import bisect

class Solution:

	def findLeastGreater(self, n: int, a: List[int]) -> List[int]:
		ans = [-1]
		temp = [a[n - 1]]
		for i in range(n - 2, -1, -1):
			k = bisect.bisect_right(temp, a[i])
			if k >= 0 and k < len(temp):
				bisect.insort_left(temp, a[i])
				ans.append(temp[k + 1])
			else:
				bisect.insort_left(temp, a[i])
				ans.append(-1)
		return ans[::-1]


from typing import List
from collections import deque

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

class Solution:

	def __init__(self):
		self.root = None

	def insert(self, root, val, succ):
		if not root:
			return (Node(val), succ)
		if val < root.data:
			succ = root
			(root.left, succ) = self.insert(root.left, val, succ)
		elif val >= root.data:
			(root.right, succ) = self.insert(root.right, val, succ)
		return (root, succ)

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		ans = [-1] * n
		root = None
		for i in range(n - 1, -1, -1):
			succ = None
			(root, succ) = self.insert(root, arr[i], succ)
			if succ:
				ans[i] = succ.data
		return ans


import bisect
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		st = []
		vec = []
		j = 0
		for i in range(n - 1, -1, -1):
			idx = bisect.bisect(st, arr[i])
			if idx == j:
				vec.append(-1)
			else:
				vec.append(st[idx])
			st.insert(idx, arr[i])
			j += 1
		return vec[::-1]


from typing import List

class Node:

	def __init__(self, data):
		self.data = data
		self.right = None
		self.left = None

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		root = Node(arr[-1])
		ans = [-1] * n
		for i in range(n - 2, -1, -1):
			ans[i] = self.Array_to_BST(root, arr[i], -1)
		return ans

	def Array_to_BST(self, root, val, prev):
		if not root:
			return
		if root.data == val:
			if root.right:
				return self.Array_to_BST(root.right, val, prev)
			else:
				return prev
		elif root.data < val:
			if root.right:
				return self.Array_to_BST(root.right, val, prev)
			else:
				root.right = Node(val)
				return prev
		elif root.left:
			return self.Array_to_BST(root.left, val, root.data)
		else:
			root.left = Node(val)
			return root.data


from typing import List

class tree:

	def __init__(self, data):
		self.data = data
		self.left = self.right = None

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:

		def insert(val, root, succ):
			if not root:
				return (tree(val), succ)
			if root.data > val:
				succ = root
				(node, succ) = insert(val, root.left, succ)
				root.left = node
			else:
				(node, succ) = insert(val, root.right, succ)
				root.right = node
			return (root, succ)
		ans = [-1] * n
		head = None
		for i in range(n - 1, -1, -1):
			(head, succ) = insert(arr[i], head, None)
			if succ:
				ans[i] = succ.data
		return ans


class Node:

	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		self.ans = [-1]
		root = Node(arr[n - 1])
		for i in range(n - 2, -1, -1):
			self.addNode(Node(arr[i]), root, -1)
		return self.ans[::-1]

	def addNode(self, node, root, maxi):
		if root.val <= node.val:
			if root.right is None:
				root.right = node
				self.ans.append(maxi)
			else:
				self.addNode(node, root.right, maxi)
		else:
			maxi = root.val
			if root.left is None:
				root.left = node
				self.ans.append(maxi)
			else:
				self.addNode(node, root.left, maxi)


from collections import defaultdict
from heapq import heappush, heappop, heapify
from typing import List

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:

		def BST(root, x, succ):
			if root is None:
				return Node(x)
			if root.data > x:
				succ[0] = root
				root.left = BST(root.left, x, succ)
			else:
				root.right = BST(root.right, x, succ)
			return root
		root = Node(arr[-1])
		arr[-1] = -1
		for i in range(n - 2, -1, -1):
			succ = [None]
			BST(root, arr[i], succ)
			if succ[0]:
				arr[i] = succ[0].data
			else:
				arr[i] = -1
		return arr


from bisect import bisect_right
from collections import Counter
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		result = []
		set1 = set()
		arr2 = arr.copy()
		arr2.sort()
		c = Counter(arr2)
		n1 = len(arr2)
		for i in range(n):
			index = bisect_right(arr2, arr[i])
			if index >= n1:
				result.append(-1)
			else:
				while index <= n1 - 1 and arr2[index] in set1 and (c[arr2[index]] == 0):
					index += 1
				if index >= n1:
					result.append(-1)
				else:
					result.append(arr2[index])
			set1.add(arr[i])
			c[arr[i]] -= 1
		return result


from bisect import bisect
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		brr = []
		output = []
		for i in range(n):
			j = bisect(brr, arr[-i - 1])
			if j == len(brr):
				output.append(-1)
				brr.append(arr[-i - 1])
			else:
				output.append(brr[j])
				brr.insert(j, arr[-i - 1])
		return output[::-1]


from sortedcontainers import SortedList
from typing import List

class Solution:

	def findLeastGreater(self, n: int, a: List[int]) -> List[int]:
		s = SortedList()
		res = [-1] * n
		for i in range(n - 1, -1, -1):
			index = s.bisect_right(a[i])
			if index < len(s):
				res[i] = s[index]
			s.add(a[i])
		return res


from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		ans = [-1] * n
		new = []
		stack = []
		for (i, ele) in enumerate(arr):
			new.append((ele, i))
		new = sorted(new, key=lambda x: x[1], reverse=True)
		new = sorted(new, key=lambda x: x[0])
		for i in range(n):
			while stack and stack[-1][1] < new[i][1]:
				(ele, ind) = stack.pop()
				ans[ind] = new[i][0]
			stack.append((new[i][0], new[i][1]))
		return ans


from typing import List

class Node:

	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None

class BST:

	def __init__(self):
		self.root = None

	def insert(self, value):
		if not self.root:
			self.root = Node(value)
		else:
			current = self.root
			while True:
				if value < current.value:
					if not current.left:
						current.left = Node(value)
						break
					current = current.left
				else:
					if not current.right:
						current.right = Node(value)
						break
					current = current.right

	def find_least_greater(self, value):
		current = self.root
		least_greater = None
		while current:
			if current.value > value:
				least_greater = current.value
				current = current.left
			else:
				current = current.right
		return least_greater

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		bst = BST()
		result = [-1] * n
		for i in range(n - 1, -1, -1):
			bst.insert(arr[i])
			least_greater = bst.find_least_greater(arr[i])
			if least_greater:
				result[i] = least_greater
		return result


from bisect import *
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		ls = []
		for i in range(n - 1, -1, -1):
			ele = arr[i]
			pos = bisect_right(ls, ele)
			if pos < len(ls):
				arr[i] = ls[pos]
			else:
				arr[i] = -1
			ls[pos:pos] = [ele]
		return arr


from typing import List
from bisect import *

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		tmp = []
		for i in range(n - 1, -1, -1):
			ele = arr[i]
			insertPoint = bisect_right(tmp, ele)
			if insertPoint < len(tmp):
				arr[i] = tmp[insertPoint]
			else:
				arr[i] = -1
			insort(tmp, ele)
		return arr


from typing import List

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

class Solution:

	def solve(self, val, head):
		suc = -1
		node = head
		while node:
			pre = node
			if node.data < val:
				node = node.right
			elif node.data > val:
				suc = node.data
				node = node.left
			else:
				if node.right:
					n = node.right
					while n.left:
						n = n.left
					suc = n.data
				pre = None
				break
		newNode = Node(val)
		if pre:
			if pre.data < val:
				pre.right = newNode
			else:
				pre.left = newNode
		return (suc, head)

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		ans = [-1 for i in range(n)]
		head = Node(arr[n - 1])
		for i in range(n - 2, -1, -1):
			(suc, head) = self.solve(arr[i], head)
			ans[i] = suc
		return ans


from typing import List
import bisect

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		list1 = [0] * n
		list1[-1] = -1
		maximum = arr[-1]
		minimum = arr[-1]
		stack = [arr[-1]]
		for i in range(-2, -n - 1, -1):
			if arr[i] >= maximum:
				list1[i] = -1
				maximum = arr[i]
				bisect.insort(stack, arr[i])
			elif arr[i] < minimum:
				list1[i] = stack[0]
				minimum = arr[i]
				bisect.insort(stack, arr[i])
			else:
				bisect.insort(stack, arr[i])
				left = bisect.bisect_right(stack, arr[i])
				list1[i] = stack[left]
		return list1


from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:

		def nextgreater(array):
			s = []
			for i in range(len(array)):
				while s and s[-1].get('value') < array[i]:
					d = s.pop()
					array[d.get('ind')] = array[i]
				s.append({'value': array[i], 'ind': i})
			while s:
				d = s.pop()
				array[d.get('ind')] = -1
			return array
		tmp = [[x, -i] for (i, x) in enumerate(arr)]
		tmp.sort()
		indexes = [-x[1] for x in tmp]
		nextgreater(indexes)
		res = [-1 for i in range(n)]
		tmp = [[x, -y] for (x, y) in tmp]
		for i in range(n):
			if indexes[i] != -1:
				res[tmp[i][1]] = arr[indexes[i]]
		return res


from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:

		class Node:

			def __init__(self, val):
				self.val = val
				self.left = None
				self.right = None

		def insert(node, key):
			nonlocal succ
			if not node:
				return Node(key)
			if node.val > key:
				succ = node.val
				node.left = insert(node.left, key)
			else:
				node.right = insert(node.right, key)
			return node
		root = None
		for i in range(n - 1, -1, -1):
			succ = -1
			root = insert(root, arr[i])
			arr[i] = succ
		return arr


from typing import List

class Node:

	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None

class Solution:

	def findLeastGreater(self, n: int, A: List[int]) -> List[int]:
		root = None
		ans = []
		for a in reversed(A):
			(root, prev) = insert(a, root)
			ans.append(prev)
		return reversed(ans)

def insert(val, root, prev=-1):
	if not root:
		return (Node(val), prev)
	if val < root.val:
		prev = root.val
		(root.left, prev) = insert(val, root.left, prev)
	else:
		(root.right, prev) = insert(val, root.right, prev)
	return (root, prev)


from typing import List

class Node:

	def __init__(self, key):
		self.key = key
		self.left = None
		self.right = None

class Solution:

	def findLeastGreater(self, n: int, nums: List[int]) -> List[int]:
		root = None
		for i in reversed(range(len(nums))):
			successor = -1
			(root, successor) = insert(root, nums[i], successor)
			nums[i] = successor
		return nums

def insert(root, key, successor):
	if root is None:
		return (Node(key), successor)
	if key < root.key:
		successor = root.key
		(root.left, successor) = insert(root.left, key, successor)
	elif key >= root.key:
		(root.right, successor) = insert(root.right, key, successor)
	return (root, successor)


class Node:

	def __init__(self, data):
		self.data = data
		self.left = self.right = None
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:

		def insert(root, x):
			if root == None:
				return Node(x)
			if x < root.data:
				succ[0] = root.data
				root.left = insert(root.left, x)
			else:
				root.right = insert(root.right, x)
			return root
		root = None
		for i in range(n - 1, -1, -1):
			succ = [-1]
			root = insert(root, arr[i])
			arr[i] = succ[0]
		return arr


from typing import List
from sortedcontainers import SortedList

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		res = [0] * n
		s = SortedList([])
		for i in range(n - 1, -1, -1):
			idx = s.bisect_right(arr[i])
			if idx == len(s):
				res[i] = -1
			else:
				res[i] = s[idx]
			s.add(arr[i])
		return res


from bisect import bisect_right
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		s = []
		res = [-1] * n
		for i in range(n - 1, -1, -1):
			ind = bisect_right(s, arr[i])
			if ind < len(s):
				res[i] = s[ind]
			s.insert(ind, arr[i])
		return res


from bisect import insort, bisect_right
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		res = [-1] * n
		temp = []
		for (i, v) in reversed(list(enumerate(arr))):
			insort(temp, v)
			idx = bisect_right(temp, v)
			if idx < len(temp):
				res[i] = temp[idx]
		return res


from bisect import bisect_right
from collections import Counter
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		sol = []
		sample = set()
		new = arr.copy()
		new.sort()
		temp = Counter(new)
		for i in range(n):
			pos = bisect_right(new, arr[i])
			if pos >= n:
				sol.append(-1)
			else:
				while pos < n and new[pos] in sample and (temp[new[pos]] == 0):
					pos += 1
				if pos >= n:
					sol.append(-1)
				else:
					sol.append(new[pos])
			sample.add(arr[i])
			temp[arr[i]] -= 1
		return sol


from typing import List

class Node:

	def __init__(self, n):
		self.data = n
		self.left = None
		self.right = None

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		root1 = Node(arr[-1])
		ans = [-1]
		for i in range(n - 2, -1, -1):
			a = arr[i]
			c = -1
			root = root1
			while True:
				if a >= root.data:
					if root.right == None:
						tn = Node(a)
						root.right = tn
						ans.append(c)
						break
					else:
						root = root.right
				elif root.left == None:
					tn = Node(a)
					root.left = tn
					ans.append(root.data)
					break
				else:
					c = root.data
					root = root.left
		return ans[::-1]


from sortedcontainers import SortedList
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		l = SortedList()
		ans = []
		for i in range(n - 1, -1, -1):
			if arr[i] not in l:
				l.add(arr[i])
			x = l.index(arr[i])
			if x == len(l) - 1:
				ans.append(-1)
			else:
				ans.append(l[x + 1])
		return ans[::-1]


import bisect
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		q = []
		output = [-1 for i in range(n)]
		for i in range(n - 1, -1, -1):
			if len(q) == 0:
				q.append(arr[i])
			else:
				inx = bisect.bisect(q, arr[i])
				if inx == len(q):
					if q[inx - 1] != arr[i]:
						q.append(arr[i])
					else:
						continue
				elif inx != 0:
					if q[inx - 1] != arr[i]:
						output[i] = q[inx]
						q.insert(inx, arr[i])
					else:
						output[i] = q[inx]
				else:
					output[i] = q[inx]
					q.insert(0, arr[i])
		return output


from typing import List

class node:

	def __init__(self, key):
		self.data = key
		self.left = None
		self.right = None
succ = None

def insertBST(root, key):
	if root:
		global succ
		if root.data < key:
			root.right = insertBST(root.right, key)
			return root
		elif root.data == key:
			insertBST(root.right, key)
			return root
		else:
			succ = root
			root.left = insertBST(root.left, key)
			return root
	else:
		return node(key)

def insert(node, data):
	global succ
	root = node
	if node == None:
		return Node(data)
	if data < node.data:
		succ = node
		root.left = insert(node.left, data)
	elif data > node.data:
		root.right = insert(node.right, data)
	return root

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		root = None
		global succ
		for i in range(n - 1, -1, -1):
			succ = None
			root = insertBST(root, arr[i])
			if succ:
				arr[i] = succ.data
			else:
				arr[i] = -1
		return arr


import bisect
from typing import List

class Solution:

	def findLeastGreater(self, n: int, arr: List[int]) -> List[int]:
		a = []
		ans = []
		for i in range(n - 1, -1, -1):
			ind = bisect.bisect_right(a, arr[i], 0, len(a))
			if ind == len(a):
				a.append(arr[i])
				ans.append(-1)
			else:
				a.insert(ind, arr[i])
				ans.append(a[ind + 1])
		return ans[::-1]