Given an array a of integers of length n, find the nearest smaller number for every element such that the smaller element is on left side.If no small element present on the left print -1.
Example 1:
Input: n = 3
a = {1, 6, 2}
Output: -1 1 1
Explaination: There is no number at the 
left of 1. Smaller number than 6 and 2 is 1.
Example 2:
Input: n = 6
a = {1, 5, 0, 3, 4, 5}
Output: -1 1 -1 0 3 4
Explaination: Upto 3 it is easy to see 
the smaller numbers. But for 4 the smaller 
numbers are 1, 0 and 3. But among them 3 
is closest. Similary for 5 it is 4.
Your Task:
You do not need to read input or print anything. Your task is to complete the function leftSmaller() which takes n and a as input parameters and returns the list of smaller numbers.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ n ≤ 10000
0 ≤ a[i] ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: # User function Template for Python3



class Solution:

    def leftSmaller(self, n, a):

        # code here

Solutions:
class Solution:

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


class Solution:

	def leftSmaller(self, n, arr):
		st = [arr[0]]
		ans = [-1 for i in range(n)]
		for i in range(1, n):
			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 leftSmaller(self, n, a):
		ans = []
		arr = a
		st = []
		for el in arr:
			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


class Solution:

	def leftSmaller(self, n, a):
		ans = []
		arr = a
		for i in range(n):
			flag = True
			for j in range(i - 1, -1, -1):
				if arr[j] < arr[i]:
					ans.append(arr[j])
					flag = False
					break
			if flag:
				ans.append(-1)
		return ans


class Solution:

	def leftSmaller(self, n, arr):
		stack = [-1]
		ans = []
		for elm in arr:
			while len(stack) > 1 and stack[-1] >= elm:
				stack.pop()
			ans.append(stack[-1])
			stack.append(elm)
		return ans


class Solution:

	def leftSmaller(self, n, a):
		stack = []
		ans = []
		for cur in a:
			while stack and cur <= stack[-1]:
				stack.pop()
			if stack:
				ans.append(stack[-1])
			else:
				ans.append(-1)
			stack.append(cur)
		return ans


class Solution:

	def leftSmaller(self, n, a):
		stack = []
		ans = []
		for cur in a:
			if not stack:
				ans.append(-1)
			else:
				flag = True
				while stack:
					if stack[-1] < cur:
						ans.append(stack[-1])
						flag = False
						break
					stack.pop()
				if flag:
					ans.append(-1)
			stack.append(cur)
		return ans


class Solution:

	def leftSmaller(self, n, a):
		arr = [-1] * n
		nums = a[::-1]
		stk = [0]
		for i in range(1, n):
			while stk and nums[i] < nums[stk[-1]]:
				arr[stk.pop()] = nums[i]
			stk.append(i)
		return arr[::-1]


class Solution:

	def leftSmaller(self, n, a):
		stack = []
		ans = []
		for i in range(n):
			while stack and a[i] <= stack[-1]:
				stack.pop()
			if not stack:
				ans.append(-1)
			else:
				ans.append(stack[-1])
			stack.append(a[i])
		return ans


class Solution:

	def leftSmaller(self, n, a):
		ans = []
		st = [-1]
		for i in range(0, n):
			while st[-1] != -1 and st[-1] >= a[i]:
				st.pop()
			ans.append(st[-1])
			st.append(a[i])
		return ans


class Solution:

	def leftSmaller(self, n, nums):
		q = []
		NG = []
		for i in range(0, n):
			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


class Solution:

	def leftSmaller(self, n, a):
		stack = []
		res = []
		for ele in a:
			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


class Solution:

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


class Solution:

	def leftSmaller(self, n, a):
		stack = [-1]
		res = []
		for cur in a:
			while stack and cur <= stack[-1]:
				stack.pop()
			res.append(stack[-1])
			stack.append(cur)
		return res


class Solution:

	def leftSmaller(self, n, a):
		stack = [-1]
		for i in range(1, n):
			for j in range(i - 1, -1, -1):
				if a[j] < a[i]:
					stack.append(a[j])
					break
			else:
				stack.append(-1)
		return stack


import sys

class Solution:

	def leftSmaller(self, n, a):
		l = []
		stack = []
		for i in range(0, len(a)):
			if len(stack) == 0:
				l.append(-1)
			elif a[i] > stack[-1]:
				l.append(stack[-1])
			elif len(stack) > 0 and a[i] <= stack[-1]:
				while len(stack) > 0 and a[i] <= stack[-1]:
					stack.pop()
				if len(stack) == 0:
					l.append(-1)
				elif len(stack) > 0:
					l.append(stack[-1])
			stack.append(a[i])
		return l


class Solution:

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


class Solution:

	def leftSmaller(self, n, a):
		stack = []
		ans = []
		for i in range(n):
			while True:
				if stack == []:
					ans.append(-1)
					stack.append(a[i])
					break
				if a[i] > stack[-1]:
					ans.append(stack[-1])
					stack.append(a[i])
					break
				else:
					stack.pop()
		return ans


class Solution:

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


class Solution:

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


class Solution:

	def leftSmaller(self, n, a):
		s = []
		res = []
		for i in a:
			if len(s) == 0:
				res.append(-1)
			elif s[-1] < i:
				res.append(s[-1])
			else:
				while len(s) != 0 and s[-1] >= i:
					s.pop()
					if len(s) == 0:
						res.append(-1)
					elif s[-1] < i:
						res.append(s[-1])
						break
			s.append(i)
		return res


class Solution:

	def leftSmaller(self, n, a):
		lst = [-1]
		ind = [-1]
		for i in range(1, n):
			if a[i] > a[i - 1]:
				lst.append(a[i - 1])
				ind.append(i - 1)
			else:
				j = i - 1
				while j != -1 and a[i] <= a[j]:
					j = ind[j]
				if j == -1:
					lst.append(-1)
					ind.append(-1)
				else:
					lst.append(a[j])
					ind.append(j)
		return lst


class Solution:

	def leftSmaller(self, n, a):
		stack = []
		a.reverse()
		ans = [-1] * n
		for (idx, x) in enumerate(a):
			if len(stack) == 0:
				stack.append((idx, x))
			while stack and x < stack[-1][1]:
				(_idx, _) = stack.pop()
				ans[_idx] = x
			stack.append((idx, x))
		return reversed(ans)


class Solution:

	def leftSmaller(self, n, a):
		stack = []
		answer = []
		for i in range(0, n, 1):
			while stack and stack[-1] >= a[i]:
				stack.pop()
			answer.append(stack[-1] if stack else -1)
			stack.append(a[i])
		return answer


class Solution:

	def leftSmaller(self, n, a):
		st = []
		res = [0] * n
		for i in range(n):
			while st and st[-1] >= a[i]:
				st.pop()
			if st:
				res[i] = st[-1]
			else:
				res[i] = -1
			st.append(a[i])
		return res


from collections import deque

class Solution:

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


class Solution:

	def leftSmaller(self, n, a):
		list = [-1]
		for i in range(1, n):
			k = i - 1
			while k != -1:
				if a[k] < a[i]:
					list.append(a[k])
					break
				k = k - 1
			else:
				list.append(-1)
		return list


from collections import deque

class Solution:

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


class Solution:

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


class Solution:

	def leftSmaller(self, n, a):
		ans = list((-1 for _ in range(n)))
		s = [a[0]]
		for i in range(1, n):
			while len(s) > 0 and s[-1] >= a[i]:
				s.pop()
			if len(s) == 0:
				ans[i] = -1
			else:
				ans[i] = s[-1]
			s.append(a[i])
		return ans


class Solution:

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


class Solution:

	def leftSmaller(self, n, a):
		stack = []
		res = []
		for i in a:
			while stack:
				if stack[-1] < i:
					res.append(stack[-1])
					break
				else:
					stack.pop()
			if not stack:
				res.append(-1)
			stack.append(i)
		return res


class Solution:

	def leftSmaller(self, n, a):
		st = []
		v = []
		st.append(-1)
		for i in range(n):
			curr = a[i]
			while curr <= st[-1]:
				st.pop()
			v.append(st[-1])
			st.append(curr)
		return v


class Solution:

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


class Solution:

	def leftSmaller(self, n, a):
		a.reverse()
		arr = a
		sta = []
		ans = []
		i = n - 1
		ls = 0
		while i >= 0:
			if ls == 0:
				ans.append(-1)
				sta.append(arr[i])
				ls += 1
			else:
				while True:
					if ls == 0:
						ans.append(-1)
						sta.append(arr[i])
						ls += 1
						break
					elif ls > 0 and sta[-1] < arr[i]:
						ans.append(sta[-1])
						sta.append(arr[i])
						ls += 1
						break
					else:
						ls -= 1
						sta.pop()
			i -= 1
		return ans


class Solution:

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


class Solution:

	def leftSmaller(self, n, a):
		l = []
		l.append(-1)
		for i in range(1, n):
			b = i
			while True:
				if b < 0:
					l.append(-1)
					break
				if a[i] > a[b]:
					l.append(a[b])
					break
				b -= 1
		return l


class Solution:

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


from collections import deque

class Solution:

	def leftSmaller(self, n, a):
		ans = []
		stack = deque()
		stack.append(-1)
		i = 0
		while i < n:
			if a[i] > stack[-1]:
				ans.append(stack[-1])
				stack.append(a[i])
				i += 1
				continue
			else:
				stack.pop()
		return ans


class Solution:

	def leftSmaller(self, n, a):
		ans = [-1] * n
		for i in range(1, n):
			for j in range(i - 1, -1, -1):
				if a[j] < a[i]:
					ans[i] = a[j]
					break
		return ans


class Solution:

	def leftSmaller(self, n, a):
		a.reverse()
		stack = []
		res = [-1] * n
		for (idx, i) in enumerate(a):
			while stack and i < a[stack[-1]]:
				res[stack.pop()] = i
			stack.append(idx)
		return res[::-1]


from collections import deque

class Solution:

	def leftSmaller(self, n, a):
		stack = deque()
		result = [-1] * n
		for i in range(n):
			if stack and stack[-1] < a[i]:
				result[i] = stack[-1]
			elif stack and stack[-1] >= a[i]:
				while stack and stack[-1] >= a[i]:
					stack.pop()
				if stack:
					result[i] = stack[-1]
			stack.append(a[i])
		return result


class Solution:

	def leftSmaller(self, n, a):
		stack = []
		ans = []
		for i in a:
			while len(stack) != 0:
				temp = stack.pop()
				if temp < i:
					ans.append(temp)
					stack.append(temp)
					stack.append(i)
					break
			if len(stack) == 0:
				ans.append(-1)
				stack.append(i)
		return ans


class Solution:

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


class Solution:

	def leftSmaller(self, n, a):
		stack = []
		sol = []
		for el in a:
			while stack and stack[-1] >= el:
				stack.pop()
			if not stack:
				sol.append(-1)
			else:
				sol.append(stack[-1])
			stack.append(el)
		return sol


class Solution:

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


import math

class Solution:

	def leftSmaller(self, n, a):
		stack = []
		ans = []
		for i in a:
			while len(stack) != 0:
				t = stack.pop()
				if t < i:
					ans.append(t)
					stack.append(t)
					stack.append(i)
					break
			if len(stack) == 0:
				ans.append(-1)
				stack.append(i)
		return ans


class Solution:

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


class Solution:

	def leftSmaller(self, n, a):
		arr = [-1] * len(a)
		st = []
		for i in range(len(a)):
			if not st:
				st.append(a[i])
				continue
			if st[-1] < a[i]:
				arr[i] = st[-1]
			else:
				while st and st[-1] >= a[i]:
					st.pop()
			if st:
				arr[i] = st[-1]
			st.append(a[i])
		arr[0] = -1
		return arr


from collections import deque

class Solution:

	def leftSmaller(self, n, a):
		st = list()
		res = []
		for i in range(n):
			while len(st) != 0 and a[i] <= st[-1]:
				st.pop()
			if len(st) == 0:
				res.append(-1)
			else:
				res.append(st[-1])
			st.append(a[i])
		return res


class Solution:

	def leftSmaller(self, n, a):
		a = a[::-1]
		stack = []
		final = [-1 for i in range(len(a))]
		i = 0
		while i < len(a):
			if len(stack) == 0:
				p = []
				p.append(a[i])
				p.append(i)
				stack.append(p)
				i = i + 1
			elif stack[-1][0] > a[i]:
				final[stack[-1][1]] = a[i]
				stack.pop()
			else:
				stack.append([a[i], i])
				i = i + 1
		return final[::-1]


class Solution:

	def leftSmaller(self, n, a):
		res = [-1]
		s = [a[0]]
		for i in range(1, n):
			while s:
				if s[-1] < a[i]:
					res.append(s[-1])
					break
				else:
					s.pop()
			if not s:
				res.append(-1)
			s.append(a[i])
		return res


import math

class Solution:

	def leftSmaller(self, n, a):
		st = []
		r_res = []
		for i in a:
			while len(st) != 0:
				temp = st.pop()
				if temp < i:
					r_res.append(temp)
					st.append(temp)
					st.append(i)
					break
			if len(st) == 0:
				r_res.append(-1)
				st.append(i)
		return r_res