Next Permutation of Array in DSA Javascript

Mental Model

Find the next bigger arrangement of numbers by changing the smallest part of the array that can be increased.

Analogy: Imagine you have a lock with numbers and you want to find the next combination that is just a little bigger than the current one, like turning the last dial to the next number possible.

Array: [1, 2, 3, 4]
Indexes:  0  1  2  3
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 that is just bigger than [1, 2, 3], which is [1, 3, 2]

Step 1: Find the first index from the right where the number is smaller than the number after it (pivot).

[1, 2, 3]
Indexes: 0  1  2
Pivot found at index 1 because 2 < 3

Why: We need to find where we can increase the number to get a bigger permutation.

Step 2: Find the first number from the right that is bigger than the pivot number (2).

[1, 2, 3]
Indexes: 0  1  2
Number bigger than pivot (2) found at index 2 (3)

Why: We want to swap pivot with the next bigger number to get the next permutation.

Step 3: Swap the pivot (2) with the number found (3).

[1, 3, 2]
Indexes: 0  1  2
After swapping pivot and next bigger number

Why: Swapping increases the permutation just enough.

Step 4: Reverse the part of the array after the pivot index to get the smallest order.

[1, 3, 2]
Indexes: 0  1  2
Reversing after pivot index 1 (only index 2 here)

Why: Reversing ensures the suffix is the smallest possible to get the next permutation.

Result:

[1, 3, 2]

Annotated Code

DSA Javascript

class NextPermutation {
  static nextPermutation(nums) {
    let i = nums.length - 2;
    // Find pivot: first number from right smaller than next
    while (i >= 0 && nums[i] >= nums[i + 1]) {
      i--;
    }
    if (i >= 0) {
      let j = nums.length - 1;
      // Find number bigger than pivot
      while (nums[j] <= nums[i]) {
        j--;
      }
      // Swap pivot and this number
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    // Reverse suffix
    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 pivot index where nums[i] < nums[i+1]

while (nums[j] <= nums[i]) { j--; }

Find number just bigger than pivot to swap

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

Swap pivot with next bigger number

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

Reverse suffix after pivot 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 each.

Space: O(1) because we modify the array in place without extra space.

vs Alternative: Naive approach would generate all permutations and find the next one, which is very slow (O(n!)). This method is efficient and direct.

Edge Cases

Array is in descending order like [3, 2, 1]

The algorithm reverses the whole array to the smallest permutation [1, 2, 3].

DSA Javascript

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

Array has only one element like [1]

No change happens because there is no next permutation.

DSA Javascript

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

Array with repeated elements like [1, 5, 5]

Algorithm correctly finds next permutation [5, 1, 5].

DSA Javascript

while (nums[j] <= nums[i]) { j--; }

When to Use This Pattern

When you need to find the next bigger arrangement of numbers in order, use the next permutation pattern because it efficiently finds the next order without generating all permutations.

Common Mistakes

Mistake: Not reversing the suffix after swapping pivot and next bigger number.
Fix: Always reverse the part of the array after the pivot index to get the smallest suffix.

Mistake: Swapping pivot with a number not just bigger than it, causing wrong next permutation.
Fix: Find the rightmost number bigger than pivot to swap.

Mistake: Not handling the case when the array is fully descending (no pivot found).
Fix: If no pivot found, reverse the whole array to get the smallest permutation.

Summary

Finds the next lexicographically bigger permutation of an array of numbers.

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

The key is to find the pivot from right, swap with next bigger number, then reverse the suffix.

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