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.

Practice

1. What does the next permutation of an array represent?

easy

A. The next lexicographically greater arrangement of the array elements

B. The array sorted in ascending order

C. The array reversed

D. The smallest element moved to the front

Solution

1. Step 1: Understand the concept of permutation order

   Permutations can be ordered lexicographically like words in a dictionary.

2. Step 2: Define next permutation

   The next permutation is the immediate next arrangement that is greater than the current one in lexicographic order.

3. Final Answer:

   The next lexicographically greater arrangement of the array elements -> Option A

4. Quick Check:

   Next permutation = next bigger arrangement [OK]

Hint: Next permutation means next bigger arrangement [OK]

Common Mistakes:

• Confusing next permutation with sorting ascending
• Thinking next permutation is just reversing array
• Assuming next permutation always moves smallest element front

2. Which of the following C code snippets correctly swaps two integers a and b using a temporary variable?

easy

A. a = a + b; b = a - b; a = a - b;

B. a = b; b = a;

C. int temp; a = b; b = temp;

D. int temp = a; a = b; b = temp;

Solution

1. Step 1: Understand swapping with a temporary variable

   Use a temporary variable to hold one value while assigning the other.

2. Step 2: Check each option

   int temp = a; a = b; b = temp; correctly uses a temp variable to swap values safely.

3. Final Answer:

   int temp = a; a = b; b = temp; -> Option D

4. Quick Check:

   Swap with temp variable = int temp = a; a = b; b = temp; [OK]

Hint: Use temp variable to swap safely [OK]

Common Mistakes:

• Assigning a = b; b = a; loses original value
• Using arithmetic swap without considering overflow
• Not declaring or initializing temp variable

3. What is the output of the following C code that finds the next permutation of the array arr = {1, 3, 2}?

void nextPermutation(int* arr, int n) {
    int i = n - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (arr[j] <= arr[i]) j--;
        int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }
    int left = i + 1, right = n - 1;
    while (left < right) {
        int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp;
        left++; right--;
    }
}

int main() {
    int arr[] = {1, 3, 2};
    nextPermutation(arr, 3);
    for (int i = 0; i < 3; i++) printf("%d ", arr[i]);
    return 0;
}

medium

A. 1 2 3

B. 1 3 2

C. 2 1 3

D. 3 1 2

Solution

1. Step 1: Find the pivot index i

   Start from right: arr[1]=3, arr[2]=2, since 3 >= 2, i moves left to 0 where arr[0]=1 < arr[1]=3, so i=0.

2. Step 2: Find j to swap with i

   From right, find j where arr[j] > arr[i]: arr[2]=2 > 1, so j=2. Swap arr[0] and arr[2]: arr becomes {2, 3, 1}.

3. Step 3: Reverse suffix after i

   Reverse elements from i+1=1 to end: reverse {3,1} to {1,3}. Final array: {2,1,3}.

4. Final Answer:

   2 1 3 -> Option C

5. Quick Check:

   Next permutation of [1,3,2] = [2,1,3] [OK]

Hint: Swap pivot with next bigger, then reverse suffix [OK]

Common Mistakes:

• Not reversing suffix after swap
• Swapping with wrong element j
• Stopping pivot search too early

4. Identify the bug in the following C function that attempts to compute the next permutation of an array arr of size n:

void nextPermutation(int* arr, int n) {
    int i = n - 1;
    while (i > 0 && arr[i] <= arr[i - 1]) i--;
    if (i > 0) {
        int j = n - 1;
        while (arr[j] <= arr[i - 1]) j--;
        int temp = arr[i - 1]; arr[i - 1] = arr[j]; arr[j] = temp;
    }
    int left = i, right = n - 1;
    while (left < right) {
        int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp;
        left++; right--;
    }
}

medium

A. The swap should be done with arr[i], not arr[i - 1]

B. The initial value of i should be n - 2, not n - 1

C. The reversal loop should start from i - 1, not i

D. The comparison in the first while loop should be arr[i] >= arr[i - 1]

Solution

1. Step 1: Analyze the pivot search loop

   The pivot is found by moving left from n-2, but here i starts at n-1, which skips checking the last pair correctly.

2. Step 2: Correct initial i value

   Setting i = n - 2 ensures the loop compares arr[i] and arr[i+1] properly to find the pivot.

3. Final Answer:

   The initial value of i should be n - 2, not n - 1 -> Option B

4. Quick Check:

   Pivot search starts at n-2 index [OK]

Hint: Start pivot search at n-2 index [OK]

Common Mistakes:

• Starting pivot index at n-1 causes missed comparisons
• Incorrect comparison operators in loops
• Reversing wrong subarray segment

5. Given an array arr = {5, 4, 7, 5, 3, 2}, what will be the next permutation after applying the standard next permutation algorithm?

hard

A. [5, 5, 2, 3, 4, 7]

B. [5, 4, 7, 5, 3, 2]

C. [5, 4, 7, 5, 2, 3]

D. [7, 2, 3, 4, 5, 5]

Solution

1. Step 1: Find pivot index i

   Traverse from right: arr[4]=3, arr[5]=2 (3 >= 2), move left; arr[3]=5, arr[4]=3 (5 >= 3), move left; arr[2]=7, arr[3]=5 (7 >= 5), move left; arr[1]=4, arr[2]=7 (4 < 7), so i=1.

2. Step 2: Find j to swap with i

   From right, find j where arr[j] > arr[i]: arr[5]=2 (2 > 4? No), arr[4]=3 (3 > 4? No), arr[3]=5 (5 > 4? Yes), so j=3. Swap arr[1] and arr[3]: arr becomes {5,5,7,4,3,2}.

3. Step 3: Reverse suffix after i

   Reverse elements from i+1=2 to end: reverse {7,4,3,2} to {2,3,4,7}. Final array: {5,5,2,3,4,7}.

4. Final Answer:

   [5, 5, 2, 3, 4, 7] -> Option A

5. Quick Check:

   Next permutation of [5,4,7,5,3,2] = [5,5,2,3,4,7] [OK]

Hint: Swap pivot with next bigger, reverse suffix [OK]

Common Mistakes:

• Not finding correct pivot index
• Swapping with wrong element j
• Not reversing suffix correctly