Given an array Arr[] of size N. For every element in the array, the task is to find the index of the farthest element in the array to the right which is smaller than the current element. If no such number exists then print -1.
Note: 0 based indexing.
Example 1:
Input: 
N=5
Arr[] = {3, 1, 5, 2, 4}
Output: 
3 -1 4 -1 -1
Explanation:
Arr[3] is the farthest smallest element
to the right of Arr[0].
Arr[4] is the farthest smallest element
to the right of Arr[2].
And for the rest of the elements, there is
no smaller element to their right.
Example 2:
Input: 
N=5
Arr[] = {1, 2, 3, 4, 0}
Output: 
4 4 4 4 -1
Your Task: 
You don't need to read input or print anything. Your task is to complete the function farNumber() which takes the N (number of elements in Array Arr) ,Arr[], and returns the array of farthest element to the right for every element of the array.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)
Constraints:
1  ≤  N ≤  1e5
0 ≤  Arr[i] ≤  1e9

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def farNumber(self,N,Arr):

        #code here

Solutions:
class Solution:

	def farNumber(self, n, a):
		l = []
		res = [-1] * n
		for i in range(n):
			l.append([a[i], i])
		l.sort()
		mind = None
		for i in range(n):
			if mind == None or mind < l[i][1]:
				mind = l[i][1]
			else:
				res[l[i][1]] = mind
		return res


import bisect

class Solution:

	def farNumber(self, N, Arr):
		a = [(Arr[i], i) for i in range(N)]
		a = sorted(a, key=lambda x: (x[0], x[1]))
		r = N - 1
		ans = [-1] * N
		for i in range(N - 1, -1, -1):
			idx = bisect.bisect_right(a, (Arr[i], i))
			for j in range(idx, r + 1):
				ans[a[j][1]] = i
			r = min(r, idx - 2)
		return ans


class Solution:

	def farNumber(self, n, arr):
		arr2 = sorted(enumerate(arr), key=lambda x: [x[1], x[0]])
		list1 = [0] * n
		list1[arr2[0][0]] = -1
		index_max = arr2[0][0]
		for i in range(1, n):
			if arr2[i][0] > index_max:
				list1[arr2[i][0]] = -1
				index_max = arr2[i][0]
			else:
				list1[arr2[i][0]] = index_max
		return list1


from bisect import bisect_left as bl

class Solution:

	def farNumber(self, n, a):
		b = [a[-1]]
		for i in range(n - 2, -1, -1):
			b.append(min(a[i], b[-1]))
		ans = []
		b.reverse()
		for i in range(n):
			k = bl(b, a[i], i + 1)
			k -= 1
			if k <= i:
				ans.append(-1)
			else:
				ans.append(k)
		return ans


from bisect import bisect_left

class Solution:

	def farNumber(self, N, arr):
		output = []
		brr = []
		store = {}
		brr.append(arr[-1])
		store[arr[-1]] = N - 1
		for i in range(N - 1, -1, -1):
			j = bisect_left(brr, arr[i])
			if j == 0:
				output.append(-1)
			else:
				output.append(store[brr[j - 1]])
			if arr[i] < brr[0]:
				brr.insert(0, arr[i])
				store[arr[i]] = i
		return output[::-1]


from bisect import bisect_left as bl

class Solution:

	def farNumber(self, n, a):
		ans = [-1] * n
		suff = [0] * n
		suff[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			suff[i] = min(a[i], suff[i + 1])
		for i in range(n - 1):
			j = bl(suff, a[i], i + 1)
			if j and suff[j - 1] < a[i]:
				ans[i] = j - 1
			else:
				pass
		return ans


class Solution:

	def farNumber(self, n, a):
		ans = [-1] * n
		suff = [0] * n
		suff[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			suff[i] = min(a[i], suff[i + 1])
		for i in range(n):
			ind = -1
			low = i + 1
			high = n - 1
			while low <= high:
				mid = (high + low) // 2
				if suff[mid] < a[i]:
					ind = mid
					low = mid + 1
				else:
					high = mid - 1
			ans[i] = ind
		return ans


class Solution:

	def farNumber(self, n, arr):
		sf = [0 for i in range(n)]
		sf[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			sf[i] = min(sf[i + 1], arr[i])
		ans = []
		for i in range(n):
			l = i + 1
			h = n - 1
			val = -1
			while l <= h:
				mid = (l + h) // 2
				if sf[mid] < arr[i]:
					val = mid
					l = mid + 1
				else:
					h = mid - 1
			ans.append(val)
		return ans


class Solution:

	def findLower(self, searchArray, ele, N, i):
		n = len(searchArray)
		l = i + 1
		r = n - 1
		val = -1
		while l <= r:
			m = (l + r) // 2
			if searchArray[m] < ele:
				val = m
				l = m + 1
			else:
				r = m - 1
		return val

	def farNumber(self, N, arr):
		(minArray, res) = ([0] * N, [-1] * N)
		res[-1] = -1
		(minArray[-1], minEle) = (arr[-1], arr[-1])
		for i in range(N - 2, -1, -1):
			if arr[i] < minEle:
				minEle = arr[i]
				res[i] = -1
			else:
				res[i] = self.findLower(minArray, arr[i], N, i)
			minArray[i] = minEle
		return res


from bisect import bisect_left

class Solution:

	def min_heap(self, stack, val):
		stack.append(val)
		n = len(stack)
		for i in range(n - 1, 0, -1):
			if stack[i][0] < stack[i - 1][0]:
				(stack[i][0], stack[i - 1][0]) = (stack[i - 1][0], stack[i][0])
			else:
				break

	def farNumber(self, n, arr):
		arr2 = sorted(enumerate(arr), key=lambda x: [x[1], x[0]])
		list1 = [0] * n
		list1[arr2[0][0]] = -1
		index_max = arr2[0][0]
		for i in range(1, n):
			if arr2[i][0] > index_max:
				list1[arr2[i][0]] = -1
				index_max = arr2[i][0]
			else:
				list1[arr2[i][0]] = index_max
		return list1


from bisect import bisect_left

class Solution:

	def farNumber(self, N, Arr):
		ans = [-1] * N
		suff = [0] * N
		suff[N - 1] = Arr[N - 1]
		for i in range(N - 2, -1, -1):
			suff[i] = min(Arr[i], suff[i + 1])
		for i in range(N - 1):
			j = bisect_left(suff, Arr[i], i + 1)
			if j and suff[j - 1] < Arr[i]:
				ans[i] = j - 1
		return ans


class Solution:

	def farNumber(self, N, Arr):
		ref = [0] * N
		ref[N - 1] = Arr[N - 1]
		for i in range(N - 2, -1, -1):
			ref[i] = min(Arr[i], ref[i + 1])
		res = []
		for i in range(N):
			low = i + 1
			high = N - 1
			ans = -1
			while low <= high:
				mid = (low + high) // 2
				if Arr[i] <= ref[mid]:
					high = mid - 1
				else:
					ans = mid
					low = mid + 1
			res.append(ans)
		return res


class Solution:

	def farNumber(self, n, a):
		pref = [0] * n
		pref[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			pref[i] = min(a[i], pref[i + 1])
		res = []
		for i in range(n):
			low = i + 1
			high = n - 1
			ans = -1
			while low <= high:
				mid = (low + high) // 2
				if a[i] <= pref[mid]:
					high = mid - 1
				else:
					ans = mid
					low = mid + 1
			res.append(ans)
		return res


class Solution:

	def farNumber(self, N, Arr):
		n = N
		a = Arr
		l = []
		suffix_min = [0 for i in range(n)]
		suffix_min[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			suffix_min[i] = min(suffix_min[i + 1], a[i])
		for i in range(n):
			low = i + 1
			high = n - 1
			ans = -1
			while low <= high:
				mid = (low + high) // 2
				if suffix_min[mid] < a[i]:
					ans = mid
					low = mid + 1
				else:
					high = mid - 1
			l.append(ans)
		return l


class Solution:

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

	def farNumber(self, N, Arr):
		suffixmin = [0] * N
		suffixmin[N - 1] = Arr[N - 1]
		for i in range(N - 2, -1, -1):
			suffixmin[i] = min(suffixmin[i + 1], Arr[i])
		res = []
		for i in range(N):
			l = self.binarysearch(suffixmin, i + 1, N - 1, Arr[i])
			if l <= i:
				res.append(-1)
			else:
				res.append(l)
		return res


class Solution:

	def farNumber(self, N, Arr):
		new = [-1] * N
		suf = [float('inf')] * N
		suf[N - 1] = Arr[N - 1]
		p = N - 1
		mins = float('inf')
		while p >= 0:
			mins = min(mins, Arr[p])
			suf[p] = mins
			p -= 1
		for i in range(N - 2, -1, -1):
			l = i + 1
			r = N - 1
			while l <= r:
				m = (l + r) // 2
				if suf[m] < Arr[i]:
					new[i] = m
					l = m + 1
				else:
					r = m - 1
		return new


class Solution:

	def farNumber(self, N, A):
		st = []
		size = 0
		ans = [-1] * N
		for i in range(N - 1, -1, -1):
			s = 0
			e = size - 1
			while s <= e:
				mid = (s + e) // 2
				if A[st[mid]] >= A[i]:
					s = mid + 1
				else:
					ans[i] = st[mid]
					e = mid - 1
			if ans[i] == -1:
				st.append(i)
				size += 1
		return ans


def bs(A, key, l, r):
	ans = -1
	while l <= r:
		mid = l + (r - l >> 1)
		if A[mid] < key:
			ans = mid
			l = mid + 1
		else:
			r = mid - 1
	return ans

class Solution:

	def farNumber(self, N, A):
		suff = [0] * N
		suff[-1] = A[-1]
		for i in range(N - 2, -1, -1):
			suff[i] = min(A[i], suff[i + 1])
		ans = [0] * N
		ans[-1] = -1
		for i in range(N - 2, -1, -1):
			ix = bs(suff, A[i], i, N - 1)
			ans[i] = ix
		return ans


class Solution:

	def farNumber(self, N, Arr):

		def binary_search(l, h, x):
			ans = -1
			while l <= h:
				mid = (l + h) // 2
				if suf[mid] < x:
					ans = mid
					l = mid + 1
				else:
					h = mid - 1
			return ans
		suf = [-1] * N
		suf[-1] = Arr[-1]
		for i in range(N - 2, -1, -1):
			suf[i] = min(suf[i + 1], Arr[i])
		res = []
		for i in range(N - 1):
			res.append(binary_search(i + 1, N - 1, Arr[i]))
		res.append(-1)
		return res


class Solution:

	def farNumber(self, N, Arr):
		mi = [0] * N
		mi[N - 1] = Arr[N - 1]
		for i in range(N - 2, -1, -1):
			mi[i] = min(mi[i + 1], Arr[i])
		ans = []
		for i in range(N):
			l = i + 1
			r = N - 1
			a = -1
			while l <= r:
				mid = (l + r) // 2
				if Arr[i] > mi[mid]:
					a = mid
					l = mid + 1
				else:
					r = mid - 1
			ans.append(a)
		return ans


class Solution:

	def farNumber(self, N, Arr):
		temp = []
		i = 0
		ans = []
		while i < N:
			j = N - 1
			while j >= 0 and j > i and (Arr[j] >= Arr[i]):
				j -= 1
			if i != j:
				ans.append(j)
			else:
				ans.append(-1)
			i += 1
		return ans


class Solution:

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


class Solution:

	def farNumber(self, N, Arr):
		suff = [0] * N
		suff[N - 1] = Arr[N - 1]
		minn = Arr[N - 1]
		for i in range(N - 2, -1, -1):
			minn = min(minn, Arr[i])
			suff[i] = minn
		li = []
		for i in range(N):
			low = i + 1
			high = N - 1
			ans = -1
			while low <= high:
				mid = low + high >> 1
				if suff[mid] < Arr[i]:
					ans = mid
					low = mid + 1
				else:
					high = mid - 1
			li.append(ans)
		return li


class Solution:

	def farNumber(self, N, Arr):
		ans = [-1] * N
		for i in range(N):
			found = 0
			for j in range(N - 1, i, -1):
				if Arr[j] < Arr[i]:
					found = 1
					ans[i] = j
					break
		return ans


class Solution:

	def farNumber(self, N, Arr):
		r = Arr[::-1]
		b = [-1] * N
		for i in range(len(Arr)):
			for j in range(len(Arr) - 1, i, -1):
				if Arr[j] < Arr[i]:
					b[i] = j
					break
		return b


class Solution:

	def farNumber(self, n, arr):
		i = 0
		a = [-1] * n
		j = n - 1
		for i in range(n):
			while j > i:
				if arr[i] > arr[j]:
					a[i] = j
					break
				else:
					j -= 1
			j = n - 1
		return a


class Solution:

	def farNumber(self, N, Arr):
		l = []
		for i in range(N - 1):
			c = 0
			for j in range(N - 1, i, -1):
				if Arr[j] < Arr[i]:
					l.append(j)
					c = 1
					break
			if c == 0:
				l.append(-1)
		l.append(-1)
		return l


class Solution:

	def farNumber(self, N, Arr):
		lst = [-1] * N
		for i in range(N):
			for j in range(N - 1, i, -1):
				if Arr[j] < Arr[i]:
					lst[i] = j
					break
		return lst


class Solution:

	def farNumber(self, N, Arr):
		res = []
		j = N - 1
		track = 0
		for i in range(N):
			for j in range(N - 1, i, -1):
				if Arr[i] > Arr[j]:
					res.append(j)
					track = 1
					break
			if track == 0:
				res.append(-1)
			track = 0
		return res


class Solution:

	def farNumber(self, N, Arr):
		out = []
		for lp in range(len(Arr)):
			rp = len(Arr) - 1
			flag = 0
			while rp > lp:
				if Arr[lp] > Arr[rp]:
					out.append(rp)
					flag = 1
					break
				rp -= 1
			if flag == 0:
				out.append(-1)
		return out


class Solution:

	def farNumber(self, N, Arr):
		lista = [-1] * N
		for i in range(N):
			cn = 0
			j = N - 1
			flag = 0
			while j > i and flag != 1:
				if Arr[j] < Arr[i] and j >= cn:
					cn = j
					lista[i] = cn
					flag = 1
				else:
					j = j - 1
		return lista


from bisect import bisect_left
import sys

class Solution:

	def farNumber(self, N, Arr):
		i = N - 2
		max_ = sys.maxsize
		suff = [Arr[-1]] * N
		while i >= 0:
			suff[i] = min(Arr[i], suff[i + 1])
			i -= 1
		res = []
		for i in range(N):
			ele = Arr[i]
			if ele <= suff[i]:
				res.append(-1)
				continue
			idx = bisect_left(suff, ele, i + 1)
			res.append(idx - 1)
		return res


from bisect import bisect_left
import sys

class Solution:

	def farNumber(self, N, Arr):
		i = N - 2
		m = sys.maxsize
		s = [Arr[-1]] * N
		while i >= 0:
			s[i] = min(Arr[i], s[i + 1])
			i -= 1
		res = []
		for i in range(N):
			e = Arr[i]
			if e <= s[i]:
				res.append(-1)
				continue
			index = bisect_left(s, e, i + 1)
			res.append(index - 1)
		return res


class Solution:

	def farNumber(self, N, Arr):
		for i in range(len(Arr)):
			flag = 0
			for j in reversed(range(len(Arr))):
				if Arr[i] > Arr[j] and i < j:
					Arr[i] = j
					flag = 1
					break
			if flag == 0:
				Arr[i] = -1
		return Arr


class Solution:

	def farNumber(self, N, Arr):
		result = []
		for ind in range(0, N):
			j = N - 1
			while j > ind:
				if Arr[j] < Arr[ind]:
					result.append(j)
					break
				j -= 1
			if ind == j:
				result.append(-1)
		return result


class Solution:

	def farNumber(self, N, Arr):
		x = []
		for i in range(N):
			c = 0
			for j in reversed(range(i, N)):
				if Arr[j] < Arr[i]:
					c = 1
					x.append(j)
					break
			if c == 1:
				pass
			else:
				x.append(-1)
		return x


class Solution:

	def farNumber(self, N, Arr):
		post = [Arr[-1] for _ in range(N)]
		for i in range(N - 2, -1, -1):
			post[i] = min(post[i + 1], Arr[i])
		res = []
		for i in range(N - 1):
			tar = Arr[i]
			l = i + 1
			r = N - 1
			while l <= r:
				m = l + (r - l) // 2
				if post[m] < tar:
					l = m + 1
				else:
					r = m - 1
			if i + 1 <= r <= N - 1:
				res.append(r)
			else:
				res.append(-1)
		res.append(-1)
		return res


class Solution:

	def farNumber(self, n, arr):
		res = []
		for i in range(n):
			for j in range(n - 1, i - 1, -1):
				if arr[i] > arr[j]:
					res.append(j)
					break
			else:
				res.append(-1)
		return res


def check(arr, element, i, j):
	j -= 1
	while i != j:
		if element > arr[j]:
			return j
		else:
			j -= 1
	return -1

class Solution:

	def farNumber(self, N, arr):
		ans = []
		for i in range(N):
			ans.append(check(arr, arr[i], i, N))
		return ans


class Solution:

	def farNumber(self, N, Arr):
		ans = []
		for i in range(0, N - 1):
			sm = -1
			se = Arr[i]
			for j in range(N - 1, i, -1):
				if Arr[j] < se:
					sm = j
					break
			ans.append(sm)
		ans.append(-1)
		return ans


class Solution:

	def farNumber(self, N, Arr):
		suffix_min = [float('inf')] * N
		ans = [-1] * N
		for idx in range(N - 1, -1, -1):
			if idx + 1 < N:
				suffix_min[idx] = min(suffix_min[idx + 1], Arr[idx])
			else:
				suffix_min[idx] = Arr[idx]
		for idx in range(N):
			low = idx + 1
			high = N - 1
			while low <= high:
				mid = (low + high) // 2
				if suffix_min[mid] < Arr[idx]:
					ans[idx] = mid
					low = mid + 1
				else:
					high = mid - 1
		return ans


class Solution:

	def farNumber(self, N, arr):
		array = [-1] * N
		for i in range(N):
			for j in range(N - 1, i, -1):
				if arr[j] < arr[i]:
					array[i] = j
					break
		return array


class Solution:

	def SuffixArrayOfMin(self, arr):
		suffix_arr = [0] * len(arr)
		suffix_arr[-1] = arr[-1]
		for i in range(len(arr) - 1, 0, -1):
			suffix_arr[i - 1] = min(arr[i - 1], suffix_arr[i])
		return suffix_arr

	def BinarySearchInSuffixArray(self, arr):
		result = []
		suffix_arr = self.SuffixArrayOfMin(arr)
		for i in range(len(arr)):
			start = i + 1
			end = len(arr) - 1
			ans = -1
			while start <= end:
				mid = (start + end) // 2
				if suffix_arr[mid] < arr[i]:
					ans = mid
					start = mid + 1
				else:
					end = mid - 1
			result.append(ans)
		return result

	def farNumber(self, N, Arr):
		return self.BinarySearchInSuffixArray(Arr)


class Solution:

	def farNumber(self, n, nums):
		suffix_min = [0] * n
		suffix_min[n - 1] = nums[n - 1]
		for i in range(n - 2, -1, -1):
			suffix_min[i] = min(suffix_min[i + 1], nums[i])
		result = []
		for i in range(n):
			ans = -1
			l = i + 1
			r = n - 1
			while l <= r:
				mid = l + (r - l) // 2
				if suffix_min[mid] < nums[i]:
					ans = mid
					l = mid + 1
				else:
					r = mid - 1
			result.append(ans)
		return result


class Solution:

	def farNumber(self, n, nums):
		pair = []
		for i in range(n):
			pair.append([nums[i], i])
		pair.sort()
		pair[0][0] = -1
		k = pair[0][1]
		for i in range(n):
			if pair[i][1] < k:
				pair[i][0] = k
			else:
				pair[i][0] = -1
				k = pair[i][1]
		for i in range(n):
			nums[pair[i][1]] = pair[i][0]
		return nums


class Solution:

	def farNumber(self, n, arr):
		ans = []
		for i in range(n):
			check = -1
			for j in range(n - 1, i - 1, -1):
				if arr[j] < arr[i]:
					ans.append(j)
					check = 1
					break
			if check < 0:
				ans.append(-1)
		return ans


class Solution:

	def farNumber(self, N, Arr):
		b = []
		for i in range(N):
			q = Arr[i]
			x = 0
			for j in range(N - 1, i, -1):
				if Arr[j] < q:
					b.append(j)
					x = 1
					break
			if x == 0:
				b.append(-1)
		return b


class Solution:

	def farNumber(self, n, a):
		l = []
		for i in range(n):
			flag = 0
			for j in range(n - 1, i, -1):
				if a[j] < a[i]:
					flag = 1
					l.append(j)
					break
			if flag == 0:
				l.append(-1)
		return l


class Solution:

	def farNumber(self, N, Arr):
		l = []
		x = 0
		m = 0
		for i in range(N):
			x = N - 1
			m = 0
			while x > i:
				if Arr[i] > Arr[x]:
					l.append(x)
					m = 1
					break
				x = x - 1
			if m == 0:
				l.append(-1)
		return l


class Solution:

	def farNumber(self, N, Arr):
		ans = []
		for i in range(N):
			first_num = Arr[i]
			target = -1
			for j in range(N - 1, i, -1):
				if Arr[j] < first_num:
					target = j
					break
			ans.append(target)
		return ans


class Solution:

	def farNumber(self, N, Arr):
		r = 0
		l = N - 1
		while r < N:
			if r == l:
				Arr[r] = -1
				l = N - 1
				r = r + 1
			elif Arr[r] > Arr[l]:
				Arr[r] = l
				l = N - 1
				r = r + 1
			else:
				l = l - 1
		return Arr


class Solution:

	def farNumber(self, N, Arr):
		arr = list(enumerate(Arr))
		arr = sorted(arr, key=lambda x: x[1])
		ans = [-1] * len(Arr)
		maxi = -1
		for (i, num) in arr:
			if maxi > i:
				ans[i] = maxi
			else:
				maxi = i
		return ans