Next Permutation of Array in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the purpose of the Next Permutation algorithm?

It finds the next lexicographically greater permutation of an array of numbers. If no such permutation exists (the array is in descending order), it rearranges the array to the lowest possible order (ascending).

intermediate

In the Next Permutation algorithm, what is the significance of finding the 'pivot' index?

The pivot is the first index from the right where the number is smaller than the number immediately after it. It marks the position where we can make a change to get a bigger permutation.

intermediate

Why do we reverse the suffix (the part of the array after the pivot) in the Next Permutation algorithm?

Because the suffix is in descending order, reversing it makes it ascending, which is the smallest order. This ensures the next permutation is just one step bigger than the current one.

beginner

What happens if the array is already in descending order when applying Next Permutation?

The algorithm reverses the entire array to transform it into ascending order, which is the smallest permutation possible.

beginner

Show the step-by-step changes to the array [1, 3, 2] when applying Next Permutation.

1. Find pivot: index 0 (value 1) because 1 < 3.
2. Find successor: index 2 (value 2) because 2 > 1.
3. Swap pivot and successor: [2, 3, 1].
4. Reverse suffix after pivot: suffix is [3, 1], reversed to [1, 3].
Final array: [2, 1, 3].

What is the first step in finding the next permutation of an array?

A Find the first index from the right where the number is smaller than the next number

B Reverse the entire array

C Swap the first and last elements

D Sort the array in ascending order

The first step is to find the pivot index where the number is smaller than the number immediately after it, scanning from right to left.

If no pivot is found in the array, what does the Next Permutation algorithm do?

A Leaves the array unchanged

B Reverses the entire array

C Swaps the first two elements

D Sorts the array in descending order

If the array is in descending order, no pivot exists, so the algorithm reverses the entire array to get the smallest permutation.

After swapping the pivot with the successor, what is the next step?

A Reverse the suffix after the pivot

B Sort the entire array

C Swap the first and last elements

D Do nothing

The suffix after the pivot is reversed to transform it from descending to ascending order, ensuring the next permutation is minimal.

What is the time complexity of the Next Permutation algorithm?

A O(n^2)

B O(n log n)

C O(n)

D O(1)

The algorithm scans the array a few times linearly, so the time complexity is O(n).

Given the array [1, 2, 3], what is the next permutation?

A [1, 2, 3]

B [3, 2, 1]

C [2, 1, 3]

D [1, 3, 2]

The next permutation after [1, 2, 3] is [1, 3, 2], which is the next lexicographically greater arrangement.

Explain the steps of the Next Permutation algorithm and why each step is necessary.

Think about how to get the next bigger number by changing the array minimally.

Describe how the Next Permutation algorithm changes the array [3, 2, 1] and why.

Consider what happens when the array is already the biggest permutation.

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