Next Permutation of Array in DSA Typescript

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 without changing the earlier ones too much.

Array: [1, 2, 3, 4, 5]
Indexes:  0  1  2  3  4
We want to find the next bigger order by changing from the right side.

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Find the next permutation which is just bigger than current: [1, 3, 2]

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

[1, 2, 3] with i=1 because 2 < 3

Why: We want to find the place where we can increase the number to get a bigger permutation

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

[1, 2, 3] with j=2 because 3 > 2

Why: We want to swap with a number just bigger than array[i] to get the next bigger permutation

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

[1, 3, 2]

Why: Swapping increases the number at i to the next bigger number

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 Typescript

class NextPermutation {
  static nextPermutation(nums: number[]): void {
    let i = nums.length - 2;
    // Find first decreasing element from right
    while (i >= 0 && nums[i] >= nums[i + 1]) {
      i--;
    }
    if (i >= 0) {
      let j = nums.length - 1;
      // Find element just bigger than nums[i]
      while (nums[j] <= nums[i]) {
        j--;
      }
      // Swap nums[i] and nums[j]
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    // Reverse from i+1 to end
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
      right--;
    }
  }
}

// Driver code
const arr = [1, 2, 3];
NextPermutation.nextPermutation(arr);
console.log(arr.join(", "));

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]

[nums[i], nums[j]] = [nums[j], nums[i]];

Swap nums[i] and nums[j] to increase permutation minimally

while (left < right) { [nums[left], nums[right]] = [nums[right], nums[left]]; left++; right--; }

Reverse the subarray after i to get smallest order

Output

1, 3, 2

Complexity Analysis

Time: O(n) because we scan the array from right to left a few times but only once overall

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

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 algorithm reverses the entire array to the smallest permutation [1, 2, 3]

DSA Typescript

if (i >= 0) { ... } handles no increasing pair found

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

No next bigger permutation exists, so array stays the same after reversal

DSA Typescript

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

Array with two elements like [1, 2]

Swaps to [2, 1] which is the next permutation

DSA Typescript

General logic applies without special case

When to Use This Pattern

When asked to find the next bigger arrangement of numbers or letters in order, use the next permutation pattern because it efficiently finds the minimal change to get the next order.

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

Mistake: Swapping with the wrong element that is not just bigger than nums[i]
Fix: Find the rightmost element greater than nums[i] to swap

Summary

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

Use when you need to generate permutations in order or find the next arrangement.

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

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