Next Permutation of Array in DSA C# - Execution Trace

Concept Flow - Next Permutation of Array

Start from right end

↓

Find first pair where nums[i

↓

If no such pair, reverse whole array and STOP

↓

Find element nums[j

↓

Swap nums[i

↓

Reverse subarray nums[i+1

↓

Done: Next permutation formed

Find the next bigger arrangement by swapping and reversing parts of the array.

Execution Sample

DSA C#

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);

This code finds the next permutation of the array by locating a pivot, swapping, and reversing the suffix.

Execution Table

Step	Operation	Index i	Index j	Array State	Pointer Changes
1	Initialize i at second last index	4	-	[1, 2, 3, 6, 5, 4]	i=4, j=undefined
2	Check nums[i] >= nums[i+1]? 5 >= 4	4	-	[1, 2, 3, 6, 5, 4]	i=4 (5 >= 4 true)
3	Check nums[i] >= nums[i+1]? 6 >= 5	3	-	[1, 2, 3, 6, 5, 4]	i=3 (6 >= 5 true)
4	Check nums[i] >= nums[i+1]? 3 >= 6	2	-	[1, 2, 3, 6, 5, 4]	i=2 (3 >= 6 false)
5	Find element nums[j] > nums[i] from right	2	4	[1, 2, 3, 6, 5, 4]	j=4 (5 > 3)
6	Swap nums[i] and nums[j]	2	4	[1, 2, 5, 6, 3, 4]	Swapped indices 2 and 4
7	Reverse subarray from i+1 to end	2	5	[1, 2, 5, 4, 3, 6]	Reversed subarray 3 to 5
8	Done - next permutation formed	-	-	[1, 2, 5, 4, 3, 6]	Final array state

💡 i found at 2 where nums[2] < nums[3], swap and reverse suffix to get next permutation

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 6	After Step 7	Final
i	undefined	4	2	2	2	2	-
j	undefined	-	-	4	4	4	-
Array	[1, 2, 3, 6, 5, 4]	[1, 2, 3, 6, 5, 4]	[1, 2, 3, 6, 5, 4]	[1, 2, 3, 6, 5, 4]	[1, 2, 5, 6, 3, 4]	[1, 2, 5, 4, 3, 6]	[1, 2, 5, 4, 3, 6]

Key Moments - 3 Insights

Why do we start searching for i from the right end of the array?

Because we want to find the first place from the right where the order breaks (nums[i] < nums[i+1]) to find the smallest change for the next bigger permutation. See execution_table rows 1-4.

What if no such i is found where nums[i] < nums[i+1]?

It means the array is in descending order, which is the highest permutation. We reverse the whole array to get the lowest permutation. This is the exit condition before step 5.

Why do we reverse the subarray after swapping?

Because the subarray after i was in descending order, reversing it makes it ascending, giving the next smallest permutation after the swap. See execution_table step 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the value of j and why?

A j = 4 because nums[4] > nums[2]

B j = 3 because nums[3] > nums[2]

C j = 5 because nums[5] > nums[2]

D j = 2 because nums[2] > nums[2]

💡 Hint

Check the 'Index j' and 'Pointer Changes' columns at step 5 in execution_table.

At which step does the array first change its order?

A Step 4 - when i is found

B Step 7 - after reversing subarray

C Step 6 - after swapping elements

D Step 2 - initial check

💡 Hint

Look at the 'Array State' column to see when the array elements change.

If the array was already in descending order, what would happen?

A The algorithm would do nothing

B The array would be reversed entirely to ascending order

C The algorithm would swap the first two elements

D The algorithm would throw an error

💡 Hint

Refer to key_moments question 2 about no i found condition.

Concept Snapshot

Next Permutation Algorithm:
- Start from right, find i where nums[i] < nums[i+1]
- If none, reverse whole array (lowest order)
- Else find j > i from right where nums[j] > nums[i]
- Swap nums[i] and nums[j]
- Reverse subarray from i+1 to end
- Result is next lexicographically bigger permutation

Full Transcript

The next permutation algorithm finds the next bigger arrangement of numbers by scanning from the right to find the first decreasing element. If none is found, the array is reversed to the smallest order. Otherwise, it finds a number just bigger than this element to swap with, then reverses the suffix to get the next permutation. This process ensures the next permutation is the smallest possible bigger number than the current arrangement.

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