Previous Permutation With One Swap

Previous Permutation With One Swap - Problem

Array Greedy Medium

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]

Input & Output

Example 1 — Basic Swap Case

$ Input: arr = [3,2,1]

› Output: [3,1,2]

💡 Note: Find rightmost decreasing position (i=1, where 2>1), then find largest smaller element to the right (j=2, value=1). Swap positions 1 and 2 to get [3,1,2].

Example 2 — No Swap Possible

$ Input: arr = [1,1,5]

› Output: [1,1,5]

💡 Note: Array is already in non-decreasing order from left to right. No position i exists where arr[i] > arr[i+1], so no swap is possible.

Example 3 — Multiple Candidates

$ Input: arr = [1,9,4,6,7]

› Output: [1,7,4,6,9]

💡 Note: Rightmost decreasing position is i=1 (9>4). Among elements to the right that are smaller than 9, we choose the largest one which is 7 at position 4. Swap to get [1,7,4,6,9].

Constraints

1 ≤ arr.length ≤ 10⁴
1 ≤ arr[i] ≤ 10⁴

Visualization

Tap to expand

Asked in

G Google 25 M Microsoft 18 a Amazon 12

The key insight is to find the rightmost decreasing position and swap with the largest smaller element to its right. The greedy approach works optimally in O(n) time by making two passes through the array. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Swaps	O(n³)	O(n)	Generate all possible single swaps and find the largest valid result
Greedy Two-Pass Approach	O(n)	O(1)	Find rightmost decreasing position, then find optimal swap candidate

Brute Force - Try All Swaps — Algorithm Steps

Try all possible swaps (i,j) where i < j
For each swap, check if result is smaller than original
Keep track of the largest valid result

Visualization

Tap to expand

Step-by-Step Walkthrough

Original

Start with input array [3,2,1]

Try Swaps

Test all pairs: (0,1), (0,2), (1,2)

Best Result

Keep largest valid permutation

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isSmaller(int* a, int* b, int n) {
    for (int i = 0; i < n; i++) {
        if (a[i] < b[i]) return 1;
        if (a[i] > b[i]) return 0;
    }
    return 0;
}

void solution(int* arr, int n, int* result) {
    int* original = malloc(n * sizeof(int));
    int* best = malloc(n * sizeof(int));
    int found = 0;
    
    memcpy(original, arr, n * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Try swapping arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            
            if (isSmaller(arr, original, n)) {
                if (!found || !isSmaller(arr, best, n)) {
                    memcpy(best, arr, n * sizeof(int));
                    found = 1;
                }
            }
            
            // Swap back
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    if (found) {
        memcpy(result, best, n * sizeof(int));
    } else {
        memcpy(result, arr, n * sizeof(int));
    }
    
    free(original);
    free(best);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON parsing for array
    int arr[100];
    int n = 0;
    char* ptr = strchr(line, '[') + 1;
    while (*ptr != ']') {
        arr[n++] = atoi(ptr);
        ptr = strchr(ptr, ',');
        if (ptr) ptr++;
        else break;
    }
    
    int result[100];
    solution(arr, n, result);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", result[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) pairs to swap × O(n) comparison for each swap

⚠ Quadratic Growth

Space Complexity

O(n)

Extra array to store best result and temporary swap results

⚡ Linearithmic Space

35.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Swaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler