Given an array A of positive integers (not necessarily distinct), return the lexicographically largest permutation that is smaller than A, that can be made with one swap (A swap exchanges the positions of two numbers A[i] and A[j]).  If it cannot be done, then return the same array.
 
Example 1:
Input: [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.

Example 2:
Input: [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.

Example 3:
Input: [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.

Example 4:
Input: [3,1,1,3]
Output: [1,3,1,3]
Explanation: Swapping 1 and 3.

 
Note:

1 <= A.length <= 10000
1 <= A[i] <= 10000

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Greedy algorithms

Starter code: class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        

Solutions:
class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		n = len(A)
		if n == 1:
			return A
		tidx = -1
		for i in range(n - 2, -1, -1):
			if A[i] > A[i + 1]:
				tidx = i
				break
		if tidx < 0:
			return A
		sidx = -1
		for j in range(n - 1, tidx, -1):
			if A[j] == A[j - 1]:
				continue
			if A[j] < A[tidx]:
				sidx = j
				break
		(A[tidx], A[sidx]) = (A[sidx], A[tidx])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		for i in range(len(A) - 2, -1, -1):
			if A[i] > A[i + 1]:
				break
		else:
			return A
		stack = []
		for j in range(i + 1, len(A)):
			if A[j] < A[i]:
				while stack and A[stack[-1]] < A[j]:
					stack.pop()
				stack.append(j)
		(A[i], A[stack[0]]) = (A[stack[0]], A[i])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		if len(A) == 1:
			return A
		for i in range(len(A) - 1, 0, -1):
			if A[i - 1] > A[i]:
				(m, mi) = (A[i], i)
				for j in range(i, len(A)):
					if A[j] < A[i - 1] and A[j] > m:
						mi = j
						m = A[j]
				(A[i - 1], A[mi]) = (A[mi], A[i - 1])
				break
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		n = len(A)
		for i in range(n - 2, -1, -1):
			if A[i] > A[i + 1]:
				pm = None
				for j in range(n - 1, i, -1):
					if A[j] >= A[i]:
						continue
					if pm is None:
						pm = j
					elif A[j] == A[pm]:
						pm = j
					else:
						break
				(A[i], A[pm]) = (A[pm], A[i])
				return A
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		max_index = -1
		for i in range(1, len(A)):
			if A[i - 1] > A[i]:
				max_index = max(max_index, i - 1)
		if max_index != -1:
			for i in range(max_index + 1, len(A)):
				if A[i] < A[max_index]:
					j = i
			(A[j], A[max_index]) = (A[max_index], A[j])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		l = -1
		for i in reversed(range(len(A) - 1)):
			if A[i] > A[i + 1]:
				l = i
				break
		if l >= 0:
			r = l + 1
			s = A[r]
			for i in range(l + 2, len(A)):
				if A[i] < A[l] and A[i] >= s:
					r = i
			(A[l], A[r]) = (A[r], A[l])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		already_sorted = True
		swap_left = None
		for i in range(len(A) - 1, 0, -1):
			if A[i] < A[i - 1]:
				swap_left = (i - 1, A[i - 1])
				already_sorted = False
				break
		if already_sorted:
			return A
		swap_right = None
		for i in range(swap_left[0] + 1, len(A)):
			if A[i] < swap_left[1]:
				if swap_right and A[i] <= swap_right[1]:
					continue
				else:
					swap_right = (i, A[i])
		(A[swap_right[0]], A[swap_left[0]]) = (swap_left[1], swap_right[1])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		if sorted(A) == A:
			return A
		n = len(A)
		s = A[:]
		for i in range(n - 2, -1, -1):
			s[i] = min(s[i], s[i + 1])
			if A[i] > s[i + 1]:
				j = n - 1
				while A[j] >= A[i]:
					j -= 1
				(A[i], A[j]) = (A[j], A[i])
				return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		if len(A) == 1:
			return A
		prev = A[0]
		swapping = (0, -1)
		to_swap = (0, -1)
		for ind in range(1, len(A)):
			num = A[ind]
			if num < prev:
				swapping = (num, ind)
				to_swap = (A[ind - 1], ind - 1)
			elif num > swapping[0] and num < to_swap[0]:
				swapping = (num, ind)
			prev = num
		if swapping[1] != -1:
			value = A[swapping[1]]
			A[swapping[1]] = A[to_swap[1]]
			A[to_swap[1]] = value
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		if A == []:
			return []
		last = float('inf')
		flag = False
		for i in range(len(A) - 1, -1, -1):
			if A[i] > last:
				flag = True
				break
			last = A[i]
		if not flag:
			return A
		else:
			maxx = -float('inf')
			champ = None
			for j in range(i + 1, len(A)):
				if A[j] > maxx and A[j] < A[i]:
					champ = j
					maxx = A[j]
			(A[i], A[champ]) = (A[champ], A[i])
			return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		for i in range(len(A) - 1, 0, -1):
			if A[i - 1] > A[i]:
				break
		if i == 1 and A[i - 1] <= A[i]:
			return A
		j = max([x for x in range(i, len(A)) if A[x] < A[i - 1]], key=lambda x: A[x])
		(A[i - 1], A[j]) = (A[j], A[i - 1])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		a_length = len(A)
		largest_left_index = 0
		largest_left = A[0]
		for i in range(2, a_length + 1):
			i *= -1
			if A[i] > A[i + 1]:
				largest_left_index = i
				largest_left = A[i]
				break
		largest_right_index = 0
		largest_right = 0
		for i in range(a_length + largest_left_index + 1, a_length):
			if A[i] > largest_right and A[i] < largest_left:
				largest_right_index = i
				largest_right = A[i]
		(A[largest_left_index], A[largest_right_index]) = (A[largest_right_index], A[largest_left_index])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		stack = []
		for i in range(len(A) - 1, -1, -1):
			if stack != [] and stack[-1] < A[i]:
				break
			stack.append(A[i])
		if len(stack) == len(A):
			return A
		stack = stack[::-1]
		(low, high) = (0, len(stack) - 1)
		while low < high - 1:
			mid = (low + high) // 2
			if stack[mid] >= A[i]:
				high = mid - 1
			else:
				low = mid
		if stack[high] >= A[i]:
			high -= 1
		l = high - 1
		while l >= 0 and stack[l] == stack[high]:
			l -= 1
		l += 1
		temp = A[i]
		A[i] = A[i + l + 1]
		A[i + l + 1] = temp
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		for i in range(len(A) - 2, -1, -1):
			if A[i] > A[i + 1]:
				break
		if A[i] <= A[i + 1]:
			return A
		max_j = 0
		j_ind = i
		for j in range(i, len(A)):
			if A[i] > A[j]:
				max_j = max(max_j, A[j])
				if max_j == A[j]:
					j_ind = j
		tmp = A[i]
		A[i] = A[j_ind]
		A[j_ind] = tmp
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		n = len(A)
		if n <= 1:
			return A
		left = n - 2
		while left >= 0 and A[left] <= A[left + 1]:
			left -= 1
		if left < 0:
			return A
		right = n - 1
		while A[right] >= A[left]:
			right -= 1
		while A[right] == A[right - 1]:
			right -= 1
		(A[left], A[right]) = (A[right], A[left])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		res = [val for val in A]
		length = len(A)
		start = 0
		haveInvertedPos = False
		for i in range(length - 1):
			if A[i] <= A[i + 1]:
				pass
			else:
				start = i
				haveInvertedPos = True
		if not haveInvertedPos:
			return res
		target = start + 1
		temp = A[target]
		for i in range(start + 1, length):
			if A[i] < A[start] and A[i] > temp:
				temp = A[i]
				target = i
		(res[start], res[target]) = (res[target], res[start])
		return res


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		n = len(A)
		left = n - 1
		while left >= 1 and A[left - 1] <= A[left]:
			left -= 1
		if left == 0:
			return A
		right = left
		left = left - 1
		for i in range(right, n):
			if A[i] > A[right] and A[i] < A[left]:
				right = i
		(A[left], A[right]) = (A[right], A[left])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		stack = []
		find = -1
		for i in range(1, len(A)):
			if A[i] < A[i - 1]:
				find = i - 1
				break
		if find == -1:
			return A
		j = find
		ind = []
		3210
		while j < len(A):
			if len(stack) == 0:
				stack.append(j)
				j += 1
				continue
			if A[j] < A[stack[-1]]:
				if len(stack) == 2:
					a = stack[-1]
					stack = [a, j]
				else:
					stack.append(j)
				j += 1
				continue
			else:
				if len(stack) == 2:
					ind = [stack[0], stack[1]]
				stack.pop()
		if len(stack) == 2:
			(A[stack[0]], A[stack[1]]) = (A[stack[1]], A[stack[0]])
			return A
		if len(ind) == 2:
			(A[ind[0]], A[ind[1]]) = (A[ind[1]], A[ind[0]])
			return A
		return A
		if len(stack) == 0 and len(ind) == 0:
			return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		if not A:
			return A
		leftIndex = -1
		for i in range(len(A) - 1, 0, -1):
			if A[i - 1] > A[i]:
				leftIndex = i - 1
				break
		if leftIndex == -1:
			return A
		rightIndex = -1
		for i in range(len(A) - 1, leftIndex, -1):
			if A[i] >= A[leftIndex]:
				continue
			elif rightIndex == -1:
				rightIndex = i
			elif A[i] == A[rightIndex]:
				rightIndex = i
		(A[leftIndex], A[rightIndex]) = (A[rightIndex], A[leftIndex])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		for i in range(len(A) - 2, -1, -1):
			ans = (-1, -1)
			for j in range(i + 1, len(A)):
				if A[j] < A[i]:
					ans = max(ans, (A[j], -j))
			if ans[0] != -1:
				(A[i], A[-ans[1]]) = (A[-ans[1]], A[i])
				return A
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		stack = [0]
		larger_index = [-1] * len(A)
		for i in range(1, len(A)):
			while stack and A[i] >= A[stack[-1]]:
				stack.pop()
			if stack:
				larger_index[i] = stack[-1]
			stack.append(i)
		print(larger_index)
		(idx, swap) = (len(larger_index), -1)
		for i in range(len(larger_index) - 1, -1, -1):
			if larger_index[i] == -1:
				continue
			if larger_index[i] > swap or (larger_index[i] == swap and A[i] >= A[idx]):
				val = A[larger_index[i]]
				idx = i
				swap = larger_index[i]
		if swap != -1:
			(A[swap], A[idx]) = (A[idx], A[swap])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		i = len(A) - 2
		while i >= 0 and A[i] <= A[i + 1]:
			i -= 1
		if i >= 0:
			max_ = i + 1
			for j in range(max_ + 1, len(A)):
				if A[max_] < A[j] and A[j] < A[i]:
					max_ = j
			(A[max_], A[i]) = (A[i], A[max_])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		mid = -1
		for i in range(len(A) - 2, -1, -1):
			if A[i] > A[i + 1]:
				mid = i
				break
		if mid == -1:
			return A
		max_mid = -1
		for i in range(mid + 1, len(A)):
			if A[mid] > A[i]:
				if A[i] > max_mid:
					index = i
					max_mid = A[i]
		(A[mid], A[index]) = (A[index], A[mid])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		prev_vals = [(float('inf'), None)]
		for i in range(len(A) - 1, -1, -1):
			num = A[i]
			if num > prev_vals[-1][0]:
				max_prev = 0
				ind = None
				while num > prev_vals[-1][0]:
					(prev_n, prev_ind) = prev_vals.pop()
					if prev_n > max_prev:
						max_prev = prev_n
						ind = prev_ind
				(A[i], A[ind]) = (max_prev, num)
				return A
			prev_vals.append((num, i))
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		largest = len(A) - 2
		while largest >= 0 and A[largest] <= A[largest + 1]:
			largest -= 1
		if largest == -1:
			return A
		smallest = len(A) - 1
		while A[largest] <= A[smallest]:
			smallest -= 1
		f = smallest
		while A[smallest] == A[f]:
			f -= 1
		(A[f + 1], A[largest]) = (A[largest], A[f + 1])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		idx = -1
		for i in range(len(A) - 1):
			if A[i] > A[i + 1]:
				idx = i
		if idx == -1:
			return A
		for i in range(len(A) - 1, idx, -1):
			if A[i] < A[idx] and A[i] != A[i - 1]:
				(A[idx], A[i]) = (A[i], A[idx])
				break
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		for i in range(len(A) - 2, -1, -1):
			for x in range(len(A) - 1, i, -1):
				if A[x] == A[x - 1]:
					continue
				if A[i] > A[x]:
					(A[i], A[x]) = (A[x], A[i])
					return A
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		i = len(A) - 2
		while i >= 0 and A[i + 1] >= A[i]:
			i -= 1
		if i == -1:
			return A
		k = i + 1
		j = i + 1
		while j < len(A):
			if A[k] < A[j] < A[i]:
				k = j
			j += 1
		(A[i], A[k]) = (A[k], A[i])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		point = -1
		for i in range(len(A) - 1, 0, -1):
			if A[i - 1] > A[i]:
				point = i - 1
				break
		if point == -1:
			return A
		right_point = point + 1
		max_val = -1
		for i in range(point + 1, len(A)):
			if A[i] < A[point] and max_val < A[i]:
				right_point = i
				max_val = A[i]
		(A[point], A[right_point]) = (A[right_point], A[point])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		for i in range(len(A) - 2, -1, -1):
			if A[i] > A[i + 1]:
				for j in range(i + 1, len(A)):
					if A[j] > A[i] or j == len(A) - 1:
						k = j - 1 if A[j] > A[i] else j
						while k > i and A[k] == A[i]:
							k -= 1
						while k - 1 > i and A[k - 1] == A[k]:
							k -= 1
						(A[i], A[k]) = (A[k], A[i])
						break
				break
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		rear = len(A) - 2
		while rear > -1:
			if A[rear] > A[rear + 1]:
				break
			rear -= 1
		if rear == -1:
			return A
		front = len(A) - 1
		while A[front] >= A[rear] or A[front - 1] == A[front]:
			front -= 1
		(A[rear], A[front]) = (A[front], A[rear])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		l = len(A) - 2
		while l >= 0:
			if A[l + 1] < A[l]:
				break
			l -= 1
		max_so_far = 0
		max_idx = l
		r = l + 1
		while r < len(A):
			if A[r] > max_so_far and A[r] < A[l]:
				max_so_far = A[r]
				max_idx = r
			r += 1
		if 0 <= l <= max_idx < len(A):
			(A[l], A[max_idx]) = (A[max_idx], A[l])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		smallestSeenSoFar = A[-1]
		swapOutIndex = -1
		for i in range(len(A) - 2, -1, -1):
			if A[i] > smallestSeenSoFar:
				swapOutIndex = i
				break
			smallestSeenSoFar = min(smallestSeenSoFar, A[i])
		if swapOutIndex == -1:
			return A
		swapInIndex = len(A) - 1
		largestSeenSmallerThanSwapout = 0
		for i in range(len(A) - 1, swapOutIndex, -1):
			if A[i] < A[swapOutIndex] and A[i] >= largestSeenSmallerThanSwapout:
				swapInIndex = i
				largestSeenSmallerThanSwapout = A[i]
		(A[swapOutIndex], A[swapInIndex]) = (A[swapInIndex], A[swapOutIndex])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		n = len(A)
		(i, mn, mx) = (n - 2, n - 1, n - 1)
		while i >= 0:
			if A[i] > A[mn]:
				mx = i
			if A[i] < A[mn]:
				mn = i
			if mn != mx and mx < mn:
				break
			i -= 1
		if i == -1:
			return A
		print((mx, mn))
		mxR = mx + 1
		for j in range(mx + 1, n):
			if A[j] < A[mx] and A[j] > A[mxR]:
				mxR = j
		(A[mx], A[mxR]) = (A[mxR], A[mx])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		for i in reversed(range(1, len(A))):
			if A[i - 1] > A[i]:
				maxLessInd = i
				maxLessVal = A[i]
				for j in range(i + 1, len(A)):
					if A[j] > maxLessVal and A[j] < A[i - 1]:
						maxLessVal = A[j]
						maxLessInd = j
				(A[i - 1], A[maxLessInd]) = (A[maxLessInd], A[i - 1])
				return A
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		m = 10000
		idx = defaultdict(int)
		l = []
		for i in range(len(A) - 1, -1, -1):
			if A[i] > m:
				l.sort()
				j = idx[l[bisect_left(l, A[i]) - 1]]
				(A[i], A[j]) = (A[j], A[i])
				return A
			m = min(m, A[i])
			idx[A[i]] = i
			l.append(A[i])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:
		if A == sorted(A):
			return A
		idx = None
		for i in range(len(A) - 1, 0, -1):
			if A[i - 1] > A[i]:
				idx = i - 1
				break
		mx = float('-inf')
		for i in range(idx + 1, len(A)):
			if mx < A[i] < A[idx]:
				mx = A[i]
				midx = i
		(A[midx], A[idx]) = (A[idx], A[midx])
		return A


class Solution:

	def prevPermOpt1(self, A: List[int]) -> List[int]:

		def findLarger():
			prev = A[-1]
			for i in range(len(A) - 1, -1, -1):
				if A[i] > prev:
					return i
				prev = A[i]
			return -1
		if not A:
			return A
		larger = findLarger()
		if larger == -1:
			return A
		sl = larger + 1
		for i in range(larger, len(A)):
			if A[i] < A[larger]:
				if A[sl] < A[i]:
					sl = i
		print((larger, sl))
		(A[sl], A[larger]) = (A[larger], A[sl])
		return A