Given an array arr[ ] of N positive integers, the task is to find the greatest element on the left of every element in the array which is strictly smaller than itself, if this element does not exist for an index print "-1".
Example 1:
Input:
N = 5
arr[] = {2, 3, 4, 5, 1}
Output: 
-1 2 3 4 -1
Explanation:
Greatest element on the left of 3 smaller 
than itself is 2, for 4 it is 3 and for 5 
it is 1. Since 2 is the first element and 
no element on its left is present, so it's 
greatest smaller element will be -1 and for 
1 no element smaller than itself is present 
on its left, so it's greatest smaller element 
is -1.
Example 2:
Input:
N = 3
arr[] = {1, 2, 3} 
Output:
-1 1 2 
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 Smallestonleft() that takes an array arr[ ] and sizeOfArray N, and return the required answer. The driver code takes care of the printing.
Expected Time Complexity: O(N*Log(N)).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ arr[i] ≤ 10^{8}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3





def Smallestonleft (arr,  n) : 

    #Complete the function





Solutions:
def Smallestonleft(arr, n):
	ans = []
	s = []
	from bisect import bisect_left

	def BinarySearch(a, x):
		i = bisect_left(a, x)
		if i:
			return i - 1
		else:
			return -1
	res = [-1] * (n + 1)
	lst = []
	lst.append(arr[0])
	for i in range(1, n):
		idx = BinarySearch(lst, arr[i])
		if idx != -1:
			res[i] = lst[idx]
		lst.insert(idx + 1, arr[i])
	for i in range(n):
		print(res[i], end=' ')
	return []


import bisect

def Smallestonleft(arr, n):
	stack = []
	ans = []
	ans.append(-1)
	stack.append(arr[0])
	for i in range(1, n):
		bisect.insort(stack, arr[i])
		it = bisect.bisect_left(stack, arr[i])
		if it:
			ans.append(stack[it - 1])
		else:
			ans.append(-1)
	return ans


import bisect

def Smallestonleft(arr, n):
	ans = []
	arr1 = []
	for i in range(len(arr)):
		bisect.insort(arr1, arr[i])
		k = bisect.bisect_left(arr1, arr[i])
		if k == 0:
			ans.append(-1)
		else:
			ans.append(arr1[k - 1])
	return ans


def Smallestonleft(arr, n):
	a = set()
	va = []
	for i in arr:
		if not a:
			va.append(-1)
		elif i <= min(a):
			va.append(-1)
		else:
			va.append(max(filter(lambda x: x < i, a)))
		a.add(i)
	return va


import bisect

def Smallestonleft(li, n):
	li1 = []
	ans = []
	for i in range(n):
		bisect.insort(li1, li[i])
		j = bisect.bisect_left(li1, li[i])
		if j == 0:
			ans.append(-1)
		else:
			ans.append(li1[j - 1])
	return ans


import bisect

def Smallestonleft(arr, n):
	res = []
	listo = []
	for item in arr:
		bisect.insort(listo, item)
		j = bisect.bisect_left(listo, item)
		if j == 0:
			res.append(-1)
		else:
			res.append(listo[j - 1])
	return res


from bisect import bisect_left, insort_left

def Smallestonleft(arr, n):
	ans = []
	sarr = []
	for e in arr:
		if not sarr:
			insort_left(sarr, e)
			ans.append(-1)
		else:
			idx = bisect_left(sarr, e)
			if idx:
				ans.append(sarr[idx - 1])
			else:
				ans.append(-1)
			insort_left(sarr, e)
	return ans


def Smallestonleft(arr, n):
	ans = []
	s = set()
	for i in arr:
		new = list(sorted(s))
		(low, high) = (0, len(new) - 1)
		a = -1
		while low <= high:
			mid = (low + high) // 2
			if new[mid] < i:
				a = new[mid]
				low = mid + 1
			else:
				high = mid - 1
		ans.append(a)
		s.add(i)
	return ans


from bisect import bisect_left

def BinarySearch(a, x):
	i = bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def findMaximumBefore(arr, n):
	res = [-1] * n
	lst = []
	lst.append(arr[0])
	for i in range(1, n):
		idx = BinarySearch(lst, arr[i])
		if idx != -1:
			res[i] = lst[idx]
		lst.insert(idx + 1, arr[i])
	return res

def Smallestonleft(arr, n):
	return findMaximumBefore(arr, n)


import bisect

def Smallestonleft(arr, n):
	s = []
	v = []
	for i in range(n):
		idx = bisect.bisect_left(s, arr[i])
		if idx == 0:
			v.append(-1)
		else:
			v.append(s[idx - 1])
		s.insert(idx, arr[i])
	return v


def Smallestonleft(arr, n):
	smallest = [-1 for _ in range(n)]
	values = set([arr[0]])
	for i in range(1, n):
		values.add(arr[i])
		bestm = -1
		for v in values:
			if v > bestm and v < arr[i]:
				bestm = v
		smallest[i] = bestm
	return smallest


def Smallestonleft(arr, n):
	result = []
	s = set()
	for i in range(n):
		if i == 0:
			result.append(-1)
			s.add(arr[i])
		else:
			smaller_elements = sorted(list(s))
			j = len(smaller_elements) - 1
			while j >= 0:
				if smaller_elements[j] < arr[i]:
					result.append(smaller_elements[j])
					break
				j -= 1
			else:
				result.append(-1)
			s.add(arr[i])
	return result


def Smallestonleft(arr, n):
	s = []
	a = []
	a.append(-1)
	s.append(arr[0])
	for i in range(1, n):
		s = list(set(s))
		s.sort()
		if s[0] >= arr[i]:
			a.append(-1)
		else:
			for j in range(len(s) - 1, -1, -1):
				if s[j] < arr[i]:
					a.append(s[j])
					c = 1
					break
		s.append(arr[i])
	return a


def Smallestonleft(arr, n):
	stack = []
	for i in range(n):
		replacement_value = -1
		stack2 = []
		while stack and stack[-1] > arr[i]:
			stack2.append(stack.pop())
		if stack and stack[-1] == arr[i]:
			stack.pop()
		if stack:
			replacement_value = stack[-1]
		stack.append(arr[i])
		while stack2:
			stack.append(stack2.pop())
		arr[i] = replacement_value
	return arr


from bisect import *

def Smallestonleft(arr, n):
	l = []
	ans = []
	for num in arr:
		insort(l, num)
		j = bisect_left(l, num)
		if j == 0:
			ans.append(-1)
		else:
			ans.append(l[j - 1])
	return ans


from bisect import *

def Smallestonleft(a, n):
	l = []
	ans = []
	for i in range(n):
		l1 = bisect_right(l, -1 * a[i])
		if l1 == len(l):
			ans.append(-1)
		else:
			ans.append(l[l1] * -1)
		l.insert(l1, -1 * a[i])
	return ans


import bisect

def Smallestonleft(arr, n):
	temp = []
	res = []
	for i in range(n):
		bisect.insort(temp, arr[i])
		idx = bisect.bisect_left(temp, arr[i])
		if idx == 0:
			res.append(-1)
		else:
			res.append(temp[idx - 1])
	return res


from bisect import *
from sortedcontainers import SortedList, SortedSet, SortedDict
from bisect import bisect_left

def BinarySearch(a, x):
	i = bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def Smallestonleft(arr, n):
	res = [-1] * (n + 1)
	lst = []
	lst.append(arr[0])
	for i in range(1, n):
		idx = BinarySearch(lst, arr[i])
		if idx != -1:
			res[i] = lst[idx]
		lst.insert(idx + 1, arr[i])
	res.pop()
	return res


def Smallestonleft(arr, n):
	indexes = sorted(range(len(arr) - 1, -1, -1), key=arr.__getitem__)
	stack = []
	out = [-1] * len(arr)
	for i in indexes:
		while stack and i < stack[-1]:
			del stack[-1]
		if stack:
			out[i] = arr[stack[-1]]
		stack.append(i)
	return out


import bisect

def Smallestonleft(arr, n):
	solution = []
	arr1 = []
	for i in range(len(arr)):
		bisect.insort(arr1, arr[i])
		x = bisect.bisect_left(arr1, arr[i])
		if x == 0:
			solution.append(-1)
		else:
			solution.append(arr1[x - 1])
	return solution


import bisect

def Smallestonleft(arr, n):
	sorted_arr = []
	results = []
	for i in range(0, n):
		bisect.insort(sorted_arr, arr[i])
		left_index = bisect.bisect_left(sorted_arr, arr[i])
		if left_index == 0:
			results.append(-1)
		else:
			results.append(sorted_arr[left_index - 1])
	return results


import bisect

def Smallestonleft(a, n):
	s = [a[0]]
	r = [-1]
	for i in range(1, n):
		if a[i] > s[-1]:
			r.append(s[-1])
			s.append(a[i])
		else:
			x = bisect.bisect_left(s, a[i])
			if x == 0:
				r.append(-1)
			else:
				r.append(s[x - 1])
			s.insert(x, a[i])
	return r


import bisect

def Smallestonleft(arr, n):
	srt = [arr[0]]
	result = []
	for item in arr:
		if item <= srt[0]:
			result.append(-1)
			srt.insert(0, item)
		else:
			index = bisect.bisect_left(srt, item)
			result.append(srt[index - 1])
			srt.insert(index, item)
	return result


import bisect

def Smallestonleft(arr, n):
	length = len(arr)
	arr1 = [-1]
	stack = [arr[0]]
	count = 1
	minimum = arr[0]
	maximum = arr[0]
	for i in range(1, n):
		bisect.insort(stack, arr[i])
		left = bisect.bisect_left(stack, arr[i])
		if left == 0:
			arr1.append(-1)
		else:
			arr1.append(stack[left - 1])
		count += 1
	return arr1


import bisect

def Smallestonleft(arr, n):
	temp = []
	ans = []
	for i in range(n):
		bisect.insort(temp, arr[i])
		index_pos = bisect.bisect_left(temp, arr[i])
		if index_pos == 0:
			ans.append(-1)
		else:
			ans.append(temp[index_pos - 1])
	return ans


from bisect import bisect_left

def Smallestonleft(a, n):
	b = [-1] * n
	l = [a[0]]
	for i in range(1, n):
		j = bisect_left(l, a[i])
		if j:
			b[i] = l[j - 1]
		l.insert(j, a[i])
	return b


from collections import Counter

def Smallestonleft(arr, n):

	def _take_maxsmaller(v):
		(l, r) = (0, len(cnter) - 1)
		while l <= r:
			m = (l + r) // 2
			if cnter[m][0] < v:
				l = m + 1
			elif v < cnter[m][0]:
				r = m - 1
			else:
				i = m - 1
				cnter[m][1] -= 1
				if cnter[m][1] == 0:
					cnter.pop(m)
				if i >= 0:
					return cnter[i][0]
				else:
					return -1
	cnter = Counter(arr)
	cnter = [[v, cnt] for (v, cnt) in cnter.items()]
	cnter.sort(key=lambda x: x[0])
	ans = [-1] * n
	for i in range(n - 1, -1, -1):
		ans[i] = _take_maxsmaller(arr[i])
	return ans
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = Smallestonleft(arr, n)
	for each in res:
		print(each, end=' ')
	print()


from collections import Counter

def Smallestonleft(arr, n):

	def _take_maxsmaller(v):
		(l, r) = (0, M - 1)
		while l <= r:
			m = (l + r) // 2
			if cnter[m][0] < v:
				l = m + 1
			elif v < cnter[m][0]:
				r = m - 1
			else:
				cnter[m][1] -= 1
				i = m - 1
				while i >= 0 and cnter[i][1] == 0:
					i -= 1
				if i >= 0:
					return cnter[i][0]
				else:
					return -1
		raise ValueError("ain't be here")
	cnter = Counter(arr)
	cnter = [[v, cnt] for (v, cnt) in cnter.items()]
	cnter.sort(key=lambda x: x[0])
	M = len(cnter)
	ans = [-1] * n
	for i in range(n - 1, -1, -1):
		ans[i] = _take_maxsmaller(arr[i])
	return ans
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = Smallestonleft(arr, n)
	for each in res:
		print(each, end=' ')
	print()


from bisect import bisect_left, insort_left

def Smallestonleft(arr, n):
	a = []
	s = []
	for i in arr:
		if not s:
			insort_left(s, i)
			a.append(-1)
		else:
			b = bisect_left(s, i)
			if b:
				a.append(s[b - 1])
			else:
				a.append(-1)
			insort_left(s, i)
	return a
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = Smallestonleft(arr, n)
	for each in res:
		print(each, end=' ')
	print()


from bisect import bisect_left, insort_left

def Smallestonleft(arr, n):
	ans = []
	mp = []
	for i in arr:
		if not mp:
			insort_left(mp, i)
			ans.append(-1)
		else:
			x = bisect_left(mp, i)
			if x:
				ans.append(mp[x - 1])
			else:
				ans.append(-1)
			insort_left(mp, i)
	return ans
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = Smallestonleft(arr, n)
	for each in res:
		print(each, end=' ')
	print()


from bisect import bisect_left, insort_left

def Smallestonleft(arr, n):
	ans = []
	sarr = []
	for e in arr:
		if not sarr:
			insort_left(sarr, e)
			ans.append(-1)
		else:
			idx = bisect_left(sarr, e)
			if idx:
				ans.append(sarr[idx - 1])
			else:
				ans.append(-1)
			insort_left(sarr, e)
	return ans
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = Smallestonleft(arr, n)
	for each in res:
		print(each, end=' ')
	print()


def Smallestonleft(arr, n):
	from bisect import bisect_left

	def bs(arr, x):
		idx = bisect_left(arr, x)
		if idx:
			return idx - 1
		return -1
	res = [-1] * n
	ls = [arr[0]]
	for i in range(1, n):
		idx = bs(ls, arr[i])
		if idx != -1:
			res[i] = ls[idx]
		ls.insert(idx + 1, arr[i])
	return res
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = Smallestonleft(arr, n)
	for each in res:
		print(each, end=' ')
	print()


import bisect

def binary(l, a):
	i = bisect.bisect_left(l, a)
	return i - 1

def Smallestonleft(arr, n):
	sort_l = []
	sort_l.append(arr[0])
	res = [-1] * n
	i = 1
	while i < n:
		idx = binary(sort_l, arr[i])
		if idx != -1:
			res[i] = sort_l[idx]
		sort_l.insert(idx + 1, arr[i])
		i += 1
	return res


class Node:

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

def Smallestonleft(arr, n):

	def findNext(root, n):
		smaller = 10000000
		while True:
			if n <= root.data:
				if root.left:
					root = root.left
				else:
					root.left = Node(n)
					break
			else:
				smaller = root.data
				if root.right:
					root = root.right
				else:
					root.right = Node(n)
					break
		return smaller if smaller != 10000000 else -1
	ans = [-1]
	root = Node(arr[0])
	for i in range(1, n):
		el = arr[i]
		ans.append(findNext(root, el))
	return ans


from bisect import bisect_left, insort_left

def Smallestonleft(arr, n):
	(ans, brr) = ([], [])
	for i in arr:
		if not brr:
			insort_left(brr, i)
			ans.append(-1)
		else:
			ind = bisect_left(brr, i)
			if ind:
				ans.append(brr[ind - 1])
			else:
				ans.append(-1)
			insort_left(brr, i)
	return ans


from bisect import bisect_left

def Smallestonleft(arr, n):
	l = [arr[0]]
	res = [-1]
	for i in range(1, len(arr)):
		p = bisect_left(l, arr[i])
		if p == 0:
			res.append(-1)
		else:
			res.append(l[p - 1])
		l.insert(p, arr[i])
	return res


import bisect

def Smallestonleft(arr, n):
	temp_arr = [arr[0]]
	ans = [-1]
	for i in range(1, n):
		k = bisect.bisect_left(temp_arr, arr[i])
		if k == 0:
			ans.append(-1)
		else:
			ans.append(temp_arr[k - 1])
		bisect.insort_left(temp_arr, arr[i])
	return ans


def Smallestonleft(arr, n):
	idx = [i for i in range(n)]
	idx.sort(key=lambda i: arr[i])
	sol = [0 for _ in range(n)]
	for i in range(n):
		sol[idx[i]] = get_smaller(arr, n, idx, i)
	return sol

def get_smaller(arr, n, idx, i):
	for j in range(i - 1, -1, -1):
		if idx[j] < idx[i] and arr[idx[j]] < arr[idx[i]]:
			return arr[idx[j]]
	return -1


import bisect

def Smallestonleft(arr, n):
	ans = []
	ans1 = []
	for i in range(n):
		bisect.insort(ans, arr[i])
		j = bisect.bisect_left(ans, arr[i])
		if j == 0:
			ans1.append(-1)
		else:
			ans1.append(ans[j - 1])
	return ans1


from heapq import heappush, heappop
import bisect

def Smallestonleft(arr, n):
	ans = []
	st = []
	st.append(arr[0])
	ans.append(-1)
	for i in range(1, n):
		bisect.insort(st, arr[i])
		it = bisect.bisect_left(st, arr[i])
		if it:
			ans.append(st[it - 1])
		else:
			ans.append(-1)
	return ans