Next Permutation of Array in DSA Javascript - Execution Trace

Concept Flow - Next Permutation of Array

Start from right end

↓

Find first i where arr[i

Yes↓

Find j from right where arr[j

↓

Swap arr[i

↓

Reverse subarray from i+1 to end

↓

Done - next permutation found

No↓

Reverse whole array - last permutation reached

Find the next bigger arrangement by swapping and reversing parts of the array.

Execution Sample

DSA Javascript

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

function reverse(arr, start) {
  let left = start, right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
}

This code finds the next permutation of the array by swapping and reversing parts.

Execution Table

Step	Operation	i	j	Array State	Notes
1	Initialize i at length-2	3	-	[1, 2, 3, 6, 5, 4]	Start from second last index
2	Check arr[i] >= arr[i+1]	3	-	[1, 2, 3, 6, 5, 4]	6 >= 5 is True, decrement i
3	Decrement i	2	-	[1, 2, 3, 6, 5, 4]	Now i=2
4	Check arr[i] >= arr[i+1]	2	-	[1, 2, 3, 6, 5, 4]	3 >= 6 is False, stop
5	Initialize j at end	2	5	[1, 2, 3, 6, 5, 4]	j starts at last index
6	Check arr[j] <= arr[i]	2	5	[1, 2, 3, 6, 5, 4]	4 <= 3 is False, stop
7	Swap arr[i] and arr[j]	2	5	[1, 2, 4, 6, 5, 3]	Swap 3 and 4
8	Reverse from i+1 to end	2	5	[1, 2, 4, 3, 5, 6]	Reverse subarray [6,5,3] to [3,5,6]
9	End	-	-	[1, 2, 4, 3, 5, 6]	Next permutation found

💡 Loop ends when i < 0 or next permutation is formed

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 7	Final
i	3	2	2	2	2	-
j	-	-	-	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]

Key Moments - 3 Insights

Why do we start looking for i from the right end of the array?

Because we want to find the first place from the right where the order breaks (arr[i] < arr[i+1]) to find the next bigger permutation. See execution_table steps 1-4.

Why do we reverse the subarray after swapping?

Because the subarray after i is in descending order, reversing it makes it the smallest order, ensuring the next permutation is just one step bigger. See execution_table step 8.

What happens if no such i is found (i < 0)?

It means the array is in the highest permutation order, so we reverse the whole array to get the smallest permutation. This is the exit condition in the flow.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of i?

A 3

B 2

C 1

D 4

💡 Hint

Check the 'i' column in execution_table row with Step 4

At which step does the array first change its order?

A Step 7

B Step 6

C Step 8

D Step 5

💡 Hint

Look at the 'Array State' column and see when the swap happens

If the array was already in descending order, what would happen?

A i would be found and swap happens

B j would be less than i

C The whole array would be reversed

D Nothing changes

💡 Hint

Refer to concept_flow and key_moments about when i < 0

Concept Snapshot

Next Permutation Algorithm:
1. Find i from right where arr[i] < arr[i+1]
2. If found, find j from right where arr[j] > arr[i]
3. Swap arr[i] and arr[j]
4. Reverse subarray from i+1 to end
5. If no i found, reverse whole array
This finds the next lexicographically bigger permutation.

Full Transcript

The next permutation algorithm finds the next bigger arrangement of numbers by scanning from the right to find the first pair where the order breaks. It swaps elements to increase the number slightly and reverses the tail to get the smallest bigger number. If no such pair exists, it reverses the whole array to start over from the smallest permutation.

Practice

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

easy

A. The next lexicographically greater arrangement of the array elements

B. The array sorted in ascending order

C. The array reversed

D. The smallest element moved to the front

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 next arrangement that is just greater than the current one in this order.

3. Final Answer:

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

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 JavaScript code snippets correctly swaps two elements arr[i] and arr[j] in an array?

easy

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

B. arr[i], arr[j] = arr[j], arr[i];

C. [arr[i], arr[j]] = arr[j];

D. swap(arr[i], arr[j]);

Solution

1. Step 1: Understand JavaScript swap syntax

   JavaScript does not support tuple unpacking like Python; swapping requires a temporary variable or destructuring.

2. Step 2: Check each option

   const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temporary variable correctly. arr[i], arr[j] = arr[j], arr[i]; is invalid syntax. [arr[i], arr[j]] = arr[j]; is incomplete. swap(arr[i], arr[j]); calls undefined function.

3. Final Answer:

   const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option A

4. Quick Check:

   Use temp variable to swap [OK]

Hint: Use temp variable or destructuring to swap elements [OK]

Common Mistakes:

• Using Python-style tuple swap in JavaScript
• Calling undefined swap function
• Assigning without temporary variable causing overwrite

3. What is the output of the following JavaScript code?

function nextPermutation(arr) {
  let i = arr.length - 2;
  while (i >= 0 && arr[i] >= arr[i + 1]) i--;
  if (i >= 0) {
    let j = arr.length - 1;
    while (arr[j] <= arr[i]) j--;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  let left = i + 1, right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  return arr;
}

console.log(nextPermutation([1, 3, 2]));

medium

A. [1, 2, 3]

B. [2, 1, 3]

C. [1, 3, 2]

D. [3, 1, 2]

Solution

1. Step 1: Find first decreasing element from right

   i starts at index 1 (value 3), arr[1] >= arr[2] (3 >= 2) true, so i-- to 0. arr[0] = 1, arr[1] = 3, 1 < 3, stop at i=0.

2. Step 2: Find element to swap with arr[i]

   j starts at 2 (value 2), arr[2] > arr[0] (2 > 1) true, swap arr[0] and arr[2]: array becomes [2, 3, 1]. Then reverse from i+1=1 to end: reverse [3,1] to [1,3]. Final array: [2,1,3].

3. Final Answer:

   [2, 1, 3] -> Option B

4. Quick Check:

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

Hint: Find first decreasing from right, swap, then reverse tail [OK]

Common Mistakes:

• Not reversing the tail after swap
• Swapping wrong elements
• Confusing >= with > in conditions

4. The following code attempts to find the next permutation of an array but has a bug. What is the bug?

function nextPermutation(arr) {
  let i = arr.length - 2;
  while (i >= 0 && arr[i] > arr[i + 1]) i--;
  if (i >= 0) {
    let j = arr.length - 1;
    while (arr[j] < arr[i]) j--;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  let left = i + 1, right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  return arr;
}

medium

A. The function does not handle empty arrays

B. The swap syntax is incorrect

C. The reversal loop should start from i, not i + 1

D. The comparison operators in while loops should be >= and <= instead of > and <

Solution

1. Step 1: Check the first while loop condition

   The code uses arr[i] > arr[i + 1], but it should be arr[i] >= arr[i + 1] to correctly find the first decreasing element from right.

2. Step 2: Check the second while loop condition

   Similarly, arr[j] < arr[i] should be arr[j] <= arr[i] to find the correct element to swap.

3. Final Answer:

   The comparison operators in while loops should be >= and <= instead of > and < -> Option D

4. Quick Check:

   Use >= and <= to find correct indices [OK]

Hint: Use >= and <= in comparisons to find correct swap points [OK]

Common Mistakes:

• Using > and < instead of >= and <=
• Swapping wrong elements
• Not reversing the tail correctly

5. Given the array [5, 4, 7, 5, 3, 2], what is the next permutation after applying the next permutation algorithm?

hard

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

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

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

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

Solution

1. Step 1: Find first decreasing element from right

   Start from index 4 (value 3), arr[4] >= arr[5] (3 >= 2) true, i-- to 3 (value 5), arr[3] >= arr[4] (5 >= 3) true, i-- to 2 (value 7), arr[2] >= arr[3] (7 >= 5) true, i-- to 1 (value 4), arr[1] < arr[2] (4 < 7) stop at i=1.

2. Step 2: Find element to swap with arr[i]

   j starts at 5 (value 2), arr[5] <= arr[1] (2 <= 4) true, j-- to 4 (value 3), arr[4] <= arr[1] (3 <= 4) true, j-- to 3 (value 5), arr[3] > arr[1] (5 > 4) stop at j=3.

3. Step 3: Swap arr[i] and arr[j]

   Swap arr[1] and arr[3]: array becomes [5, 5, 7, 4, 3, 2].

4. Step 4: Reverse subarray from i+1 to end

   Reverse subarray from index 2 to 5: [7, 4, 3, 2] reversed to [2, 3, 4, 7]. Final array: [5, 5, 2, 3, 4, 7].

5. Step 5: Verify options

   [5, 5, 2, 3, 4, 7] matches final array.

6. Final Answer:

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

7. Quick Check:

   Swap and reverse tail to get next permutation [OK]

Hint: Swap first smaller from right, then reverse tail [OK]

Common Mistakes:

• Not reversing the tail after swap
• Swapping wrong elements
• Stopping at wrong index for i