Next Permutation of Array in DSA Javascript - 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 no bigger arrangement exists, it resets to the smallest order. It helps find the next sequence in a list of all possible orders without listing them all. This is useful in problems involving ordering or combinations.

Why it matters

Without next permutation, finding the next bigger order would mean generating all possible orders and sorting them, which is slow and uses a lot of memory. This method quickly jumps to the next order, saving time and effort. It is important in tasks like generating combinations, solving puzzles, or optimizing sequences.

Where it fits

Before learning this, you should understand arrays and basic sorting. After this, you can learn about permutations, combinations, and backtracking algorithms. It fits in the journey of mastering sequence manipulation and combinatorial problems.

Mental Model

Core Idea

Next Permutation finds the next bigger number by changing the array minimally to get the next order in ascending sequence.

Think of it like...

Imagine you have a row of books arranged by height. To find the next arrangement that is just a bit taller overall, you look from right to left to find the first book that can be swapped with a taller one to its right, then reorder the rest to be the smallest possible after that swap.

Array: [1, 2, 3, 6, 5, 4]
Step 1: Find pivot (from right, first decrease): 3 at index 2
Step 2: Find successor (just bigger than pivot to right): 4 at index 5
Step 3: Swap pivot and successor: [1, 2, 4, 6, 5, 3]
Step 4: Reverse suffix after pivot index: [1, 2, 4, 3, 5, 6]

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, [1, 2, 3] can be arranged as [1, 3, 2], [2, 1, 3], etc. These can be listed in ascending order based on their numeric value or dictionary order.

Result

You understand that permutations have a natural order and can be listed from smallest to largest.

Understanding that permutations have an order helps us find the 'next' arrangement without listing all permutations.

2

Foundation

Recognizing the Need for Next Permutation

Concept: Why we need a method to find the next bigger permutation directly.

If you want the next bigger arrangement after [1, 2, 3], you could list all permutations and pick the next one. But this is slow for big arrays. Next Permutation gives a way to jump directly to the next bigger arrangement.

Result

You see the problem with listing all permutations and why a direct method is better.

Knowing the inefficiency of listing all permutations motivates learning a direct next permutation method.

3

Intermediate

Finding the Pivot Point in Array

🤔Before reading on: do you think the pivot is found by scanning from left or right? Commit to your answer.

Concept: The pivot is the first number from the right that is smaller than the number after it.

Start from the end of the array and move left until you find a number smaller than the one after it. This number is the pivot. If none found, the array is the highest permutation.

Result

You can identify the pivot index where the next permutation change starts.

Finding the pivot lets us know where the array stops increasing from the right, marking the place to change for the next bigger permutation.

4

Intermediate

Swapping Pivot with Successor

🤔Before reading on: do you think the successor is the smallest or largest number bigger than the pivot? Commit to your answer.

Concept: The successor is the smallest number to the right of the pivot that is bigger than the pivot.

From the right end, find the first number bigger than the pivot. Swap this successor with the pivot to increase the permutation just enough.

Result

You know how to increase the permutation minimally by swapping pivot and successor.

Swapping pivot with the right successor ensures the next permutation is just bigger, not too big.

5

Intermediate

Reversing the Suffix After Pivot

Concept: After swapping, reverse the part of the array after the pivot to get the smallest order there.

The part after the pivot was in descending order. Reversing it makes it ascending, which is the smallest order possible, completing the next permutation.

Result

You get the next permutation by minimal change and smallest suffix order.

Reversing the suffix ensures the next permutation is the immediate next bigger arrangement.

6

Advanced

Implementing Next Permutation in JavaScript

🤔Before reading on: do you think the algorithm modifies the array in place or creates a new one? Commit to your answer.

Concept: The algorithm modifies the array in place for efficiency.

function nextPermutation(nums) { 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]]; } let left = i + 1, right = nums.length - 1; while (left < right) { [nums[left], nums[right]] = [nums[right], nums[left]]; left++; right--; } } // Example: let arr = [1, 2, 3]; nextPermutation(arr); console.log(arr);

Result

[1, 3, 2]

Knowing the algorithm modifies the array in place helps write efficient code without extra memory.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think next permutation always increases the array value? Commit to your answer.

Concept: If the array is the highest permutation, next permutation resets it to the lowest order.

When no pivot is found (array is descending), reverse the whole array to get the smallest order. This handles the edge case and ensures the function cycles through permutations. The algorithm runs in O(n) time and O(1) space.

Result

You handle all cases correctly and understand the algorithm's efficiency.

Understanding edge cases prevents bugs and knowing the time/space complexity helps in performance-critical applications.

Under the Hood

The algorithm scans from right to left to find the first pair where the left number is smaller than the right. This marks the pivot. Then it finds the smallest number bigger than the pivot to the right (successor) and swaps them. Finally, it reverses the suffix after the pivot to get the smallest order. This works because permutations are ordered lexicographically, and these steps find the immediate next order.

Why designed this way?

This method was designed to avoid generating all permutations, which is expensive. It uses the property that permutations can be ordered lexicographically and that the suffix after the pivot is in descending order. Swapping and reversing efficiently produce the next permutation with minimal changes.

Array: [1, 2, 3, 6, 5, 4]

Find pivot:
  Start from right: 4 < 5? No
  5 < 6? No
  6 < 3? No
  3 < 6? Yes, pivot at index 2 (value 3)

Find successor:
  From right, find number > 3: 4 at index 5

Swap pivot and successor:
  [1, 2, 4, 6, 5, 3]

Reverse suffix after pivot:
  Reverse [6, 5, 3] -> [3, 5, 6]

Result:
  [1, 2, 4, 3, 5, 6]

Myth Busters - 4 Common Misconceptions

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

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

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

Why it matters: Assuming it always increases can cause bugs when cycling through permutations or when expecting strictly increasing sequences.

Quick: Is the pivot always the largest number in the array? Commit to yes or no.

Common Belief: The pivot is the largest number in the array.

Reality: The pivot is the first number from the right that is smaller than its next number, not necessarily the largest.

Why it matters: Misunderstanding pivot leads to incorrect swaps and wrong next permutations.

Quick: Does reversing the suffix after swapping always sort it? Commit to yes or no.

Common Belief: Reversing the suffix after swapping sorts it in ascending order.

Reality: The suffix is originally in descending order, so reversing it makes it ascending, which is the smallest order possible.

Why it matters: Thinking reversing sorts any suffix can cause wrong assumptions about the array state.

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

Common Belief: Next permutation must create a new array to avoid changing the original.

Reality: Next permutation is usually done in place for efficiency, modifying the original array.

Why it matters: Not knowing this can lead to inefficient code or unexpected side effects.

Expert Zone

1

The pivot search exploits the descending suffix property, which guarantees the suffix is the highest permutation of those elements.

2

Swapping the pivot with the successor ensures the next permutation is the immediate next lexicographical order, no more, no less.

3

Reversing the suffix instead of sorting it is an O(n) shortcut because the suffix is guaranteed to be in descending order.

When NOT to use

Next permutation is not suitable when you need all permutations at once or when permutations are not ordered lexicographically. For generating all permutations, backtracking or Heap's algorithm is better. Also, if you need the previous permutation, a different algorithm is required.

Production Patterns

Used in algorithms that require iterating through permutations efficiently, such as solving puzzles, optimization problems, or generating test cases. Also used in combinatorial libraries and coding interviews to demonstrate understanding of sequence manipulation.

Connections

Lexicographic Order

Next permutation builds on lexicographic ordering of sequences.

Understanding lexicographic order helps grasp why the algorithm finds the immediate next bigger arrangement.

Backtracking Algorithms

Next permutation can be used as a building block in backtracking to generate permutations efficiently.

Knowing next permutation helps optimize backtracking by jumping directly to next states without redundant work.

Music Composition

Ordering musical notes or chords can be seen as permutations; next permutation helps explore variations systematically.

Recognizing permutation patterns in music helps understand how systematic variations are created in art and science.

Common Pitfalls

#1 Not handling the case when the array is in descending order.

Wrong approach:

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

Correct approach:

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

Root cause:

Not checking if pivot exists causes errors when array is highest permutation.

#2 Swapping pivot with wrong element (not the smallest bigger successor).

Wrong approach:

let j = i + 1;
[nums[i], nums[j]] = [nums[j], nums[i]];

Correct approach:

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

Root cause:

Choosing the wrong successor breaks the minimal increase property.

#3 Not reversing the suffix after swapping.

Wrong approach:

function nextPermutation(nums) {
// find pivot and successor and swap
// but no reversal
}

Correct approach:

function nextPermutation(nums) {
// find pivot and successor and swap
// then reverse suffix
}

Root cause:

Forgetting to reorder suffix leads to wrong next permutation.

Key Takeaways

Next Permutation finds the immediate next bigger arrangement of an array by minimal changes.

It works by finding a pivot where the order breaks from the right, swapping it with the right successor, and reversing the suffix.

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

The algorithm runs in linear time and modifies the array in place for efficiency.

Understanding next permutation is key to solving many ordering and combinatorial problems efficiently.

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