Next Permutation of Array in DSA Typescript - Build from Scratch

Next Permutation of Array

📖 Scenario: You are working on a feature for a puzzle game. The game needs to find the next arrangement of numbers in a sequence to show the player the next challenge.

🎯 Goal: Build a program that finds the next permutation of a given array of numbers. If the array is the highest possible order, rearrange it to the lowest order.

📋 What You'll Learn

Create an array called nums with the exact values [1, 2, 3]

Create a variable called i to find the first decreasing element from the right

Implement the next permutation logic to rearrange nums to the next lexicographical order

Print the nums array after rearrangement

💡 Why This Matters

🌍 Real World

Next permutation logic is used in puzzle games, generating combinations, and solving problems that require ordered sequences.

💼 Career

Understanding permutations is important for software engineers working on algorithms, game development, and optimization problems.

1

Create the initial array

Create an array called nums with the exact values [1, 2, 3].

DSA Typescript

# Create an array called nums with values [1, 2, 3]
// Your code here

Hint

Use const nums = [1, 2, 3]; to create the array.

2

Find the first decreasing element from the right

Create a variable called i and set it to nums.length - 2. Then use a while loop to decrease i while i >= 0 and nums[i] >= nums[i + 1].

DSA Typescript

const nums = [1, 2, 3];
// Create variable i and find first decreasing element from right
// Your code here

Hint

Start from the second last index and move left while the current number is not less than the next.

3

Find the element to swap and reverse the suffix

If i >= 0, create a variable j set to nums.length - 1. Use a while loop to decrease j while nums[j] <= nums[i]. Then swap nums[i] and nums[j]. After that, reverse the subarray from i + 1 to the end of nums.

DSA Typescript

const nums = [1, 2, 3];
let i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
}
// If i >= 0, find j to swap and reverse suffix
// Your code here

Hint

Swap the found elements and reverse the part of the array after i to get the next permutation.

4

Print the next permutation

Print the nums array after rearrangement using console.log(nums).

DSA Typescript

const nums = [1, 2, 3];
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;
let right = nums.length - 1;
while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++;
    right--;
}
// Print the nums array
// Your code here

Hint

Use console.log(nums) to display the array.

Practice

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

easy

A. The smallest element moved to the front

B. The array sorted in ascending order

C. The array reversed

D. The next lexicographically greater arrangement of the array elements

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 immediate next arrangement that is greater than the current one.

3. Final Answer:

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

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 TypeScript function signatures correctly represents a function to compute the next permutation of an array of numbers?

easy

A. function nextPermutation(nums: number[]): void

B. function nextPermutation(nums: string): string

C. function nextPermutation(nums: number): number[]

D. function nextPermutation(nums: any): any[]

Solution

1. Step 1: Check parameter type

   The input should be an array of numbers, so nums: number[] is correct.

2. Step 2: Check return type

   The function modifies the array in place and returns nothing, so void is correct.

3. Final Answer:

   function nextPermutation(nums: number[]): void -> Option A

4. Quick Check:

   Input array, no return needed [OK]

Hint: Input array of numbers, modify in place, return void [OK]

Common Mistakes:

• Using string type instead of number array
• Returning a new array instead of modifying in place
• Using incorrect parameter types

3. What is the output array after applying the next permutation algorithm on [1, 3, 2]?

medium

A. [2, 1, 3]

B. [1, 2, 3]

C. [3, 1, 2]

D. [1, 3, 2]

Solution

1. Step 1: Find the pivot index i

   Start from i = nums.length - 2 = 1. nums[1] = 3 >= nums[2] = 2, so i-- to 0. nums[0] = 1 < nums[1] = 3, pivot i = 0.

2. Step 2: Find successor j

   From j = nums.length - 1 = 2, find rightmost j > i with nums[j] > nums[i]. j=2: 2 > 1, yes.

3. Step 3: Swap pivot and successor

   Swap nums[0] and nums[2]: [2, 3, 1].

4. Step 4: Reverse suffix after i

   Reverse indices 1 to 2: [3, 1] becomes [1, 3]. Final: [2, 1, 3].

5. Final Answer:

   [2, 1, 3] -> Option A

6. Quick Check:

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

Hint: Find pivot, swap with next bigger, reverse suffix [OK]

Common Mistakes:

• Swapping wrong elements
• Not reversing suffix after swap
• Confusing next permutation with sorting

4. Given this TypeScript code snippet, what is the error?

function nextPermutation(nums: number[]): void {
  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]];
  }
  nums.reverse();
}

medium

A. The while loops have wrong conditions

B. The entire array is reversed instead of just the suffix

C. The swap syntax is incorrect

D. The function returns a value but should be void

Solution

1. Step 1: Analyze reversal step

   The code reverses the entire array with nums.reverse() instead of just the suffix after index i+1.

2. Step 2: Understand correct reversal

   Only the part of the array after the pivot index should be reversed to get the next permutation.

3. Final Answer:

   The entire array is reversed instead of just the suffix -> Option B

4. Quick Check:

   Reverse suffix, not whole array [OK]

Hint: Reverse only suffix after pivot, not whole array [OK]

Common Mistakes:

• Reversing entire array instead of suffix
• Incorrect swap syntax
• Wrong loop conditions causing errors

5. You have an array [5, 4, 3, 2, 1]. After applying the next permutation algorithm, what will be the resulting array?

hard

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

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

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

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

Solution

1. Step 1: Check if array is highest permutation

   The array is in descending order, which is the highest permutation.

2. Step 2: Apply next permutation rule for highest permutation

   If no next bigger permutation exists, the array is reversed to the lowest permutation.

3. Final Answer:

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

4. Quick Check:

   Descending array next permutation is ascending [OK]

Hint: Descending array next permutation is ascending order [OK]

Common Mistakes:

• Returning same array instead of reversed
• Trying to swap elements incorrectly
• Confusing next permutation with partial sorting