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.

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