Next Permutation of Array in DSA Javascript - 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

What do you do after finding the pivot in the Next Permutation algorithm?

Find the smallest element to the right of the pivot that is greater than the pivot, then swap them. Finally, reverse the order of elements to the right of the pivot to get the next permutation.

advanced

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

Because the suffix was in descending order, reversing it makes it the smallest ascending order, ensuring the next permutation is the immediate next larger sequence.

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 transform it into the lowest possible order (ascending), restarting the cycle.

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

A Sort the array in ascending order

B Reverse the entire array

C Find the first element from the right that is smaller than the element after it

D Swap the first two elements

The first step is to find the pivot, which is the first element from the right that is smaller than the element immediately after it.

After finding the pivot, what do you do next in the Next Permutation algorithm?

A Swap it with the largest element to the right

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

C Reverse the entire array

D Do nothing

You swap the pivot with the smallest element to the right that is greater than the pivot to get the next larger permutation.

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

A To sort the suffix in descending order

B To find the maximum element

C To remove duplicates

D To make the suffix the smallest possible order

Reversing the suffix changes it from descending to ascending order, making the permutation the immediate next larger sequence.

What does the Next Permutation algorithm do if the array is already the highest permutation?

A Reverses the entire array to the lowest permutation

B Sorts the array in descending order

C Returns the array as is

D Throws an error

If the array is the highest permutation, the algorithm reverses it to the lowest permutation (ascending order).

Which of these arrays is the next permutation of [1, 2, 3]?

A [1, 3, 2]

B [3, 2, 1]

C [2, 1, 3]

D [1, 2, 3]

The next permutation after [1, 2, 3] is [1, 3, 2], which is the next lexicographically larger sequence.

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

Think about how to get the next bigger sequence by changing the smallest part possible.

What does the Next Permutation algorithm do when the array is in descending order?

Consider what happens when no bigger permutation exists.

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