Next Permutation of Array in DSA Javascript - Time & Space Complexity

Time Complexity: Next Permutation of Array

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the next permutation changes as the array size grows.

How does the number of steps grow when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds the next lexicographical permutation of the input array in place.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Three while loops that scan parts of the array.
• How many times: Each loop runs at most once from one end to the other, so up to n times each.

How Execution Grows With Input

As the array size grows, each loop can scan more elements, but each loop runs only once.

Input Size (n)	Approx. Operations
10	Up to about 30 steps (3 loops x 10 steps each)
100	Up to about 300 steps
1000	Up to about 3000 steps

Pattern observation: The total steps grow roughly in direct proportion to the array size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the next permutation grows linearly with the size of the array.

Common Mistake

[X] Wrong: "The algorithm checks all possible permutations, so it must be factorial time."

[OK] Correct: The algorithm only finds the next permutation by scanning the array a few times, not generating all permutations.

Interview Connect

Understanding this linear time approach shows you can handle array manipulation efficiently, a skill useful in many coding challenges.

Self-Check

"What if we used recursion to generate all permutations instead? How would the time complexity change?"

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