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

Recall & Review

beginner

What is the goal of the Next Permutation algorithm?

To rearrange numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it rearranges to the lowest possible order (sorted ascending).

intermediate

In the Next Permutation algorithm, what is the significance of finding the first decreasing element from the right?

It identifies the pivot point where the next permutation can be generated by swapping and rearranging elements to the right of this pivot.

intermediate

Why do we reverse the suffix after swapping in the Next Permutation algorithm?

Because the suffix is in descending order, reversing it makes it the smallest ascending order, ensuring the next permutation is just one step greater.

beginner

TypeScript snippet: How do you swap two elements in an array at indices i and j?

const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

beginner

What happens if the entire array is in descending order in the Next Permutation algorithm?

It means the current permutation is the highest possible. The algorithm reverses the entire array to get the lowest permutation (ascending order).

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

A Swap the first and last elements

B Reverse the entire array

C Sort the array in ascending order

D Find the first element from the right that is smaller than the element next to it

The algorithm starts by finding the first decreasing element from the right to identify the pivot.

After finding the pivot, what is the next step in the Next Permutation algorithm?

A Reverse the entire array

B Sort the array in descending order

C Swap the pivot with the smallest element to its right that is greater than it

D Swap the pivot with the first element

Swapping the pivot with the next bigger element ensures the next permutation is just larger.

Why do we reverse the suffix after swapping in the Next Permutation algorithm?

A To get the largest possible order for the suffix

B To get the smallest possible order for the suffix

C To sort the entire array

D To swap the first and last elements

Reversing the suffix changes it from descending to ascending order, making the permutation next smallest.

If no pivot is found (array is fully descending), what does the Next Permutation algorithm do?

A Reverses the entire array to ascending order

B Leaves the array unchanged

C Sorts the array in descending order

D Swaps the first two elements

This resets the array to the lowest permutation since the current is the highest.

What is the time complexity of the Next Permutation algorithm?

A O(n)

B O(n log n)

C O(n^2)

D O(1)

The algorithm scans the array a few times linearly, so it runs in O(n) time.

Explain the steps to find the next permutation of an array.

Think about how to get the next bigger number by rearranging digits.

Describe what happens when the array is in descending order in the Next Permutation algorithm.

Consider what the next permutation means if you are already at the last one.

Practice

1. What does the next permutation of an array represent?

easy

A. The smallest element moved to the front

B. The array sorted in ascending order

C. The array reversed

D. The next lexicographically greater arrangement of the array elements

Solution

1. Step 1: Understand permutation order

   Permutations can be ordered lexicographically like words in a dictionary.

2. Step 2: Define next permutation

   The next permutation is the immediate next arrangement that is greater than the current one.

3. Final Answer:

   The next lexicographically greater arrangement of the array elements -> Option D

4. Quick Check:

   Next permutation means next bigger order [OK]

Hint: Next permutation means next bigger order of elements [OK]

Common Mistakes:

• Thinking next permutation is just sorting ascending
• Confusing next permutation with reversing the array
• Assuming next permutation always moves smallest element front

2. Which of the following TypeScript function signatures correctly represents a function to compute the next permutation of an array of numbers?

easy

A. function nextPermutation(nums: number[]): void

B. function nextPermutation(nums: string): string

C. function nextPermutation(nums: number): number[]

D. function nextPermutation(nums: any): any[]

Solution

1. Step 1: Check parameter type

   The input should be an array of numbers, so nums: number[] is correct.

2. Step 2: Check return type

   The function modifies the array in place and returns nothing, so void is correct.

3. Final Answer:

   function nextPermutation(nums: number[]): void -> Option A

4. Quick Check:

   Input array, no return needed [OK]

Hint: Input array of numbers, modify in place, return void [OK]

Common Mistakes:

• Using string type instead of number array
• Returning a new array instead of modifying in place
• Using incorrect parameter types

3. What is the output array after applying the next permutation algorithm on [1, 3, 2]?

medium

A. [2, 1, 3]

B. [1, 2, 3]

C. [3, 1, 2]

D. [1, 3, 2]

Solution

1. Step 1: Find the pivot index i

   Start from i = nums.length - 2 = 1. nums[1] = 3 >= nums[2] = 2, so i-- to 0. nums[0] = 1 < nums[1] = 3, pivot i = 0.

2. Step 2: Find successor j

   From j = nums.length - 1 = 2, find rightmost j > i with nums[j] > nums[i]. j=2: 2 > 1, yes.

3. Step 3: Swap pivot and successor

   Swap nums[0] and nums[2]: [2, 3, 1].

4. Step 4: Reverse suffix after i

   Reverse indices 1 to 2: [3, 1] becomes [1, 3]. Final: [2, 1, 3].

5. Final Answer:

   [2, 1, 3] -> Option A

6. Quick Check:

   Next permutation of [1,3,2] is [2,1,3] [OK]

Hint: Find pivot, swap with next bigger, reverse suffix [OK]

Common Mistakes:

• Swapping wrong elements
• Not reversing suffix after swap
• Confusing next permutation with sorting

4. Given this TypeScript code snippet, what is the error?

function nextPermutation(nums: number[]): void {
  let i = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }
  if (i >= 0) {
    let j = nums.length - 1;
    while (nums[j] <= nums[i]) {
      j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
  nums.reverse();
}

medium

A. The while loops have wrong conditions

B. The entire array is reversed instead of just the suffix

C. The swap syntax is incorrect

D. The function returns a value but should be void

Solution

1. Step 1: Analyze reversal step

   The code reverses the entire array with nums.reverse() instead of just the suffix after index i+1.

2. Step 2: Understand correct reversal

   Only the part of the array after the pivot index should be reversed to get the next permutation.

3. Final Answer:

   The entire array is reversed instead of just the suffix -> Option B

4. Quick Check:

   Reverse suffix, not whole array [OK]

Hint: Reverse only suffix after pivot, not whole array [OK]

Common Mistakes:

• Reversing entire array instead of suffix
• Incorrect swap syntax
• Wrong loop conditions causing errors

5. You have an array [5, 4, 3, 2, 1]. After applying the next permutation algorithm, what will be the resulting array?

hard

A. [5, 4, 3, 1, 2]

B. [5, 4, 3, 2, 1]

C. [1, 2, 3, 4, 5]

D. [1, 5, 4, 3, 2]

Solution

1. Step 1: Check if array is highest permutation

   The array is in descending order, which is the highest permutation.

2. Step 2: Apply next permutation rule for highest permutation

   If no next bigger permutation exists, the array is reversed to the lowest permutation.

3. Final Answer:

   [1, 2, 3, 4, 5] -> Option C

4. Quick Check:

   Descending array next permutation is ascending [OK]

Hint: Descending array next permutation is ascending order [OK]

Common Mistakes:

• Returning same array instead of reversed
• Trying to swap elements incorrectly
• Confusing next permutation with partial sorting