Given an array A of N length. We need to calculate the next smallest greater element for each element in a given array. If the next greater element is not available in a given array then we need to fill -10000000 at that index place.
Example 1:
Input : arr[] = {13, 6, 7, 12}
Output : _ 7 12 13 
Explanation:
Here, at index 0, 13 is the greatest value 
in given array and no other array element 
is greater from 13. So at index 0 we fill 
'-10000000'.
Example 2:
Input : arr[] = {6, 3, 9, 8, 10, 2, 1, 15, 7} 
Output :  7 6 10 9 15 3 2 _ 8
Explanation: Here, at index 7, 15 is the greatest
value in given array and no other array element is
greater from 15. So at index 7 we fill '-10000000'.
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function greaterElement() that takes an array (arr), sizeOfArray (n), and return an array that displays the next greater element to element at that index. The driver code takes care of the printing.
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{5}
-10^{6} ≤ A_{i} ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Complete search

Starter code: #User function Template for python3





def greaterElement (arr,  n) : 

    #Complete the function



Solutions:
import bisect

def greaterElement(arr, n):
	arr_sorted = sorted(arr)
	output = []
	for val in arr:
		idx = bisect.bisect_right(arr_sorted, val)
		smallest_greater = arr_sorted[idx] if idx <= n - 1 else -10000000
		output.append(smallest_greater)
	return output


from bisect import bisect_right

def greaterElement(arr, n):
	sortedArr = sorted(arr[:])
	res = []
	for element in arr:
		idx = bisect_right(sortedArr, element)
		res.append(-10000000 if idx == n else sortedArr[idx])
	return res


def greaterElement(arr, n):
	no = -10000000
	cp = sorted(arr)
	res = []
	for i in range(n):
		idx = bisect_right(cp, arr[i])
		if idx == n:
			res.append(no)
		else:
			res.append(cp[idx])
	return res
from bisect import *


import bisect
import copy

def greaterElement(arr, n):
	temp = copy.deepcopy(arr)
	arr.sort()
	ans = [0 for i in range(n)]
	for i in range(n):
		idx = bisect.bisect(arr, temp[i])
		if idx <= n - 1:
			ans[i] = arr[idx]
		else:
			ans[i] = -10000000
	return ans


def greaterElement(arr, n):
	result = []
	temp = []
	for i in range(0, n):
		temp.append(arr[i])
	temp.sort()
	for i in range(0, n):
		if arr[i] == temp[n - 1]:
			result.append(-10000000)
		else:
			st = 0
			ed = n - 1
			while st <= ed:
				mid = (st + ed) // 2
				if temp[mid] > arr[i]:
					ed = mid - 1
				else:
					st = mid + 1
			result.append(temp[st])
	return result


def greaterElement(arr, n):
	s = list(set(arr))
	temp = sorted(s)
	ans = []
	temp.sort()
	d = {}
	l = len(s)
	for i in range(l - 1):
		d[temp[i]] = temp[i + 1]
	d[temp[l - 1]] = -10000000
	for i in range(n):
		ans.append(d[arr[i]])
	return ans


def greaterElement(arr, n):
	s = set(arr)
	s = sorted(s)
	d = {}
	for i in range(len(s) - 1):
		d[s[i]] = s[i + 1]
	d[s[-1]] = -10000000
	for i in range(n):
		arr[i] = d[arr[i]]
	return arr


def greaterElement(a, n):
	l = sorted(a)
	d = {}
	for i in range(n - 1):
		d[l[i]] = l[i + 1]
	d[l[-1]] = -10000000
	for i in range(n):
		a[i] = d[a[i]]
	return a


def greaterElement(arr, n):
	d = dict()
	N = [i for i in arr]
	N.sort()
	for i in range(n - 1):
		d[N[i]] = N[i + 1]
	d[N[i + 1]] = -10000000
	res = []
	for i in arr:
		res.append(d[i])
	return res


def greaterElement(arr, n):
	sarr = sorted(arr)
	d = {}
	for i in range(n - 1):
		d[sarr[i]] = sarr[i + 1]
	d[sarr[-1]] = '_'
	for i in range(n):
		arr[i] = d[arr[i]]
	return arr


def greaterElement(arr, n):
	cp = list(set(arr))
	cp.sort()
	res = []
	for i in range(n):
		num = arr[i]
		idx = locate(cp, num)
		if idx == len(cp) - 1:
			res.append(-10000000)
		else:
			res.append(cp[idx + 1])
	return res

def locate(arr, num):
	return locater(arr, 0, len(arr) - 1, num)

def locater(arr, left, right, num):
	if left == right:
		return left
	mid = (left + right) // 2
	if arr[mid] == num:
		return mid
	elif arr[mid] < num:
		return locater(arr, mid + 1, right, num)
	else:
		return locater(arr, left, mid - 1, num)


def greaterElement(arr, n):
	b = arr[:]
	d = {}
	arr.sort()
	for i in range(n - 1):
		d[arr[i]] = arr[i + 1]
	d[arr[n - 1]] = -10000000
	for i in range(n):
		b[i] = d[b[i]]
	return b


import bisect

def greaterElement(arr, n):
	sorted_arr = sorted(arr)
	arr2 = []
	for item in arr:
		if item == sorted_arr[-1]:
			arr2.append(-10000000)
		else:
			arr2.append(sorted_arr[bisect.bisect(sorted_arr, item)])
	return arr2


def greaterElement(arr, n):
	res = []
	temp = []
	for x in arr:
		temp.append(x)
	temp.sort()
	for x in arr:
		if temp[-1] == x:
			res.append(-10000000)
		else:
			st = 0
			ed = n - 1
			while st <= ed:
				mid = (ed + st) // 2
				if temp[mid] > x:
					ed = mid - 1
				else:
					st = mid + 1
			res.append(temp[st])
	return res


def binarysearch(arr, l, r, k):
	if l <= r:
		mid = (l + r) // 2
		if arr[mid] > k:
			return binarysearch(arr, l, mid - 1, k)
		else:
			return binarysearch(arr, mid + 1, r, k)
	return l

def greaterElement(arr, n):
	arr2 = arr.copy()
	arr2.sort()
	res = []
	for i in range(n):
		l = binarysearch(arr2, 0, n - 1, arr[i])
		if l >= n:
			res.append(-10000000)
		else:
			res.append(arr2[l])
	return res


from bisect import bisect_left

def greaterElement(arr, n):
	arrNew = sorted(list(set(arr)))
	out = []
	for i in range(0, n):
		j = bisect_left(arrNew, arr[i])
		if j < len(arrNew) - 1:
			out.append(arrNew[j + 1])
		else:
			out.append(-10000000)
	return out


def greaterElement(arr, n):
	temp = arr.copy()
	temp.sort()

	def search(arr, key):
		start = 0
		end = len(arr) - 1
		mid = (start + end) // 2
		while start <= end:
			if arr[mid] <= key:
				start = mid + 1
			else:
				end = mid - 1
			mid = (start + end) // 2
		if start >= len(arr):
			return -pow(10, 7)
		else:
			return arr[start]
	for index in range(len(arr)):
		arr[index] = search(temp, arr[index])
	return arr


def greaterElement(arr, n):
	res = []
	temp = []
	for i in range(n):
		temp.append(arr[i])
	temp.sort()
	for i in range(n):
		if arr[i] == temp[n - 1]:
			res.append(-10000000)
		else:
			l = 0
			r = n - 1
			while l <= r:
				m = (l + r) // 2
				if temp[m] > arr[i]:
					r = m - 1
				else:
					l = m + 1
			res.append(temp[l])
	return res


def greaterElement(arr, n):
	arr1 = sorted(arr)
	res = [0] * n
	j = 0
	k = n - 1
	for (z, i) in enumerate(arr):
		j = 0
		k = n - 1
		while j <= k:
			mid = (j + k) // 2
			if arr[z] == arr1[mid]:
				if mid == n - 1:
					res[z] = -10000000
					break
				else:
					while arr1[mid + 1] == arr1[mid]:
						mid = mid + 1
						if mid >= n - 1:
							res[z] = -10000000
							break
					if mid < n - 1:
						res[z] = arr1[mid + 1]
					break
			elif arr[z] > arr1[mid]:
				j = mid + 1
			elif arr[z] < arr1[mid]:
				k = mid - 1
	return res


def greaterElement(arr, n):
	s = list(set(arr))
	s = sorted(s)
	temp_dict = {s[i]: i for i in range(len(s))}
	for i in range(n):
		ind = temp_dict[arr[i]]
		if ind + 1 == len(s):
			arr[i] = -10000000
		else:
			arr[i] = s[ind + 1]
	return arr


def greaterElement(arr, n):
	x = arr.copy()
	x.sort()
	d = {}
	for i in range(n - 1):
		d[x[i]] = x[i + 1]
	d[x[-1]] = -10000000
	ans = []
	for i in arr:
		ans.append(d[i])
	return ans


def getGreater(arr, target):
	n = len(arr)
	low = 0
	high = n - 1
	while low <= high:
		mid = low + (high - low) // 2
		if arr[mid] == target:
			if mid == n - 1:
				return -10000000
			else:
				return arr[mid + 1]
		if arr[mid] == target:
			return arr[mid + 1]
		elif arr[mid] > target:
			high = mid - 1
		else:
			low = mid + 1
	return -10000000

def greaterElement(arr, n):
	s = set(arr)
	lst = list(s)
	lst.sort()
	ans = [None] * n
	for i in range(n):
		res = getGreater(lst, arr[i])
		ans[i] = res
	return ans


def greaterElement(arr, n):
	a = sorted(arr)
	d = {}
	for i in range(n - 1):
		d[a[i]] = a[i + 1]
	d[a[n - 1]] = -10000000
	return [d[k] for k in arr]


def greaterElement(arr, n):
	s = list(set(arr))
	s = sorted(s)
	temp_dict = {s[i]: i for i in range(len(s))}
	for i in range(n):
		ind = temp_dict[arr[i]]
		if ind + 1 == len(s):
			arr[i] = -10000000
		else:
			arr[i] = s[ind + 1]
	return arr
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = greaterElement(arr, n)
	ans = ''
	for i in res:
		if i == -10000000:
			ans += '_ '
		else:
			ans += str(i) + ' '
	print(ans)


def greaterElement(arr, n):
	a = list(set(arr))
	a = sorted(a)
	t = {a[i]: i for i in range(len(a))}
	for i in range(n):
		index = t[arr[i]]
		if index + 1 == len(a):
			arr[i] = -10000000
		else:
			arr[i] = a[index + 1]
	return arr
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = greaterElement(arr, n)
	ans = ''
	for i in res:
		if i == -10000000:
			ans += '_ '
		else:
			ans += str(i) + ' '
	print(ans)


def greaterElement(arr, n):
	sortedArr = sorted(list(set(arr)))
	d = {sortedArr[i]: i for i in range(len(sortedArr))}
	for i in range(n):
		integer = d[arr[i]]
		if integer + 1 == len(sortedArr):
			arr[i] = -10000000
		else:
			arr[i] = sortedArr[integer + 1]
	return arr


def greaterElement(arr, n):
	indexes = list(range(n))
	indexes.sort(key=lambda x: arr[x])
	ans = [-10000000] * n
	for i in range(n - 1):
		cur_idx = indexes[i]
		cur_val = arr[indexes[i]]
		inc = 1
		next_val = cur_val
		while next_val == cur_val and i + inc < n:
			next_val = arr[indexes[i + inc]]
			inc += 1
		if next_val != cur_val:
			ans[cur_idx] = next_val
	return ans


def greaterElement(arr, n):
	s = list(set(arr))
	s = sorted(s)
	d = {s[i]: i for i in range(len(s))}
	for i in range(n):
		m = d[arr[i]]
		if m + 1 == len(s):
			arr[i] = -10000000
		else:
			arr[i] = s[m + 1]
	return arr


def greaterElement(arr, n):
	arrs = sorted(arr)
	d = {}
	ans = []
	for i in range(n - 1):
		d[arrs[i]] = arrs[i + 1]
	d[arrs[n - 1]] = -10000000
	for i in range(n):
		ans.append(d[arr[i]])
	return ans


def greaterElement(arr, n):
	m = set()
	z = sorted(arr)
	for i in z:
		m.add(i)
	m = list(m)
	m = sorted(m)
	ans = [-10000000] * n
	for i in range(n):
		l = 0
		r = len(m) - 1
		while l <= r:
			mid = (l + r) // 2
			if m[mid] > arr[i]:
				r = mid - 1
			elif m[mid] < arr[i]:
				l = mid + 1
			else:
				if mid != len(m) - 1:
					ans[i] = m[mid + 1]
				else:
					break
				break
	return ans


def greaterElement(arr, n):
	m = {}
	z = sorted(arr)
	for i in z:
		if i in m:
			continue
		else:
			m[i] = 1
	m = m.keys()
	m = sorted(m)
	ans = [-10000000] * n
	for i in range(n):
		l = 0
		r = len(m) - 1
		while l <= r:
			mid = (l + r) // 2
			if m[mid] > arr[i]:
				r = mid - 1
			elif m[mid] < arr[i]:
				l = mid + 1
			else:
				if mid != len(m) - 1:
					ans[i] = m[mid + 1]
				else:
					break
				break
	return ans


def greaterElement(arr, n):
	s = sorted(arr)
	hm = {}
	res = []
	for i in range(len(s)):
		if i == n - 1:
			hm[s[i]] = -10000000
		else:
			hm[s[i]] = s[i + 1]
	for i in arr:
		res.append(hm[i])
	return res


from collections import defaultdict as dc

def greaterElement(a, n):
	p = dc(int)
	q = sorted(list(set(a)))
	for i in range(len(q) - 1):
		p[q[i]] = q[i + 1]
	p[q[-1]] = -10 ** 7
	ans = []
	for i in range(n):
		ans.append(p[a[i]])
	return ans


def greaterElement(arr, n):
	Arr = arr.copy()
	Arr.sort()
	Dict = {}
	for i in range(n - 1):
		Dict[Arr[i]] = Arr[i + 1]
	arr1 = [0 for _ in range(n)]
	Dict[Arr[n - 1]] = -100000
	for i in range(n):
		if Dict[arr[i]] == -100000:
			arr1[i] = '_'
		else:
			arr1[i] = Dict[arr[i]]
	return arr1


def greaterElement(arr, n):
	a = -10000000
	b = arr.copy()
	b.sort()
	gg = {}
	dd = {}
	for i in range(n):
		gg[b[i]] = i
		dd[i] = b[i]
	ans = []
	for i in arr:
		k = gg[i]
		if k == n - 1:
			ans.append(a)
		else:
			ans.append(dd[k + 1])
	return ans


def greaterElement(arr, n):
	arr1 = sorted(set(arr))
	l = len(arr1)
	res = []
	d = {}
	for i in range(l):
		d[arr1[i]] = i
	for i in arr:
		ind = d[i]
		if ind + 1 < l:
			res.append(arr1[ind + 1])
		else:
			res.append(-10000000)
	return res


def greaterElement(arr, n):
	l = sorted(arr)
	k = l[-1]
	D = {}
	for i in range(n):
		if l[i] == k:
			D[k] = -10000000
		else:
			D[l[i]] = l[i + 1]
	for i in range(n):
		arr[i] = D[arr[i]]
	return arr


def greaterElement(arr, n):
	sorted_arr = sorted(arr)
	dict_map = {}
	op = []
	for i in range(len(sorted_arr) - 1):
		if sorted_arr[i] != sorted_arr[i + 1]:
			dict_map.update({sorted_arr[i]: sorted_arr[i + 1]})
	for i in arr:
		if i in dict_map.keys():
			op.append(dict_map[i])
		else:
			op.append('_')
	return op

def merge_sort(arr):
	if len(arr) <= 1:
		return arr
	m = len(arr) // 2
	sorted_left_array = merge_sort(arr[0:m])
	sorted_right_array = merge_sort(arr[m:])
	merged_sorted_array = merge(sorted_left_array, sorted_right_array)
	return merged_sorted_array

def merge(left_array, right_array):
	i = 0
	j = 0
	op = []
	while i < len(left_array) and j < len(right_array):
		if left_array[i] < right_array[j]:
			op.append(left_array[i])
			i += 1
		else:
			op.append(right_array[j])
			j += 1
	return op + left_array[i:] + right_array[j:]


import collections

def greaterElement(arr, n):
	ans = [-10000000] * n
	idxs = collections.defaultdict(list)
	for (idx, val) in enumerate(arr):
		idxs[val].append(idx)
	arr.sort()
	curr_max = arr[-1]
	idxs[arr[-1]].pop()
	prev_max = -10000000
	for idx in range(n - 2, -1, -1):
		if idx + 1 < n and arr[idx] == arr[idx + 1]:
			index = idxs[arr[idx]].pop()
			ans[index] = prev_max
		elif arr[idx] < curr_max:
			index = idxs[arr[idx]].pop()
			ans[index] = curr_max
			prev_max = curr_max
		curr_max = min(curr_max, arr[idx])
	return ans


def greaterElement(arr, n):
	b = sorted(arr)
	new = []
	d = {}
	for i in range(0, len(b) - 1):
		d[b[i]] = b[i + 1]
	d[b[-1]] = -10000000
	for i in arr:
		new.append(d[i])
	return new


def BST(brr, n, k):
	l = 0
	r = n - 1
	while l <= r:
		mid = (l + r) // 2
		if brr[mid] == k:
			return mid
		if brr[mid] < k:
			l = mid + 1
		else:
			r = mid - 1
	return -1

def greaterElement(arr, n):
	brr = sorted(arr)
	for j in range(n):
		v = BST(brr, n, arr[j])
		while v < n - 1 and brr[v] == brr[v + 1]:
			v += 1
		if v == -1 or v == n - 1:
			arr[j] = -10000000
		else:
			arr[j] = brr[v + 1]
	return arr


import sys

def greaterElement(arr, n):
	s = set()
	m = -9999999999
	for i in arr:
		s.add(i)
		m = max(m, i)
	res = [-1] * n
	for i in range(n):
		flag = False
		for j in range(arr[i] + 1, m + 1):
			if j in s:
				res[i] = j
				flag = True
				break
		if not flag:
			res[i] = -10000000
	return res


def search(arr, n, ele):
	i = 0
	j = n - 1
	while i <= j:
		mid = (i + j) // 2
		if arr[mid] == ele:
			return arr[mid + 1]
		elif arr[mid] > ele:
			j = mid - 1
		else:
			i = mid + 1

def greaterElement(arr, n):
	arr1 = arr.copy()
	arr1 = list(set(arr1))
	arr1.sort()
	Len = len(arr1)
	Max = max(arr)
	for i in range(n):
		if arr[i] == Max:
			arr[i] = '_'
		else:
			arr[i] = search(arr1, Len, arr[i])
	return arr


def greaterElement(arr, n):
	x = sorted(list(set(arr)))
	d = {x[i]: i for i in range(len(x))}
	ind = 0
	for i in range(len(arr)):
		ind = d[arr[i]]
		if ind + 1 == len(x):
			arr[i] = -10000000
		else:
			arr[i] = x[ind + 1]
	return arr


def greaterElement(arr, n):
	idx = [i for i in range(n)]
	idx.sort(key=lambda i: arr[i])
	new_arr = [0 for _ in range(n)]
	for i in range(n):
		for j in range(i + 1, n + 1):
			if j == n:
				new_arr[idx[i]] = -10000000
				break
			if arr[idx[j]] > arr[idx[i]]:
				new_arr[idx[i]] = arr[idx[j]]
				break
	return new_arr


def greaterElement(arr, n):
	a = sorted(arr)
	d = dict()
	for i in range(n):
		d[a[i]] = i
	for i in range(n):
		if d[arr[i]] == n - 1:
			arr[i] = -10000000
		else:
			arr[i] = a[d[arr[i]] + 1]
	return arr

def nextG(a, k, n):
	(i, j) = (0, n - 1)
	ans = -10000001
	while i <= j:
		mid = (j + i) // 2
		if a[mid] > k:
			ans = a[mid]
			j = mid - 1
		else:
			i = mid + 1
	if ans == -10000001:
		return -10000000
	return ans


def greaterElement(arr, n):
	new_arr = sorted(arr)
	hash = {}
	for i in range(len(new_arr) - 1):
		hash[new_arr[i]] = new_arr[i + 1]
	hash[new_arr[len(new_arr) - 1]] = -10000000
	for i in range(len(arr)):
		arr[i] = hash[arr[i]]
	return arr


from bisect import bisect

def findI(a, x, lo=0, hi=-1):
	i = bisect(a, x, lo, hi)
	if i == 0:
		return -1
	elif a[i - 1] == x:
		return i - 1
	else:
		return -1

def greaterElement(arr, n):
	nums = list(set([x for x in arr]))
	nums.sort()
	next = []
	maxN = nums[len(nums) - 1]
	for i in arr:
		if i != maxN:
			next.append(nums[findI(nums, i, 0, len(nums)) + 1])
		else:
			next.append(-10000000)
	return next


import bisect

def greaterElement(arr, n):
	a = list(set(arr))
	a.sort()
	ans = []
	for x in arr:
		ind = bisect.bisect(a, x)
		if 0 <= ind < len(a):
			ans.append(a[ind])
		else:
			ans.append(-10000000)
	return ans


def greaterElement(arr, n):
	k = sorted(arr)
	dic = {}
	for i in range(n - 1):
		dic[k[i]] = k[i + 1]
	dic[k[-1]] = -10000000
	res = []
	for i in arr:
		res.append(dic[i])
	return res


def greaterElement(arr, n):
	temp = arr.copy()
	temp.sort()
	dicty = {}
	for i in range(n - 1):
		dicty[temp[i]] = temp[i + 1]
	dicty[temp[n - 1]] = -10000000
	out = []
	for i in arr:
		out.append(dicty[i])
	return out


def greaterElement(arr, n):
	s = sorted(range(len(arr)), key=lambda k: arr[k])[::-1]
	res = [0] * n
	v = arr[s[0]]
	res[s[0]] = -10000000
	for ix in range(len(s) - 1):
		if v > arr[s[ix + 1]]:
			res[s[ix + 1]] = v
			v = arr[s[ix + 1]]
		else:
			res[s[ix + 1]] = res[s[ix]]
	return res


def greaterElement(arr, n):
	(st, mp) = (sorted(set(arr)), dict())
	for i in range(len(st) - 1):
		mp[st[i]] = st[i + 1]
	for i in range(n):
		arr[i] = mp.get(arr[i], -10000000)
	return arr


def greaterElement(arr, n):
	x = list(enumerate(arr))
	r = sorted(x, key=lambda x: x[1])
	res = [-10000000] * len(arr)
	i = 0
	j = 1
	while i < len(arr) - 1 and j < len(arr):
		if r[i][1] != r[j][1]:
			res[r[i][0]] = r[j][1]
			i += 1
			j = i + 1
		else:
			j += 1
	return res


def greaterElement(arr, n):
	max1 = max(arr)
	temp = sorted(enumerate(arr), key=lambda x: x[1])
	t = []
	for id in range(len(temp)):
		if temp[id][1] == max1:
			arr[temp[id][0]] = '_'
		elif temp[id][1] == temp[id + 1][1]:
			t.extend([temp[id][0], temp[id + 1][0]])
		elif len(t) == 0:
			arr[temp[id][0]] = temp[id + 1][1]
		else:
			for j in range(len(t)):
				arr[t[j]] = temp[id + 1][1]
			t = []
	return arr