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

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the next permutation?

Given the array [1, 3, 2], what will be the array after applying the next permutation algorithm once?

DSA C#

int[] arr = {1, 3, 2};
NextPermutation(arr);
Console.WriteLine(string.Join(", ", arr));

void NextPermutation(int[] nums) {
    int i = nums.Length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = nums.Length - 1;
        while (nums[j] <= nums[i]) j--;
        Swap(nums, i, j);
    }
    Reverse(nums, i + 1, nums.Length - 1);
}

void Swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void Reverse(int[] nums, int start, int end) {
    while (start < end) {
        Swap(nums, start, end);
        start++;
        end--;
    }
}

A [3, 2, 1]

B [1, 2, 3]

C [1, 3, 2]

D [2, 1, 3]

💡 Hint

Look for the first pair from the right where the left number is smaller, then swap and reverse the tail.

The next permutation finds the next lexicographically greater sequence. For [1,3,2], the next is [2,1,3].

❓ Predict Output

intermediate

Next permutation of a descending array

What is the output after applying next permutation on the array [3, 2, 1]?

DSA C#

int[] arr = {3, 2, 1};
NextPermutation(arr);
Console.WriteLine(string.Join(", ", arr));

void NextPermutation(int[] nums) {
    int i = nums.Length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = nums.Length - 1;
        while (nums[j] <= nums[i]) j--;
        Swap(nums, i, j);
    }
    Reverse(nums, i + 1, nums.Length - 1);
}

void Swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void Reverse(int[] nums, int start, int end) {
    while (start < end) {
        Swap(nums, start, end);
        start++;
        end--;
    }
}

A [3, 2, 1]

B [1, 2, 3]

C [3, 1, 2]

D [2, 3, 1]

💡 Hint

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

The array is the highest permutation, so the next permutation resets to the lowest: sorted ascending.

🔧 Debug

advanced

Identify the error in this next permutation code

What error will this code produce when run on input [1, 2, 3]?

DSA C#

void NextPermutation(int[] nums) {
    int i = nums.Length - 2;
    while (i >= 0 && nums[i] > nums[i + 1]) i--;
    if (i >= 0) {
        int j = nums.Length - 1;
        while (nums[j] < nums[i]) j--;
        Swap(nums, i, j);
    }
    Reverse(nums, i + 1, nums.Length - 1);
}

void Swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void Reverse(int[] nums, int start, int end) {
    while (start < end) {
        Swap(nums, start, end);
        start++;
        end--;
    }
}

A No error, outputs [1, 3, 2]

B Wrong output: [1, 2, 3]

C IndexOutOfRangeException

D Infinite loop in while condition

💡 Hint

Check the comparison operators in the while loops carefully.

The code uses strict comparison signs (> instead of >= and < instead of <=), but for distinct elements like [1,2,3], it correctly finds the pivot i=1 and produces [1,3,2].

🧠 Conceptual

advanced

How many next permutations exist for an array of length 3?

For an array with 3 distinct elements, how many unique next permutations can be generated by repeatedly applying the next permutation algorithm until it cycles back?

A 3

B 5

C 6

D 4

💡 Hint

Think about how many ways to arrange 3 distinct elements.

There are 3! = 6 permutations total, so 6 unique next permutations cycle through all.

🚀 Application

expert

Find the 4th next permutation of [1, 2, 3]

Starting from the array [1, 2, 3], what is the array after applying the next permutation algorithm 4 times in a row?

DSA C#

int[] arr = {1, 2, 3};
for (int k = 0; k < 4; k++) {
    NextPermutation(arr);
}
Console.WriteLine(string.Join(", ", arr));

void NextPermutation(int[] nums) {
    int i = nums.Length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = nums.Length - 1;
        while (nums[j] <= nums[i]) j--;
        Swap(nums, i, j);
    }
    Reverse(nums, i + 1, nums.Length - 1);
}

void Swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void Reverse(int[] nums, int start, int end) {
    while (start < end) {
        Swap(nums, start, end);
        start++;
        end--;
    }
}

A [3, 1, 2]

B [2, 3, 1]

C [2, 1, 3]

D [3, 2, 1]

💡 Hint

List permutations in order and count four steps from the start.

The permutations in order are: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. The 4th next permutation after [1,2,3] is [3,1,2].

Practice

1. What does the Next Permutation algorithm do to an array of numbers?

easy

A. It finds the maximum element in the array.

B. It sorts the array in ascending order.

C. It reverses the array.

D. It rearranges the array to the next lexicographically greater permutation.

Solution

1. Step 1: Understand the purpose of Next Permutation

   The algorithm finds the next arrangement of numbers that is just larger than the current one in dictionary order.

2. Step 2: Compare with other options

   Sorting or reversing changes the order but does not guarantee the next immediate permutation. Finding max element is unrelated.

3. Final Answer:

   It rearranges the array to the next lexicographically greater permutation. -> Option D

4. Quick Check:

   Next permutation = next lexicographically greater order [OK]

Hint: Next permutation means next bigger arrangement in order [OK]

Common Mistakes:

• Confusing next permutation with sorting
• Thinking it just reverses the array
• Assuming it finds max element

2. Which of the following C# code snippets correctly swaps two elements nums[i] and nums[j] in an array?

easy

A. int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;

B. nums[i] = nums[j]; nums[j] = nums[i];

C. Swap(nums[i], nums[j]);

D. nums[i], nums[j] = nums[j], nums[i];

Solution

1. Step 1: Check correct swap syntax in C#

   Using a temporary variable to hold one value before swapping is the correct approach in C#.

2. Step 2: Analyze other options

   nums[i] = nums[j]; nums[j] = nums[i]; overwrites nums[i] before assigning to nums[j]. Swap(nums[i], nums[j]); is invalid without a defined method. nums[i], nums[j] = nums[j], nums[i]; is Python syntax, not C#.

3. Final Answer:

   int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; -> Option A

4. Quick Check:

   Use temp variable to swap in C# [OK]

Hint: Use temp variable to swap values in C# [OK]

Common Mistakes:

• Overwriting one element before saving it
• Using Python tuple swap syntax in C#
• Calling undefined Swap method

3. What is the output array after applying the Next Permutation algorithm once on int[] nums = {1, 3, 2}?

medium

A. [1, 2, 3]

B. [3, 1, 2]

C. [2, 1, 3]

D. [1, 3, 2]

Solution

1. Step 1: Find the first decreasing element from the right

   From right, 2 < 3 is false, but 3 > 1 is true, so pivot is at index 0 (value 1).

2. Step 2: Find the element just larger than pivot to the right and swap

   Element just larger than 1 on right is 2 at index 2. Swap 1 and 2: array becomes [2, 3, 1].

3. Step 3: Reverse the suffix after pivot index

   Reverse elements after index 0: [3, 1] reversed 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
• Confusing pivot position

4. Given the following code snippet for Next Permutation, what is the bug?

void NextPermutation(int[] nums) {
  int i = nums.Length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;
  if (i >= 0) {
    int j = nums.Length - 1;
    while (nums[j] <= nums[i]) j--;
    int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
  }
  Array.Reverse(nums, i, nums.Length - i);
}

medium

A. The Array.Reverse call has wrong start index; should be i + 1.

B. The first while loop condition is incorrect.

C. Swapping elements uses wrong indices.

D. The method does not handle empty arrays.

Solution

1. Step 1: Analyze Array.Reverse parameters

   Array.Reverse(nums, i, nums.Length - i) reverses from index i, but suffix to reverse starts at i+1.

2. Step 2: Correct the start index for reversal

   It should be Array.Reverse(nums, i + 1, nums.Length - (i + 1)) to reverse the suffix properly.

3. Final Answer:

   The Array.Reverse call has wrong start index; should be i + 1. -> Option A

4. Quick Check:

   Reverse suffix starting at i+1, not i [OK]

Hint: Reverse suffix from i+1, not i [OK]

Common Mistakes:

• Reversing from wrong index
• Ignoring empty array edge case
• Swapping wrong elements

5. You have an array nums = {5, 4, 3, 2, 1}. What will be the result after applying the Next Permutation algorithm once, and why?

hard

A. [5, 4, 3, 2, 1] because it is already the highest permutation.

B. [1, 2, 3, 4, 5] because the array is in descending order, so next permutation is the lowest ascending order.

C. [5, 4, 3, 2, 2] because the last element is decreased by one.

D. [1, 5, 4, 3, 2] because the first element is swapped with the smallest.

Solution

1. Step 1: Identify if array is highest permutation

   The array is strictly descending, so it is the highest lexicographical permutation.

2. Step 2: Apply rule for highest permutation

   Next permutation resets to the lowest order by sorting ascending, resulting in [1, 2, 3, 4, 5].

3. Final Answer:

   [1, 2, 3, 4, 5] because the array is in descending order, so next permutation is the lowest ascending order. -> Option B

4. Quick Check:

   Descending array next permutation = ascending order [OK]

Hint: Descending array resets to ascending order as next permutation [OK]

Common Mistakes:

• Thinking highest permutation stays same
• Decreasing last element incorrectly
• Swapping wrong elements