Next Permutation of Array in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Next Permutation on a simple array

What is the output of the following C code after calling next_permutation on the array?

DSA C

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

#include <stdio.h>
int main() {
    int arr[3] = {1, 2, 3};
    next_permutation(arr, 3);
    for (int i = 0; i < 3; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A 1 3 2

B 3 2 1

C 1 2 3

D 2 1 3

💡 Hint

Remember next permutation finds the next lexicographically greater arrangement.

The next permutation of [1, 2, 3] is [1, 3, 2]. The code swaps the first decreasing element from the right with the next bigger element and reverses the suffix.

❓ Predict Output

intermediate

Next Permutation output for descending array

What will be printed after running next_permutation on this descending array?

DSA C

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

#include <stdio.h>
int main() {
    int arr[4] = {4, 3, 2, 1};
    next_permutation(arr, 4);
    for (int i = 0; i < 4; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A 1 3 2 4

B 4 3 2 1

C 1 2 3 4

D 2 1 3 4

💡 Hint

If the array is in descending order, the next permutation is the lowest ascending order.

The array is the highest permutation. The next permutation resets it to the lowest: [1, 2, 3, 4].

🔧 Debug

advanced

Identify the error in this next_permutation implementation

What error will this code cause when run on array [1, 3, 2]?

DSA C

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

#include <stdio.h>
int main() {
    int arr[3] = {1, 3, 2};
    next_permutation(arr, 3);
    for (int i = 0; i < 3; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A The code runs correctly and outputs: 2 1 3

B The code swaps wrong elements and outputs: 1 3 2

C The code causes an infinite loop

D The code runs correctly and outputs: 1 2 3

💡 Hint

Check the comparison operators in the while loops carefully.

The code uses '>' and '<' instead of '>=' and '<=' causing incorrect pivot and swap selection, so the output remains unchanged.

🧠 Conceptual

advanced

Understanding the pivot in next permutation

In the next permutation algorithm, what does the pivot index represent?

A The index of the smallest element in the array

B The last index of the array

C The first index from the right where the sequence stops increasing

D The first index from the right where the sequence stops decreasing

💡 Hint

Think about where the array stops descending from the right side.

The pivot is the first index from the right where the sequence stops decreasing (or stops non-increasing). This is where we find the element to swap to get the next bigger permutation.

❓ Predict Output

expert

Next Permutation output for array with duplicates

What is the output after running next_permutation on this array with duplicates?

DSA C

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

#include <stdio.h>
int main() {
    int arr[5] = {1, 2, 2, 3, 3};
    next_permutation(arr, 5);
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A 1 2 3 3 2

B 1 2 3 2 3

C 1 3 2 2 3

D 1 2 2 3 3

💡 Hint

The next permutation must be the next lexicographically bigger sequence.

The next permutation after [1, 2, 2, 3, 3] is [1, 2, 3, 3, 2]. The pivot is at index 2 (value 2), swapped with index 4 (value 3), then suffix reversed.