Next Permutation of Array in DSA C#

Mental Model

Find the next bigger arrangement of numbers by changing the smallest possible part of the array.

Analogy: Imagine you have a lock with numbers. To get the next code, you try to increase the last digits first, but if you can't, you move left until you find a digit you can increase, then reset the digits to the right to the smallest order.

Array: [1] -> [2] -> [3] -> [4] -> [5]
Indexes:  0      1      2      3      4

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Find the next permutation after [1, 2, 3], which is the next bigger number using the same digits

Step 1: Find the first index from the right where array[i] < array[i+1]

[1, 2, 3] ↑ i=1 (since 2 < 3)

Why: We need to find where the order breaks from the right to find the pivot to increase

Step 2: Find the first index from the right where array[j] > array[i]

[1, 2, 3] ↑ j=2 (3 > 2)

Why: We find the number just bigger than array[i] to swap with

Step 3: Swap array[i] and array[j]

[1, 3, 2]

Why: Swapping increases the number minimally

Step 4: Reverse the subarray from i+1 to end

[1, 3, 2]

Why: Reversing makes the tail the smallest possible order to get the next permutation

Result:

[1, 3, 2]

Annotated Code

DSA C#

using System;

class NextPermutation {
    public static void NextPerm(int[] nums) {
        int i = nums.Length - 2;
        // Find first decreasing element from right
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.Length - 1;
            // Find element just bigger than nums[i]
            while (nums[j] <= nums[i]) {
                j--;
            }
            // Swap nums[i] and nums[j]
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        } else {
            // If no such index i, reverse the whole array
            Reverse(nums, 0, nums.Length - 1);
            return;
        }
        // Reverse from i+1 to end
        Reverse(nums, i + 1, nums.Length - 1);
    }

    private static void Reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

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

while (i >= 0 && nums[i] >= nums[i + 1]) { i--; }

Find first index i from right where nums[i] < nums[i+1]

while (nums[j] <= nums[i]) { j--; }

Find index j from right where nums[j] > nums[i]

Swap nums[i] and nums[j]

Swap to increase the permutation minimally

Reverse(nums, i + 1, nums.Length - 1);

Reverse the tail to get the smallest order after swap

Output

1, 3, 2

Complexity Analysis

Time: O(n) because we scan the array from right to left a few times and reverse a subarray once

Space: O(1) because all operations are done in place without extra arrays

vs Alternative: Naive approach would generate all permutations and find the next one, which is O(n!) and very inefficient

Edge Cases

Array is in descending order like [3, 2, 1]

The code reverses the entire array to the smallest permutation [1, 2, 3]

DSA C#

if (i >= 0) { ... } else Reverse(nums, 0, nums.Length - 1);

Array with all identical elements like [2, 2, 2]

No next permutation exists, array remains the same after reversal

DSA C#

while (i >= 0 && nums[i] >= nums[i + 1]) { i--; }

Single element array like [1]

No change, array remains the same

DSA C#

while (i >= 0 && nums[i] >= nums[i + 1]) { i--; }

When to Use This Pattern

When asked to find the next bigger arrangement or permutation of a sequence, use the next permutation pattern to efficiently find it without generating all permutations.

Common Mistakes

Mistake: Not reversing the tail after swapping, resulting in a wrong next permutation
Fix: Always reverse the subarray after the swapped index to get the smallest tail order

Mistake: Swapping the wrong elements or not finding the correct j index
Fix: Find j as the first element from the right greater than nums[i]

Summary

Finds the next lexicographically bigger permutation of an array in place.

Use when you need the next order of elements without generating all permutations.

The key is to find the pivot from right, swap with just bigger element, then reverse the tail.

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