Next Permutation of Array in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the next permutation function?

Given the array [1, 2, 3], what will be the state of the array after applying the next permutation algorithm once?

DSA Javascript

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

A [1, 2, 3]

B [1, 3, 2]

C [3, 2, 1]

D [2, 1, 3]

💡 Hint

Look for the first decreasing element from the right and swap it with the next bigger element.

The next permutation of [1, 2, 3] is [1, 3, 2] because we find the first element from the right that is smaller than its next element (2), then swap it with the next bigger element (3), and finally reverse the suffix.

❓ Predict Output

intermediate

What is the output after next permutation on [3, 2, 1]?

Apply the next permutation algorithm on the array [3, 2, 1]. What is the resulting array?

DSA Javascript

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

A [3, 2, 1]

B [3, 1, 2]

C [1, 2, 3]

D [2, 3, 1]

💡 Hint

If the array is in descending order, the next permutation is the ascending order.

The array [3, 2, 1] is the highest permutation. The next permutation resets it to the lowest, which is [1, 2, 3].

🔧 Debug

advanced

Why does this next permutation code fail on [1, 5, 1]?

The following code is intended to compute the next permutation but produces incorrect output for [1, 5, 1]. What is the output and why is it wrong? Code: 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--; } }

A [1, 1, 5] because the comparison operators are incorrect causing wrong pivot selection

B [1, 5, 1] because the array is unchanged due to a missing swap

C [5, 1, 1] because the suffix is not reversed properly

D [1, 5, 1] because the loop conditions cause an infinite loop

💡 Hint

Check the comparison operators in the while loops for pivot and successor selection.

The code uses > and < instead of >= and <=, causing it to pick the wrong pivot and successor, resulting in the output [1, 1, 5] instead of the correct next permutation [5, 1, 1].

🧠 Conceptual

advanced

What is the time complexity of the next permutation algorithm?

Consider the standard next permutation algorithm that finds the next lexicographically greater permutation of an array. What is its time complexity in terms of the array length n?

A O(n^2) because it uses nested loops to find the pivot and successor

B O(1) because it only swaps two elements

C O(log n) because it uses binary search to find the successor

D O(n) because it scans the array a few times linearly

💡 Hint

Think about how many times the array is scanned or reversed.

The algorithm scans the array from the end to find the pivot and successor, then reverses the suffix. Each step is linear, so overall O(n).

🚀 Application

expert

How many unique permutations are generated by repeatedly applying next permutation on [1, 1, 2]?

Starting from the array [1, 1, 2], if you repeatedly apply the next permutation algorithm until it cycles back to the original array, how many unique permutations will be generated?

A 3

B 6

C 4

D 2

💡 Hint

Count distinct permutations considering duplicates in the array.

The array [1, 1, 2] has 3 unique permutations: [1,1,2], [1,2,1], and [2,1,1]. Repeated next permutation cycles through these 3.

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