Previous Permutation With One Swap

medium greedy array permutation

Problem

Given an array of positive integers arr (not necessarily distinct), return the lexicographically largest permutation that is smaller than arr, that can be made with exactly one swap. If it cannot be done, then return the same array.

Inputarr = [3, 2, 1]

Output[3, 1, 2]

Swapping 2 and 1 gives the largest array still smaller than [3, 2, 1].

arr (comma-separated)

def prev_perm_opt1(arr):
    n = len(arr)
    for i in range(n - 2, -1, -1):
        if arr[i] > arr[i + 1]:
            j = i + 1
            while j + 1 < n and arr[j + 1] < arr[i]:
                j += 1
            while j > i + 1 and arr[j] == arr[j - 1]:
                j -= 1
            arr[i], arr[j] = arr[j], arr[i]
            break
    return arr

function prevPermOpt1(arr) {
  const n = arr.length;
  for (let i = n - 2; i >= 0; i--) {
    if (arr[i] > arr[i + 1]) {
      let j = i + 1;
      while (j + 1 < n && arr[j + 1] < arr[i]) j++;
      while (j > i + 1 && arr[j] === arr[j - 1]) j--;
      [arr[i], arr[j]] = [arr[j], arr[i]];
      break;
    }
  }
  return arr;
}

class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                int j = i + 1;
                while (j + 1 < n && arr[j + 1] < arr[i]) j++;
                while (j > i + 1 && arr[j] == arr[j - 1]) j--;
                int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
                break;
            }
        }
        return arr;
    }
}

vector<int> prevPermOpt1(vector<int>& arr) {
    int n = arr.size();
    for (int i = n - 2; i >= 0; i--) {
        if (arr[i] > arr[i + 1]) {
            int j = i + 1;
            while (j + 1 < n && arr[j + 1] < arr[i]) j++;
            while (j > i + 1 && arr[j] == arr[j - 1]) j--;
            swap(arr[i], arr[j]);
            break;
        }
    }
    return arr;
}

Explanation

We want the largest array that is still smaller than the input, using just one swap. The key insight is that to make the array smaller we must lower a digit, and to keep it as large as possible we should lower the rightmost digit we can.

So we scan from the right looking for the first descent — an index i where arr[i] > arr[i + 1]. That is the rightmost spot where swapping in a smaller value will actually shrink the array.

To its right we pick the swap partner j: the largest value that is still smaller than arr[i]. The inner loop extends j while the next value is still below arr[i], and if duplicates exist we step left to the leftmost copy so the swapped-in digit lands as far left as possible (keeping the result big).

Example: arr = [3, 2, 1]. Scanning right, the first descent is at i = 1 (2 > 1). The best smaller value to its right is 1 at j = 2. Swapping gives [3, 1, 2].

If no descent exists, the array is already non-decreasing (the smallest permutation), so nothing can be made smaller and we return it unchanged.

Time: O(n) Space: O(1)