Next Permutation of Array in DSA C

Mental Model

Find the next bigger arrangement of numbers by changing the smallest part of the array to get the next order.

Analogy: Imagine you have a row of books sorted in a certain order. To find the next order, you look from right to left to find the first book that can be swapped with a bigger one to its right, then rearrange the books after it to the smallest order.

Array: [1] -> [2] -> [3] -> [4] -> [5]
Indexes:  0      1      2      3      4

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Find the next permutation after [1, 2, 3], which is the next bigger arrangement of these numbers.

Step 1: Find the first index from the right where the number is smaller than the number after it (pivot).

[1, 2, 3] with pivot at index 1 (value 2)

Why: We need to find where the ascending order breaks from the right to find the pivot to swap.

Step 2: Find the first number from the right that is bigger than the pivot (value 2).

[1, 2, 3] with successor at index 2 (value 3)

Why: We want to swap pivot with the next bigger number to get the next permutation.

Step 3: Swap the pivot and successor.

[1, 3, 2]

Why: Swapping creates a bigger number but still close to the original.

Step 4: Reverse the subarray after the pivot index to get the smallest order.

[1, 3, 2]

Why: Reversing ensures the suffix is the smallest possible to get the next permutation.

Result:

[1] -> [3] -> [2] (next permutation)

Annotated Code

DSA C

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void reverse(int arr[], int start, int end) {
    while (start < end) {
        swap(&arr[start], &arr[end]);
        start++;
        end--;
    }
}

void nextPermutation(int arr[], int n) {
    int i = n - 2;
    // Find pivot
    while (i >= 0 && arr[i] >= arr[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = n - 1;
        // Find successor
        while (arr[j] <= arr[i]) {
            j--;
        }
        swap(&arr[i], &arr[j]);
    }
    // Reverse suffix
    reverse(arr, i + 1, n - 1);
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i != n - 1) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array:\n");
    printArray(arr, n);
    nextPermutation(arr, n);
    printf("Next permutation:\n");
    printArray(arr, n);
    return 0;
}

while (i >= 0 && arr[i] >= arr[i + 1]) { i--; }

Find pivot index where ascending order breaks from right

while (arr[j] <= arr[i]) { j--; }

Find successor index to pivot that is just bigger

swap(&arr[i], &arr[j]);

Swap pivot and successor to increase permutation

reverse(arr, i + 1, n - 1);

Reverse suffix to get smallest order after pivot

Output

Original array:

1 -> 2 -> 3 -> null

Next permutation:

1 -> 3 -> 2 -> null

Complexity Analysis

Time: O(n) because we scan the array from right to left a few times and reverse a suffix once

Space: O(1) because all operations are done in place without extra arrays

vs Alternative: Compared to generating all permutations and sorting, this approach is much faster and uses less memory

Edge Cases

Array is in descending order like [3, 2, 1]

The function reverses the entire array to the smallest permutation [1, 2, 3]

DSA C

while (i >= 0 && arr[i] >= arr[i + 1]) { i--; }

Array has only one element like [1]

No change happens since there is no next permutation

DSA C

while (i >= 0 && arr[i] >= arr[i + 1]) { i--; }

Array has duplicate elements like [1, 5, 5]

Next permutation is correctly found as [5, 1, 5]

DSA C

while (arr[j] <= arr[i]) { j--; }

When to Use This Pattern

When asked to find the next bigger arrangement of numbers or letters in order, use the next permutation pattern to find it efficiently without generating all permutations.

Common Mistakes

Mistake: Not reversing the suffix after swapping pivot and successor
Fix: Always reverse the subarray after the pivot index to get the smallest suffix

Mistake: Finding the pivot incorrectly by checking arr[i] > arr[i+1] instead of arr[i] >= arr[i+1]
Fix: Use arr[i] >= arr[i+1] to correctly find the pivot where ascending order breaks

Summary

Finds the next bigger permutation of an array of numbers in place.

Use when you need the next lexicographical order of a sequence without generating all permutations.

The key is to find the pivot where order breaks, swap with next bigger number, then reverse the suffix.