Next Permutation of Array in DSA Typescript - Deep Dive

Overview - Next Permutation of Array

What is it?

Next Permutation of Array is a way to rearrange numbers in an array to get the next bigger arrangement in order. If the array is already the biggest arrangement, it resets to the smallest. This helps find the next sequence without listing all possibilities. It works by changing the array in place, without extra space.

Why it matters

Without next permutation, finding the next bigger arrangement would mean generating all permutations and sorting them, which is slow and uses a lot of memory. This method quickly jumps to the next arrangement, saving time and space. It is useful in problems like generating combinations, solving puzzles, or optimizing sequences.

Where it fits

Before learning this, you should understand arrays and how to swap elements. After this, you can learn about permutations in general, backtracking algorithms, and combinatorial optimization.

Mental Model

Core Idea

Next permutation finds the next bigger sequence by changing the smallest possible part of the array to get a bigger number.

Think of it like...

Imagine you have a lock with numbers that you can turn. Next permutation is like turning the lock to the next combination that is just a little bigger than the current one, without skipping any combinations.

Array: [1, 2, 3]
Step 1: Find pivot (from right) where number is smaller than next
Step 2: Find number just bigger than pivot to the right
Step 3: Swap pivot and that number
Step 4: Reverse the part after pivot

Example:
1 2 3
 ^ pivot at 2
Swap 2 with 3
1 3 2
Reverse after pivot (only last element)
Result: 1 3 2

Build-Up - 7 Steps

1

Foundation

Understanding permutations and order

Concept: What permutations are and how they can be ordered.

A permutation is a way to arrange items in order. For example, for [1, 2, 3], permutations include [1, 2, 3], [1, 3, 2], [2, 1, 3], etc. These can be sorted in ascending order to list all possible arrangements.

Result

You understand that permutations are different orders of the same items and that they can be arranged from smallest to largest.

Understanding permutations as ordered sequences helps see why we want the 'next' one and how to move between them.

2

Foundation

Swapping and reversing array parts

Concept: How to swap two elements and reverse a part of an array.

Swapping means exchanging two elements in an array. Reversing means flipping the order of elements in a section. For example, swapping positions 1 and 2 in [1, 2, 3] gives [1, 3, 2]. Reversing from position 1 to end in [1, 3, 2] gives [1, 2, 3].

Result

You can change parts of an array to create new arrangements.

Knowing how to swap and reverse is essential to rearranging arrays efficiently.

3

Intermediate

Finding the pivot for next permutation

🤔Before reading on: do you think the pivot is the first or last place where the array decreases from right to left? Commit to your answer.

Concept: Identify the rightmost position where the array value is smaller than the next value to the right.

Starting from the end of the array, move left until you find a number that is smaller than the number immediately after it. This position is called the pivot. If no such position exists, the array is the highest permutation.

Result

You can find the pivot index or know the array is the last permutation.

Finding the pivot pinpoints where the next bigger arrangement can start, avoiding unnecessary checks.

4

Intermediate

Swapping pivot with next bigger element

🤔Before reading on: do you think we swap the pivot with the smallest or largest number bigger than it to the right? Commit to your answer.

Concept: Find the smallest number bigger than the pivot to the right and swap them.

From the right end, find the first number larger than the pivot value. Swap this number with the pivot. This step ensures the new sequence is just bigger than the old one.

Result

The pivot is replaced with the next bigger number, moving towards the next permutation.

Swapping with the smallest bigger number ensures the next permutation is the immediate next, not skipping any.

5

Intermediate

Reversing suffix after pivot

Concept: Reverse the part of the array after the pivot to get the smallest order.

After swapping, the part of the array to the right of the pivot is still in descending order. Reverse it to make it ascending, which gives the smallest possible sequence after the pivot.

Result

The array is rearranged to the next permutation in ascending order after the pivot.

Reversing the suffix resets it to the smallest order, completing the next permutation.

6

Advanced

Handling edge case: highest permutation resets

🤔Before reading on: do you think the highest permutation returns itself or resets to lowest? Commit to your answer.

Concept: If no pivot is found, the array is the highest permutation and must reset to the lowest.

If the array is in descending order (like [3, 2, 1]), it is the highest permutation. The next permutation is the lowest one, which is the array sorted ascending. We reverse the whole array to reset.

Result

The array resets to the smallest permutation when no next bigger arrangement exists.

Recognizing this edge case prevents errors and completes the cycle of permutations.

7

Expert

In-place algorithm and time complexity

🤔Before reading on: do you think next permutation requires extra memory or can be done in-place? Commit to your answer.

Concept: The algorithm modifies the array in place with O(n) time and O(1) extra space.

The steps only swap and reverse parts of the original array without extra arrays. Finding the pivot and swapping take linear time. This makes it efficient for large arrays and practical use.

Result

You understand the algorithm is optimal in time and space for this problem.

Knowing the algorithm is in-place and linear time explains why it is preferred in performance-critical applications.

Under the Hood

The algorithm scans the array from right to left to find the pivot where the order breaks ascending. It then finds the next bigger element to swap with the pivot. After swapping, the suffix is reversed to restore ascending order. This works because permutations are ordered lexicographically, and these steps move to the next lexicographic permutation.

Why designed this way?

This method was designed to efficiently find the next permutation without generating all permutations. It uses the properties of lexicographic order and minimal changes to jump directly to the next sequence. Alternatives like generating all permutations are costly, so this approach balances speed and memory.

Array: [a1, a2, ..., apivot, ..., an]

Step 1: Find pivot (apivot < apivot+1)
          ↓
[a1, a2, ..., apivot, ..., an]

Step 2: Find successor (as) > apivot to the right
          ↓
Swap apivot and as

Step 3: Reverse suffix after pivot
          ↓
Result: next permutation

Myth Busters - 4 Common Misconceptions

Quick: Does next permutation always produce a bigger number? Commit yes or no.

Common Belief: Next permutation always gives a bigger number than the current one.

Reality: If the current permutation is the highest, next permutation resets to the smallest, which is smaller than the current.

Why it matters: Assuming it always increases can cause bugs when handling the last permutation, leading to wrong results or infinite loops.

Quick: Is it necessary to generate all permutations to find the next one? Commit yes or no.

Common Belief: You must generate all permutations and sort them to find the next permutation.

Reality: Next permutation algorithm finds the next sequence directly without generating all permutations.

Why it matters: Generating all permutations is inefficient and impractical for large arrays, causing performance issues.

Quick: Does reversing the suffix after swapping always increase the permutation? Commit yes or no.

Common Belief: Reversing the suffix after swapping the pivot always increases the permutation.

Reality: Reversing the suffix resets it to the smallest order, which may be smaller than before but ensures the overall permutation is the next bigger one.

Why it matters: Misunderstanding this can lead to incorrect implementations that do not produce the correct next permutation.

Quick: Can next permutation be done without modifying the original array? Commit yes or no.

Common Belief: Next permutation requires creating a new array and cannot be done in place.

Reality: The algorithm modifies the array in place using swaps and reverses, no extra array needed.

Why it matters: Thinking extra memory is needed can lead to inefficient code and misunderstanding of the algorithm's efficiency.

Expert Zone

1

The pivot is always the rightmost position where the ascending order breaks, ensuring minimal change to get the next permutation.

2

Reversing the suffix after swapping is crucial because the suffix is in descending order, and reversing it gives the smallest possible order, completing the next permutation.

3

The algorithm works lexicographically, meaning it treats the array like a number and finds the next bigger number with the same digits.

When NOT to use

Next permutation is not suitable when you need all permutations or random permutations. For those, use backtracking or random shuffling algorithms instead.

Production Patterns

Used in combinatorial problems, generating sequences in lex order, solving puzzles like the traveling salesman problem, and in optimization algorithms where next state exploration is needed.

Connections

Lexicographic Order

Next permutation builds on lexicographic ordering of sequences.

Understanding lexicographic order clarifies why the algorithm finds the next bigger sequence by minimal changes.

Backtracking Algorithms

Next permutation can be used to generate permutations iteratively instead of recursively backtracking.

Knowing next permutation helps optimize permutation generation by avoiding recursion and reducing memory use.

Number Systems and Counting

Next permutation is like counting in a mixed base system where digits are array elements.

Seeing permutations as numbers in a counting system helps understand the stepwise increment to the next permutation.

Common Pitfalls

#1 Not handling the case when the array is the highest permutation.

Wrong approach:

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

Correct approach:

function nextPermutation(nums: number[]) {
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]];
}
reverse(nums, i + 1);
}
function reverse(nums: number[], start: number) {
let left = start, right = nums.length - 1;
while (left < right) {
[nums[left], nums[right]] = [nums[right], nums[left]];
left++;
right--;
}
}

Root cause:

Forgetting to reverse the entire array when no pivot is found causes the array to remain in the highest permutation state.

#2 Swapping pivot with wrong element (not the next bigger one).

Wrong approach:

let j = i + 1;
while (j < nums.length && nums[j] > nums[i]) {
j++;
}
[nums[j - 1], nums[i]] = [nums[i], nums[j - 1]]; // swaps with largest bigger instead of smallest bigger

Correct approach:

let j = nums.length - 1;
while (nums[j] <= nums[i]) {
j--;
}
[nums[i], nums[j]] = [nums[j], nums[i]];

Root cause:

Not searching from the right end for the smallest bigger element leads to swapping with a larger element, skipping permutations.

#3 Not reversing the suffix after swapping.

Wrong approach:

function nextPermutation(nums: number[]) {
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]];
}
// Missing reverse here
}

Correct approach:

function nextPermutation(nums: number[]) {
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]];
}
reverse(nums, i + 1);
}
function reverse(nums: number[], start: number) {
let left = start, right = nums.length - 1;
while (left < right) {
[nums[left], nums[right]] = [nums[right], nums[left]];
left++;
right--;
}
}

Root cause:

Skipping the reverse step leaves the suffix in descending order, resulting in a permutation that is not the immediate next.

Key Takeaways

Next permutation finds the next bigger arrangement of an array by changing the smallest possible part.

It works by finding a pivot where the order breaks, swapping it with the next bigger element, and reversing the suffix.

If the array is the highest permutation, it resets to the lowest by reversing the whole array.

The algorithm runs in linear time and modifies the array in place without extra memory.

Understanding this algorithm helps efficiently generate permutations and solve related problems.

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