Previous permutation with one swap

Array Greedy

49.3% acceptance

Feb 25, 2026

479

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. Note that a swap exchanges the positions of two numbers arr[i] and arr[j]

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn prev_perm_opt1(mut arr: Vec<i32>) -> Vec<i32> {
    let n = arr.len();
    // Find rightmost i where arr[i] > arr[i+1]
    let mut i = n as i32 - 2;
    while i >= 0 && arr[i as usize] <= arr[i as usize + 1] { i -= 1; }
    if i < 0 { return arr; }
    let i = i as usize;
    // Find largest value < arr[i] in arr[i+1..], take leftmost
    let target = *arr[i+1..].iter().filter(|&&x| x < arr[i]).max().unwrap();
    let j = arr[i+1..].iter().position(|&x| x == target).unwrap() + i + 1;
    arr.swap(i, j);
    arr
  }
}