Next Permutation of Array in DSA C# - Time & Space Complexity

Time Complexity: Next Permutation of Array

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the next permutation changes as the array size grows.

How does the number of steps grow when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

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

This code finds the next lexicographical permutation of the array in place.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loops that scan the array from the end to find the pivot and the element to swap, plus the reverse operation.
• How many times: Each loop can run up to n times in the worst case, where n is the array length.

How Execution Grows With Input

As the array size grows, the number of steps grows roughly in a straight line with the size.

Input Size (n)	Approx. Operations
10	About 10 to 30 steps
100	About 100 to 300 steps
1000	About 1000 to 3000 steps

Pattern observation: The steps increase roughly in direct proportion to the array size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the next permutation grows linearly with the size of the array.

Common Mistake

[X] Wrong: "The algorithm checks every possible permutation, so it must be exponential time."

[OK] Correct: The algorithm only scans the array a few times and does swaps and reversals, so it runs in linear time, not exponential.

Interview Connect

Understanding this linear time solution shows you can handle array manipulation and think about efficient scanning, which is a valuable skill in many coding problems.

Self-Check

"What if we used a sorting method instead of reversing the suffix? How would the time complexity change?"

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