Next Permutation of Array in DSA C# - Build from Scratch

Next Permutation of Array

📖 Scenario: You are working on a feature for a puzzle game where players can rearrange numbers to find the next possible combination in order.To help the game, you need to write code that finds the next permutation of a list of numbers.

🎯 Goal: Build a program that takes an array of integers and rearranges it to the next lexicographically greater permutation. If no such permutation exists, rearrange it to the lowest possible order (sorted ascending).

📋 What You'll Learn

Create an integer array called nums with the exact values {1, 2, 3}.

Create an integer variable called i initialized to nums.Length - 2.

Use a while loop to find the first index i from the right where nums[i] < nums[i + 1].

If such i is found, create an integer variable j initialized to nums.Length - 1.

Use a while loop to find the first index j from the right where nums[j] > nums[i].

Swap nums[i] and nums[j].

Reverse the sub-array from i + 1 to the end of the array.

Print the final state of the nums array as a sequence of numbers separated by spaces.

💡 Why This Matters

🌍 Real World

Finding the next permutation is useful in games, puzzles, and algorithms that need to generate all possible orderings.

💼 Career

Understanding permutations helps in coding interviews and solving problems related to combinatorics and sequence generation.

1

Create the initial array

Create an integer array called nums with the exact values {1, 2, 3}.

DSA C#

# Create the integer array nums with values {1, 2, 3}
# Your code here

Hint

Use int[] nums = {1, 2, 3}; to create the array.

2

Find the first decreasing element from the right

Create an integer variable called i and set it to nums.Length - 2. Use a while loop to decrease i while i >= 0 and nums[i] >= nums[i + 1].

DSA C#

int[] nums = {1, 2, 3};
// Find the first index i from the right where nums[i] < nums[i + 1]
// Your code here

Hint

Start from the second last index and move left while the current number is not less than the next.

3

Find the element to swap and swap

If i >= 0, create an integer variable j set to nums.Length - 1. Use a while loop to decrease j while nums[j] <= nums[i]. Swap nums[i] and nums[j]. Then reverse the sub-array from i + 1 to the end of the array.

DSA C#

int[] nums = {1, 2, 3};
int i = nums.Length - 2;
while (i >= 0 && nums[i] >= nums[i + 1])
{
    i--;
}
// If i >= 0, find j and swap nums[i] and nums[j]
// Then reverse the sub-array from i+1 to end
// Your code here

Hint

Swap the numbers at i and j, then reverse the part of the array after i.

4

Print the next permutation

Print the elements of the nums array separated by spaces using Console.WriteLine.

DSA C#

int[] nums = {1, 2, 3};
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;
}
int left = i + 1;
int right = nums.Length - 1;
while (left < right)
{
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
    left++;
    right--;
}
// Print the nums array separated by spaces
// Your code here

Hint

Use Console.WriteLine(string.Join(" ", nums)); to print the array elements separated by spaces.

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