ZeeshanAli-0704

Posted on Dec 20

Permutations & Next Permutation

#interview #computerscience #tutorial #algorithms

🔁 Permutations & Next Permutation

A Deep Problem-Solving & DSA Guide (With Theory, Intuition & Code)

1️⃣ Introduction

Permutations are one of the most fundamental concepts in problem solving and data structures (PS/DSA).
They appear in:

Recursion & backtracking
Combinatorics
Graph traversal
Interview problems (very frequently)
Optimization & state exploration

Understanding permutations deeply also makes Next Permutation trivial and intuitive.

2️⃣ What Is a Permutation?

A permutation is an ordered arrangement of elements.

Definition

If you have n distinct elements, then:

A permutation is any ordering of these n elements
Total permutations = n!

Example

For array:

[1, 2, 3]

All permutations:

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

Key Observations

Order matters ([1,2] ≠ [2,1])
Every permutation is a unique state
Exploring permutations means exploring all possible states

3️⃣ Why Permutations Matter in PS / DSA

Permutations train you in:

Recursion
Backtracking
State restoration
Depth-first search
Choice–Explore–Undo pattern

Many advanced problems are built on permutations:

N-Queens
Sudoku
Subsets & combinations
K-th permutation
Word arrangements

4️⃣ How to Generate Permutations (Core Theory)

Fundamental Idea

At each position:

Choose one available element
Fix it
Recursively permute the remaining elements
Restore state after recursion

This is backtracking.

5️⃣ Backtracking Explained (Conceptual Model)

Backtracking = DFS + Undo

General template:

Choose
Explore
Unchoose (Backtrack)

In permutations:

Choose → swap or mark element as used
Explore → recursive call
Unchoose → undo swap / unmark

6️⃣ Permutations Using Backtracking (Swap-Based)

Why Swap-Based?

No extra space
Original array reused
Clean recursion
Preferred in interviews

Algorithm (Theory)

Fix index i
Swap index i with all positions j ≥ i
Recurse for i + 1
Swap back (restore state)

JavaScript Code (Distinct Elements)

function permute(nums) {
  const result = [];

  function backtrack(index) {
    if (index === nums.length) {
      result.push([...nums]);
      return;
    }

    for (let i = index; i < nums.length; i++) {
      [nums[index], nums[i]] = [nums[i], nums[index]];
      backtrack(index + 1);
      [nums[index], nums[i]] = [nums[i], nums[index]]; // backtrack
    }
  }

  backtrack(0);
  return result;
}

Time & Space

Metric	Value
Time	O(n!)
Space	O(n) recursion

7️⃣ Handling Duplicate Elements in Permutations

Problem

Input:

[1, 1, 2]

Naive backtracking generates duplicates.

Key Insight

Duplicates arise when:

We fix the same value at the same position multiple times

Strategy to Avoid Duplicates

Sort the array
Skip repeated choices at the same recursion level

Rule (Very Important)

At the same recursion depth, do not choose the same value twice.

Duplicate-Safe Permutation Code (JS)

function permuteUnique(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  const used = new Array(nums.length).fill(false);

  function backtrack(path) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;

      // skip duplicates
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;

      used[i] = true;
      path.push(nums[i]);
      backtrack(path);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return result;
}

Example Output

[1,1,2]
→
[1,1,2]
[1,2,1]
[2,1,1]

8️⃣ What Is Next Permutation? (Deep Theory)

Definition (Precise)

Next permutation is the smallest permutation Q such that Q > P in lexicographical order.

Q must be greater than current permutation P
Among all such permutations, Q must be the smallest

Lexicographical Order (Dictionary Order)

For [1,2,3]:

Each row is one permutation.
Next permutation = next row.

9️⃣ Intuition Behind Next Permutation

Ask:

“From the right side, where can I make the smallest possible increase?”

Why from the right?

Rightmost change affects the value least
Left changes cause large jumps

🔑 Core Insight

If an array is:

descending → largest permutation
ascending → smallest permutation

🔟 Next Permutation Algorithm (Theory)

Step 1: Find Pivot

From right, find first index i where:

nums[i] < nums[i + 1]

This is the rightmost place where improvement is possible.

Step 2: Find Successor

From right, find:

smallest element > nums[i]

Important rule:

Successor must be to the right of pivot
Never from the left

Step 3: Swap Pivot & Successor

Step 4: Reverse the Suffix

Reverse everything after pivot index.

Why reverse?

Suffix is in descending order
Reversing gives smallest lexicographic order

1️⃣1️⃣ JavaScript Code (Next Permutation)

function nextPermutation(nums) {
  let i = nums.length - 2;

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

  if (i >= 0) {
    let j = nums.length - 1;

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

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

  // reverse suffix
  reverse(nums, i + 1);
}

function reverse(arr, start) {
  let l = start, r = arr.length - 1;
  while (l < r) {
    [arr[l], arr[r]] = [arr[r], arr[l]];
    l++;
    r--;
  }
}

1️⃣2️⃣ Next Permutation with Duplicates

Important Note

The same algorithm works even if duplicates exist.

Why?

Comparisons (<, >) still hold
Lexicographical order naturally handles duplicates

Example

[1,1,2]

Sequence:

[1,1,2]
[1,2,1]
[2,1,1]

Calling nextPermutation() cycles through correctly.

1️⃣3️⃣ Edge Case: Largest Permutation

Input

[3,2,1]

No pivot found
Already largest permutation
Reverse whole array

Output

[1,2,3]

1️⃣4️⃣ Permutation vs Next Permutation

Aspect	Permutation	Next Permutation
Goal	All arrangements	Next only
Technique	Backtracking	Greedy
Time	O(n!)	O(n)
Space	O(n)	O(1)
Order	Any	Lexicographical

1️⃣5️⃣ Common Interview Mistakes

❌ Forgetting to backtrack
❌ Choosing successor from left side
❌ Sorting suffix instead of reversing
❌ Not handling descending case
❌ Confusing permutation with combination