Next Permutation of Array in DSA Typescript - Execution Trace

Concept Flow - Next Permutation of Array

Start from right end

↓

Find first pair where nums[i

↓

If no such pair, reverse whole array -> Done

Yes↓

Find element nums[j

↓

Swap nums[i

↓

Reverse subarray from i+1 to end

↓

Done with next permutation

Find the next lexicographically greater permutation by identifying a pivot, swapping, and reversing the suffix.

Execution Sample

DSA Typescript

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]];
  }
  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--;
  }
}

This code modifies the input array to its next permutation in-place.

Execution Table

Step	Operation	i	j	Array State	Pointer Changes	Notes
1	Initialize i to length-2	4	-	[1, 2, 3, 6, 5, 4]	i=4	Start from second last index
2	Check nums[i] >= nums[i+1]	4	-	[1, 2, 3, 6, 5, 4]	i=4	5 >= 4 is true, decrement i
3	Check nums[i] >= nums[i+1]	3	-	[1, 2, 3, 6, 5, 4]	i=3	6 >= 5 is true, decrement i
4	Check nums[i] >= nums[i+1]	2	-	[1, 2, 3, 6, 5, 4]	i=2	3 >= 6 is false, stop decrementing
5	Initialize j to last index	2	5	[1, 2, 3, 6, 5, 4]	j=5	Start from end to find element > nums[i]
6	Check nums[j] <= nums[i]	2	5	[1, 2, 3, 6, 5, 4]	j=5	4 <= 3 is false, stop
7	Swap nums[i] and nums[j]	2	5	[1, 2, 4, 6, 5, 3]	Swap indices 2 and 5	Swap 3 and 4
8	Reverse subarray from i+1 to end	2	5	[1, 2, 4, 3, 5, 6]	Reverse indices 3 to 5	Reverse [6,5,3] to [3,5,6]
9	Done	2	5	[1, 2, 4, 3, 5, 6]	-	Next permutation found

💡 After reversing suffix, array is next permutation; process ends.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 7	After Step 8	Final
i	4	3	2	2	2	2	2
j	-	-	-	5	5	5	5
Array	[1,2,3,6,5,4]	[1,2,3,6,5,4]	[1,2,3,6,5,4]	[1,2,3,6,5,4]	[1,2,4,6,5,3]	[1,2,4,3,5,6]	[1,2,4,3,5,6]

Key Moments - 3 Insights

Why do we start looking for i from the right end (length-2) and not from the left?

Because the next permutation changes the suffix to the smallest bigger sequence. Starting from the right finds the first decreasing pair to pivot the change. See execution_table rows 1-4 where i moves left until nums[i]<nums[i+1].

Why do we reverse the subarray after swapping nums[i] and nums[j]?

Because the suffix after i was in descending order, reversing it makes it ascending, which is the smallest order to get the next permutation. See execution_table row 8 where reversal changes [6,5,3] to [3,5,6].

What if no i is found such that nums[i] < nums[i+1]?

It means the array is in descending order, the highest permutation. We reverse the whole array to get the lowest permutation. This is handled by i becoming -1 and reversing the entire array (not shown in this example).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of i and why does the loop stop decrementing i?

A i = 3, because nums[3] < nums[4]

B i = 2, because nums[2] < nums[3]

C i = 1, because nums[1] >= nums[2]

D i = 0, because nums[0] < nums[1]

💡 Hint

Check the 'i' column and 'Notes' in execution_table row 4.

At which step does the array first change from the original state?

A Step 6 - when j is found

B Step 8 - after reversing the suffix

C Step 7 - after swapping nums[i] and nums[j]

D Step 9 - final step

💡 Hint

Look at 'Array State' column changes in execution_table rows 6 and 7.

If the array was already in descending order, what would happen to i in the first while loop?

A i would become -1 and the whole array would be reversed

B i would stay at length-2 and no changes happen

C i would become 0 and swap with last element

D i would become length-1 and exit

💡 Hint

Refer to key_moments question 3 about no i found.

Concept Snapshot

Next Permutation Algorithm:
1. Find i from right where nums[i] < nums[i+1]
2. If none, reverse whole array
3. Find j from right where nums[j] > nums[i]
4. Swap nums[i], nums[j]
5. Reverse suffix from i+1 to end
Produces next lexicographically greater permutation in-place.

Full Transcript

The next permutation algorithm finds the next lexicographically greater arrangement of numbers. It starts from the right end to find the first index i where nums[i] is less than nums[i+1]. If no such i exists, the array is reversed to the smallest order. Otherwise, it finds an index j from the right where nums[j] is greater than nums[i], swaps nums[i] and nums[j], then reverses the subarray after i to get the next permutation. This process modifies the array in-place and ensures the next bigger permutation is found or resets to the smallest if none exists.

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