Given an array arr[] of n positive integers. The task is to find the maximum of j - i subjected to the constraint of arr[i] <= arr[j].
Example 1:
Input:
n = 9
arr[] = {34, 8, 10, 3, 2, 80, 30, 33, 1}
Output: 
6
Explanation: 
In the given array arr[1] < arr[7]  satisfying 
the required condition (arr[i] <= arr[j])  thus 
giving the maximum difference of j - i which is
6(7-1).
Example 2:
Input:
N = 2
arr[] = {18, 17}
Output: 
0
Explanation: 
We can either take i and j as 0 and 0 
or we cantake 1 and 1 both give the same result 0.
Your Task:
Complete the function maxIndexDiff() which takes array arr and size n, as input parameters and returns an integer representing the answer. You don't to print answer or take inputs. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{6}
0 ≤ Arr[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3
class Solution:

	def maxIndexDiff(self,arr,n):
		#code here

Solutions:
class Solution:

	def maxIndexDiff(self, arr, n):
		m = -100000
		for i in range(n):
			j = n - 1
			while i < j and arr[i] > arr[j]:
				j -= 1
			m = max(m, j - i)
		return m


class Solution:

	def maxIndexDiff(self, arr, n):
		ans = 0
		i = 0
		j = n - 1
		while i <= j:
			if arr[i] <= arr[j]:
				ans = max(ans, j - i)
				i += 1
				j = n - 1
			else:
				j -= 1
		return ans


class Solution:

	def maxIndexDiff(self, arr, n):
		left = [0] * n
		right = [0] * n
		left[0] = arr[0]
		for i in range(1, n):
			left[i] = min(left[i - 1], arr[i])
		right[n - 1] = arr[n - 1]
		for j in range(n - 2, -1, -1):
			right[j] = max(right[j + 1], arr[j])
		maxdiff = -1
		i = 0
		j = 0
		while j < n and i < n:
			if left[i] <= right[j]:
				maxdiff = max(maxdiff, j - i)
				j += 1
			else:
				i += 1
		return maxdiff


class Solution:

	def maxIndexDiff(self, arr, n):
		mx = 0
		current_mx = 0
		for index in range(n):
			start = n - 1
			while start > index and arr[index] > arr[start]:
				start -= 1
			current_mx = start - index
			mx = max(mx, current_mx)
		return mx


class Solution:

	def maxIndexDiff(self, arr, n):
		st = []
		n = len(arr)
		max = -1
		res = 0
		for j in range(n - 1, -1, -1):
			if arr[j] > max:
				max = arr[j]
				st.append(j)
		i = 0
		while i < n and st:
			while st and arr[i] <= arr[st[-1]]:
				j = st.pop()
				if j - i > res:
					res = j - i
			i += 1
		return res


class Solution:

	def maxIndexDiff(self, arr, n):
		maxdiff = 0
		for i in range(n):
			for j in range(n - 1, i, -1):
				if arr[i] <= arr[j]:
					if maxdiff < j - i:
						maxdiff = j - i
					else:
						break
		return maxdiff


class Solution:

	def maxIndexDiff(self, arr, n):
		ans = 0
		for i in range(n):
			for j in range(i + ans + 1, n):
				if arr[j] >= arr[i]:
					ans = j - i
		return ans


class Solution:

	def maxIndexDiff(self, arr, n):
		i = 0
		m = 0
		while i < n - 1:
			j = n - 1
			while i < j:
				if arr[j] >= arr[i]:
					if j - i > m:
						m = j - i
					break
				else:
					j -= 1
			i += 1
		return m


class Solution:

	def maxIndexDiff(self, arr, n):
		st = []
		ans = 0
		j = n - 1
		while j >= 0:
			if len(st) == 0:
				st.append([arr[j], j])
				j -= 1
			else:
				i = 0
				while i < len(st) and st[i][0] < arr[j]:
					i += 1
				if i == len(st):
					st.append([arr[j], j])
					j -= 1
				else:
					ans = max(ans, st[i][1] - j)
					j -= 1
		return ans


class Solution:

	def maxIndexDiff(self, arr, n):
		res = 0
		i = 0
		j = n - 1
		while i <= j:
			if arr[i] <= arr[j]:
				if res < j - i:
					res = j - i
				i = i + 1
				j = n - 1
			else:
				j = j - 1
		return res


class Solution:

	def maxIndexDiff(self, arr, n):
		if n == 1:
			return 0
		res = 0
		temp = 0
		for i in range(0, n):
			j = n - 1
			while i < j:
				if arr[j] >= arr[i]:
					temp = j - i
					break
				else:
					j -= 1
			res = max(res, temp)
		return res


class Solution:

	def maxIndexDiff(self, arr, n):
		r = [0]
		for j in range(n - 1, -1, -1):
			for i in range(0, j - 1):
				if arr[j] >= arr[i]:
					r.append(j - i)
					break
		return max(r)


class Solution:

	def maxIndexDiff(self, arr, n):
		left_min = [0] * n
		right_max = [0] * n
		left_min[0] = arr[0]
		for i in range(1, n):
			left_min[i] = min(left_min[i - 1], arr[i])
		right_max[n - 1] = arr[n - 1]
		for j in range(n - 2, -1, -1):
			right_max[j] = max(right_max[j + 1], arr[j])
		i = j = max_diff = 0
		while i < n and j < n:
			if left_min[i] <= right_max[j]:
				max_diff = max(max_diff, j - i)
				j += 1
			else:
				i += 1
		return max_diff


class Solution:

	def maxIndexDiff(self, arr, n):
		stk = [0]
		for i in range(1, len(arr)):
			if arr[stk[-1]] > arr[i]:
				stk.append(i)
		ans = 0
		for j in range(len(arr) - 1, -1, -1):
			while stk and arr[stk[-1]] <= arr[j]:
				ans = max(ans, j - stk[-1])
				stk.pop()
		return ans


class Solution:

	def maxIndexDiff(self, arr, n):
		k = n - 1
		while k:
			i = 0
			while i + k < n:
				if arr[i] <= arr[i + k]:
					return k
				i += 1
			k -= 1
		return 0


class Solution:

	def maxIndexDiff(self, arr, n):
		Lmin = [0] * n
		Rmax = [0] * n
		Lmin[0] = arr[0]
		for i in range(1, n):
			Lmin[i] = min(arr[i], Lmin[i - 1])
		Rmax[n - 1] = arr[n - 1]
		for j in range(n - 2, -1, -1):
			Rmax[j] = max(arr[j], Rmax[j + 1])
		minIndex = 0
		maxIndex = 0
		maxdiff = -1
		while minIndex < n and maxIndex < n:
			if Lmin[minIndex] <= Rmax[maxIndex]:
				maxdiff = max(maxdiff, maxIndex - minIndex)
				maxIndex = maxIndex + 1
			else:
				minIndex = minIndex + 1
		return maxdiff


class Solution:

	def maxIndexDiff(self, arr, n):
		LMin = [0] * n
		RMax = [0] * n
		LMin[0] = arr[0]
		for i in range(1, n):
			LMin[i] = min(arr[i], LMin[i - 1])
		RMax[n - 1] = arr[n - 1]
		for j in range(n - 2, -1, -1):
			RMax[j] = max(arr[j], RMax[j + 1])
		(i, j, ans) = (0, 0, -1)
		while i < n and j < n:
			if LMin[i] <= RMax[j]:
				ans = max(ans, j - i)
				j += 1
			else:
				i += 1
		return ans


class Solution:

	def maxIndexDiff(self, arr, n):
		cnt = 0
		for i in range(n):
			for j in range(i + cnt, n):
				if arr[j] >= arr[i]:
					cnt = j - i
		return cnt


class Solution:

	def maxIndexDiff(self, arr, n):
		rmax = [0] * n
		rmax[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			rmax[i] = max(arr[i], rmax[i + 1])
		mini = -1
		i = 0
		j = 0
		while i < n and j < n:
			if rmax[j] >= arr[i]:
				mini = max(mini, j - i)
				j += 1
			else:
				i += 1
		return mini


class Solution:

	def maxIndexDiff(self, arr, n):
		ans = -1
		minleft = [None] * n
		minleft[0] = arr[0]
		maxright = [None] * n
		maxright[-1] = arr[-1]
		for i in range(1, n):
			minleft[i] = min(minleft[i - 1], arr[i])
		for j in range(n - 2, -1, -1):
			maxright[j] = max(arr[j], maxright[j + 1])
		i = 0
		j = 0
		while i < n and j < n:
			if maxright[j] >= minleft[i]:
				ans = max(ans, j - i)
				j += 1
			else:
				i += 1
		return ans


class Solution:

	def maxIndexDiff(self, arr, n):
		leftMin = [0] * n
		rightMax = [0] * n
		leftMin[0] = arr[0]
		for i in range(1, n):
			leftMin[i] = min(leftMin[i - 1], arr[i])
		rightMax[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			rightMax[i] = max(rightMax[i + 1], arr[i])
		(i, j) = (0, 0)
		maxDiff = -1
		while i < n and j < n:
			if leftMin[i] <= rightMax[j]:
				maxDiff = max(maxDiff, j - i)
				j += 1
			else:
				i += 1
		return maxDiff


import math

class Solution:

	def maxIndexDiff(self, arr, n):
		llow = []
		lhigh = []
		for i in range(len(arr)):
			if len(llow) == 0:
				llow.append([arr[i], i])
				continue
			if llow[len(llow) - 1][0] > arr[i]:
				llow.append([arr[i], i])
		arr = arr[::-1]
		for i in range(len(arr)):
			if len(lhigh) == 0:
				lhigh.append([arr[i], n - 1 - i])
				continue
			if lhigh[len(lhigh) - 1][0] < arr[i]:
				lhigh.append([arr[i], n - 1 - i])
		d = dict()

		def dfs(i, j):
			if i == len(llow):
				return -math.inf
			if j == len(lhigh):
				return -math.inf
			if d.get((i, j)) != None:
				return d[i, j]
			if llow[i][0] <= lhigh[j][0]:
				d[i, j] = max(lhigh[j][1] - llow[i][1], dfs(i + 1, j), dfs(i, j + 1))
				return max(lhigh[j][1] - llow[i][1], dfs(i + 1, j), dfs(i, j + 1))
			d[i, j] = max(dfs(i + 1, j), dfs(i, j + 1))
			return d[i, j]
		return dfs(0, 0)


class Solution:

	def maxIndexDiff(self, arr, n):
		i = 0
		j = len(arr) - 1
		res = []
		while i <= j:
			if arr[i] <= arr[j]:
				m = j - i
				res.append(m)
				j = len(arr) - 1
				i += 1
			else:
				j -= 1
		return max(res)


class Solution:

	def maxIndexDiff(self, arr, n):
		i = 0
		j = len(arr) - 1
		lst = []
		while i <= j:
			k = 0
			if arr[i] <= arr[j]:
				k = j - i
				lst.append(k)
				i = i + 1
				j = len(arr) - 1
			else:
				j = j - 1
		p = max(lst)
		return p


class Solution:

	def maxIndexDiff(self, arr, n):
		l = len(arr)
		x = [0] * l
		j = l - 1
		last = 0
		for i in range(l - 1, -1, -1):
			if arr[i] > last:
				last = arr[i]
				j = i
				x[i] = j
			else:
				x[i] = j
		m = 0
		i = j = 0
		while i < l and j < l:
			if arr[i] <= arr[x[j]]:
				m = max(m, j - i)
				j += 1
			else:
				i += 1
		return m


class Solution:

	def maxIndexDiff(self, arr, n):
		(more, less, maxDiff) = (arr[:], arr[:], 0)
		for i in range(1, n):
			if less[i] > less[i - 1]:
				less[i] = less[i - 1]
		for j in range(n - 2, -1, -1):
			if more[j] < more[j + 1]:
				more[j] = more[j + 1]
		(i, j) = (0, 0)
		while j < n and i < n:
			if less[i] <= more[j]:
				maxDiff = max(j - i, maxDiff)
				j = j + 1
			else:
				i = i + 1
		return maxDiff


class Solution:

	def maxIndexDiff(self, arr, n):
		rightMax = [0] * n
		rightMax[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			rightMax[i] = max(rightMax[i + 1], arr[i])
		(i, j) = (0, 0)
		maxDist = 0
		while i < n and j < n:
			if rightMax[j] >= arr[i]:
				maxDist = max(maxDist, j - i)
				j += 1
			else:
				i += 1
		return maxDist


class Solution:

	def maxIndexDiff(self, Arr, N):
		leftMin = [0] * N
		rightMax = [0] * N
		leftMin[0] = 0
		rightMax[N - 1] = N - 1
		for i in range(1, N):
			if Arr[i] < Arr[leftMin[i - 1]]:
				leftMin[i] = i
			else:
				leftMin[i] = leftMin[i - 1]
		for i in range(N - 2, -1, -1):
			if Arr[i] > Arr[rightMax[i + 1]]:
				rightMax[i] = i
			else:
				rightMax[i] = rightMax[i + 1]
		i = j = maxDiff = 0
		while i < N and j < N:
			if Arr[leftMin[i]] <= Arr[rightMax[j]]:
				maxDiff = max(maxDiff, j - i)
				j += 1
			else:
				i += 1
		return maxDiff


class Solution:

	def maxIndexDiff(self, arr, n):
		(low, high) = ([], [])
		for i in range(n):
			if low == []:
				low.append(i)
				continue
			if arr[i] < arr[low[-1]]:
				low.append(i)
		i = n - 1
		while i >= 0:
			if high == []:
				high.append(i)
				i -= 1
				continue
			if arr[i] > arr[high[-1]]:
				high.append(i)
			i -= 1
		out = float('-inf')
		for i in range(len(high)):
			for j in range(len(low)):
				if high[i] > low[j] and arr[high[i]] >= arr[low[j]]:
					out = max(out, high[i] - low[j])
		return out if out != float('-inf') else 0


class Solution:

	def maxIndexDiff(self, arr, n):
		l = 0
		r = 0
		lmin = []
		rmax = []
		mini = float('+inf')
		for i in arr:
			mini = min(mini, i)
			lmin.append(mini)
		maxi = float('-inf')
		for i in arr[::-1]:
			maxi = max(maxi, i)
			rmax.append(maxi)
		rmax = rmax[::-1]
		res = -1
		while l < len(lmin) and r < len(rmax):
			if lmin[l] <= rmax[r]:
				res = max(res, r - l)
				r += 1
			else:
				l += 1
		return res


class Solution:

	def maxIndexDiff(self, arr, n):
		maxarr = [0] * n
		minarr = []
		len = n - 1
		for i in range(n):
			if i == 0:
				minarr.append(arr[i])
				maxarr[len - i] = arr[len - i]
			else:
				minarr.append(min(arr[i], minarr[-1]))
				maxarr[len - i] = max(maxarr[len - i + 1], arr[len - i])
		maxlength = 0
		i = 0
		j = 0
		while i < n and j < n:
			if minarr[i] <= maxarr[j]:
				while j < n and minarr[i] <= maxarr[j]:
					j += 1
				maxlength = max(maxlength, j - i - 1)
			else:
				i += 1
		return maxlength


class Solution:

	def maxIndexDiff(self, Arr, n):
		c = []
		k = 0
		for i in range(len(Arr)):
			for j in range(i + 1, len(Arr)):
				if Arr[i] <= Arr[j]:
					k = j - i
			c.append(k)
			if max(c) >= len(Arr) - i:
				break
		return max(c)


class Solution:

	def maxIndexDiff(self, arr, n):
		st = []
		ans = 0
		for (i, a) in enumerate(arr):
			if not st or arr[st[-1]] > a:
				st.append(i)
		for i in range(n - 1, -1, -1):
			while st and arr[st[-1]] <= arr[i]:
				ans = max(ans, i - st[-1])
				st.pop(-1)
		return ans


class Solution:

	def maxIndexDiff(self, arr, n):
		a = 0
		for i in range(n):
			for j in range(i + 1 + a, n):
				if arr[i] <= arr[j]:
					a = max(j - i, a)
		return a


class Solution:

	def maxIndexDiff(self, arr, n):
		mx = 0
		for i in range(0, n):
			j = n - 1
			while j >= i:
				if arr[j] >= arr[i]:
					mx = max(j - i, mx)
					break
				j -= 1
		return mx


class Solution:

	def maxIndexDiff(self, arr, n):
		L = [0] * n
		R = [0] * n
		L[0] = arr[0]
		R[n - 1] = arr[n - 1]
		l = r = 0
		ans = -1
		for i in range(1, n):
			L[i] = min(L[i - 1], arr[i])
		for i in range(n - 2, -1, -1):
			R[i] = max(R[i + 1], arr[i])
		while l < n and r < n:
			if L[l] <= R[r]:
				ans = max(ans, r - l)
				r += 1
			else:
				l += 1
		return ans


class Solution:

	def maxIndexDiff(self, arr, n):
		l = []
		r = []
		temp = 999999999999999999999999999
		for i in range(n):
			if arr[i] < temp:
				temp = arr[i]
			l.append(temp)
		temp = 0
		for j in range(n - 1, -1, -1):
			if arr[j] > temp:
				temp = arr[j]
			r.append(temp)
		r.reverse()
		i = 0
		j = 0
		ans = 0
		while i < n and j < n:
			while j < n and r[j] >= l[i]:
				j += 1
			ans = max(ans, j - 1 - i)
			i += 1
		return ans


class Solution:

	def maxIndexDiff(self, arr, n):
		l_min = [float('-inf')] * n
		r_max = [0] * n
		(l_min[0], r_max[-1]) = (arr[0], arr[-1])
		for i in range(1, n):
			l_min[i] = min(l_min[i - 1], arr[i])
		for i in range(n - 2, -1, -1):
			r_max[i] = max(r_max[i + 1], arr[i])
		(i, j) = (0, 0)
		ans = 0
		while i < n and j < n:
			if l_min[i] <= r_max[j]:
				ans = max(ans, j - i)
				j += 1
			else:
				i += 1
		return ans


class Solution:

	def maxIndexDiff(self, arr, n):
		flag = 0
		for i in range(n):
			low = i
			high = n - 1
			while low <= high:
				if arr[high] >= arr[low]:
					flag = max(flag, high - low)
					break
				else:
					high -= 1
		return flag


class Solution:

	def maxIndexDiff(self, arr, n):
		index = dict()
		for i in range(n):
			if arr[i] in index:
				index[arr[i]].append(i)
			else:
				index[arr[i]] = [i]
		arr.sort()
		maxDiff = 0
		temp = n
		a = arr
		for i in range(n):
			if temp > index[a[i]][0]:
				temp = index[a[i]][0]
			maxDiff = max(maxDiff, index[a[i]][-1] - temp)
		return maxDiff


class Solution:

	def maxIndexDiff(self, arr, n):
		x = 0
		for i in range(0, n):
			j = n - 1
			while arr[i] > arr[j]:
				j = j - 1
			x = max(x, j - i)
		return x