Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1053.html

1053. Previous Permutation With One Swap (Medium)

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. 1 <= A.length <= 10000
2. 1 <= A[i] <= 10000

Related Topics:
Array, Greedy

Solution 1.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int[] prevPermOpt1(int[] A) {
          PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>((a, b) -> (a[0] - b[0]));
          int swapIndex = -1;
          int swapNum = 0;
          int length = A.length;
          for (int i = length - 1; i > 0; i--) {
              int num = A[i];
              priorityQueue.offer(new int[]{num, i});
              if (num < A[i - 1]) {
                  swapIndex = i - 1;
                  swapNum = A[i - 1];
                  break;
              }
          }
          if (swapIndex < 0)
              return A;
          int nextSwapNum = 0, nextSwapIndex = -1;
          while (!priorityQueue.isEmpty() && priorityQueue.peek()[0] < swapNum) {
              int[] numIndex = priorityQueue.poll();
              nextSwapNum = numIndex[0];
              nextSwapIndex = numIndex[1];
          }
          A[swapIndex] = nextSwapNum;
          A[nextSwapIndex] = swapNum;
          return A;
      }
  }
  
  ############
  
  class Solution {
      public int[] prevPermOpt1(int[] arr) {
          int n = arr.length;
          for (int i = n - 1; i > 0; --i) {
              if (arr[i - 1] > arr[i]) {
                  for (int j = n - 1; j > i - 1; --j) {
                      if (arr[j] < arr[i - 1] && arr[j] != arr[j - 1]) {
                          int t = arr[i - 1];
                          arr[i - 1] = arr[j];
                          arr[j] = t;
                          return arr;
                      }
                  }
              }
          }
          return arr;
      }
  }
  

• // OJ: https://leetcode.com/problems/previous-permutation-with-one-swap/
  // Time: O(N^2)
  // Space: O(1)
  class Solution {
  public:
      vector<int> prevPermOpt1(vector<int>& A) {
          int first = -1, second;
          for (int i = A.size() - 1; i > first; --i) {
              while (i - 1 > first && A[i - 1] == A[i]) --i;
              int j = i - 1;
              while (j > first && A[j] <= A[i]) --j;
              if (j > first) {
                  first = j;
                  second = i;
              }
          }
          if (first > -1) swap(A[first], A[second]);
          return A;
      }
  };
  

• class Solution:
      def prevPermOpt1(self, arr: List[int]) -> List[int]:
          n = len(arr)
          for i in range(n - 1, 0, -1):
              if arr[i - 1] > arr[i]:
                  for j in range(n - 1, i - 1, -1):
                      if arr[j] < arr[i - 1] and arr[j] != arr[j - 1]:
                          arr[i - 1], arr[j] = arr[j], arr[i - 1]
                          return arr
          return arr
  
  ############
  
  # 1053. Previous Permutation With One Swap
  # https://leetcode.com/problems/previous-permutation-with-one-swap/
  
  class Solution:
      def prevPermOpt1(self, arr: List[int]) -> List[int]:
          n = len(arr)
          if n <= 1: return arr
          
          index = -1
          for i in range(n - 1, 0, -1):
              if arr[i] < arr[i - 1]:
                  index = i - 1
                  break
                  
          if index == -1: return arr
          for i in range(n - 1, index - 1, -1):
              if arr[i] < arr[index] and arr[i] != arr[i - 1]:
                  arr[i], arr[index] = arr[index], arr[i]
                  break
          
          return arr
          
  
  

• func prevPermOpt1(arr []int) []int {
  	n := len(arr)
  	for i := n - 1; i > 0; i-- {
  		if arr[i-1] > arr[i] {
  			for j := n - 1; j > i-1; j-- {
  				if arr[j] < arr[i-1] && arr[j] != arr[j-1] {
  					arr[i-1], arr[j] = arr[j], arr[i-1]
  					return arr
  				}
  			}
  		}
  	}
  	return arr
  }
  

• function prevPermOpt1(arr: number[]): number[] {
      const n = arr.length;
      for (let i = n - 1; i > 0; --i) {
          if (arr[i - 1] > arr[i]) {
              for (let j = n - 1; j > i - 1; --j) {
                  if (arr[j] < arr[i - 1] && arr[j] !== arr[j - 1]) {
                      const t = arr[i - 1];
                      arr[i - 1] = arr[j];
                      arr[j] = t;
                      return arr;
                  }
              }
          }
      }
      return arr;
  }
  
  

All Problems

All Solutions