Next Permutation of Array in DSA Java - Deep Dive

Overview - Next Permutation of Array

What is it?

Next Permutation of Array is a way to rearrange numbers in an array to get the next bigger sequence in order. If the array is already the biggest possible order, it resets to the smallest order. This helps find the next arrangement without listing all permutations. It works by changing the array in place with a few simple steps.

Why it matters

Without this method, finding the next bigger arrangement would require generating all permutations, which is slow and uses a lot of memory. Next Permutation lets programs quickly jump to the next order, useful in puzzles, sorting tasks, and algorithms that explore possibilities. It makes problems with ordering efficient and practical.

Where it fits

Before learning this, you should understand arrays and basic sorting. After this, you can explore permutations, combinations, and backtracking algorithms. It fits in the journey of mastering array manipulation and algorithmic problem solving.

Mental Model

Core Idea

Next Permutation finds the next bigger number by changing the array from right to left, swapping and reversing parts to get the smallest bigger arrangement.

Think of it like...

Imagine you have a row of books sorted by height. To find the next taller arrangement, you look from right to left to find the first book that can be swapped with a taller one on its right, then reorder the books after it to be as short as possible.

Array: [1, 2, 3, 6, 5, 4]
Step 1: Find pivot (from right, first decrease): 3 at index 2
Step 2: Find successor (just bigger than pivot): 4 at index 5
Step 3: Swap pivot and successor: [1, 2, 4, 6, 5, 3]
Step 4: Reverse suffix after pivot: [1, 2, 4, 3, 5, 6]

Build-Up - 7 Steps

1

Foundation

Understanding permutations and order

Concept: What permutations are and how arrays can represent ordered sequences.

A permutation is a way to arrange items in order. For example, [1, 2, 3] can be arranged as [1, 3, 2], [2, 1, 3], etc. Arrays hold these sequences. The order matters because we want to find the next bigger arrangement, not just any arrangement.

Result

You know that permutations are different orders of the same items and that arrays can show these orders.

Understanding permutations as ordered sequences helps see why we need a method to jump to the next order without listing all.

2

Foundation

Recognizing ascending and descending parts

Concept: How to find where the array stops increasing from the right side.

Look at the array from right to left. Find the first place where a number is smaller than the number after it. This spot is called the pivot. For example, in [1, 2, 3, 6, 5, 4], starting from the right: 5 > 4 (descending), 6 > 5 (descending), 3 < 6 (pivot found at 3).

Result

You can find the pivot index where the next permutation change starts.

Finding the pivot is key because it marks where the array can be changed to get a bigger number.

3

Intermediate

Finding the successor to swap

🤔Before reading on: do you think the successor is the smallest or largest number bigger than the pivot on the right? Commit to your answer.

Concept: Identify the smallest number bigger than the pivot on the right side to swap with.

After finding the pivot, look to the right side of the array to find the smallest number bigger than the pivot. This is the successor. Swap the pivot and successor to increase the number just enough. For example, pivot=3, successor=4 in [1, 2, 3, 6, 5, 4].

Result

Swapping pivot and successor creates a bigger number but not the biggest possible.

Knowing to pick the smallest bigger number ensures the next permutation is just one step bigger, not a big jump.

4

Intermediate

Reversing the suffix after pivot

🤔Before reading on: do you think the suffix after pivot should be sorted ascending or descending after swapping? Commit to your answer.

Concept: After swapping, reverse the order of numbers after the pivot to get the smallest order there.

The part of the array after the pivot is in descending order. To get the next smallest bigger number, reverse this part to ascending order. For example, after swapping pivot and successor: [1, 2, 4, 6, 5, 3], reverse suffix after index 2: [1, 2, 4, 3, 5, 6].

Result

The array now shows the next permutation in order.

Reversing the suffix resets it to the smallest order, ensuring the next permutation is the immediate next bigger sequence.

5

Intermediate

Handling the last permutation case

Concept: What to do if the array is in descending order (last permutation).

If no pivot is found (array is fully descending), it means the array is the biggest permutation. The next permutation is the smallest one, which is the array sorted ascending. So reverse the whole array. For example, [3, 2, 1] becomes [1, 2, 3].

Result

The array resets to the smallest permutation after the last one.

Recognizing the last permutation case prevents errors and completes the cycle of permutations.

6

Advanced

In-place algorithm with O(n) time complexity

🤔Before reading on: do you think this algorithm needs extra space or can work in-place? Commit to your answer.

Concept: The next permutation algorithm works by modifying the array without extra space and in linear time.

The steps (finding pivot, successor, swapping, reversing) all happen by scanning the array from right to left once or twice. No extra arrays or memory are needed. This makes it efficient for large arrays.

Result

You can find the next permutation quickly and without extra memory.

Understanding the in-place nature and linear time helps appreciate the algorithm's efficiency and suitability for performance-critical tasks.

7

Expert

Subtle edge cases and stability considerations

🤔Before reading on: do you think the algorithm preserves the relative order of equal elements? Commit to your answer.

Concept: How the algorithm behaves with repeated numbers and stability of permutations.

When the array has duplicates, the algorithm still finds the next permutation correctly. However, it does not guarantee stability (relative order of equal elements may change). Also, careful index handling is needed to avoid off-by-one errors in pivot and successor search.

Result

The algorithm works correctly with duplicates but may reorder equal elements.

Knowing these subtle points prevents bugs in complex cases and helps when stability matters in applications.

Under the Hood

The algorithm scans the array from right to left to find the pivot where the ascending order breaks. Then it finds the successor, the smallest number bigger than the pivot on the right. Swapping these two increases the number minimally. Finally, reversing the suffix after the pivot resets it to the smallest order, ensuring the next permutation is the immediate next bigger sequence. This works because permutations can be ordered lexicographically, and these steps move to the next lex order.

Why designed this way?

This design avoids generating all permutations, which is costly. It uses the property that permutations can be ordered lexicographically and that the next permutation is the smallest bigger number. Alternatives like generating all permutations or brute force sorting are inefficient. This method is simple, fast, and uses no extra space, making it ideal for practical use.

Array: [a0, a1, ..., apivot, ..., an-1]

Step 1: Find pivot index p where a[p] < a[p+1]
  scanning from right to left

Step 2: Find successor index s > p where a[s] > a[p]

Step 3: Swap a[p] and a[s]

Step 4: Reverse array from p+1 to end

Result: Next permutation in lex order

Myth Busters - 4 Common Misconceptions

Quick: Do you think the next permutation always swaps the last two elements? Commit to yes or no.

Common Belief: The next permutation is always found by swapping the last two elements of the array.

Reality: The next permutation swaps the pivot with the successor, which may not be the last two elements. Sometimes the swap happens earlier in the array.

Why it matters: Assuming the last two elements swap can cause incorrect results and bugs, especially for longer arrays.

Quick: Do you think reversing the suffix after swapping is optional? Commit to yes or no.

Common Belief: After swapping pivot and successor, the suffix does not need to be reversed.

Reality: Reversing the suffix is essential to get the smallest order after the pivot, ensuring the next permutation is immediate and correct.

Why it matters: Skipping reversal leads to wrong permutations that are not the next in order, breaking algorithm correctness.

Quick: Do you think the algorithm works only for arrays with unique elements? Commit to yes or no.

Common Belief: Next permutation only works correctly if all elements are unique.

Reality: The algorithm works correctly even with duplicate elements, finding the next lexicographical permutation.

Why it matters: Believing it only works for unique elements limits its use and causes confusion when duplicates appear.

Quick: Do you think the algorithm requires extra memory to store permutations? Commit to yes or no.

Common Belief: Next permutation needs extra memory to store new permutations.

Reality: The algorithm works in-place, modifying the original array without extra memory.

Why it matters: Thinking extra memory is needed can lead to inefficient implementations and misunderstandings of the algorithm's efficiency.

Expert Zone

1

The pivot search must be strictly less than the next element to ensure the next bigger permutation, not just any change.

2

When duplicates exist, the successor must be chosen carefully as the rightmost element greater than the pivot to maintain lex order.

3

Reversing the suffix is more efficient than sorting because the suffix is always in descending order before reversal.

When NOT to use

Do not use next permutation when you need all permutations or when stability of equal elements is required. Instead, use backtracking for all permutations or stable sorting methods. Also, for very large arrays where only specific permutations matter, specialized algorithms may be better.

Production Patterns

Next permutation is used in combinatorial optimization, generating sequences in lex order, solving puzzles like the traveling salesman problem heuristics, and in algorithms that require stepping through permutations efficiently without full enumeration.

Connections

Lexicographic Order

Next Permutation builds on the idea of lexicographic ordering of sequences.

Understanding lex order helps grasp why the algorithm finds the immediate next bigger sequence.

Backtracking Algorithms

Next Permutation is an efficient alternative to backtracking for generating permutations one by one.

Knowing this helps choose the right approach between generating all permutations or jumping to the next.

Music Composition Patterns

Both involve arranging elements in sequences with rules to find next variations.

Recognizing pattern generation in music and permutations in arrays shows how ordering principles apply across fields.

Common Pitfalls

#1 Not finding the correct pivot index from right to left.

Wrong approach:

for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] < nums[i + 1]) {
pivot = i;
}
}

Correct approach:

int pivot = -1;
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
pivot = i;
break;
}
}

Root cause:

Misunderstanding that pivot must be found scanning from right to left to find the first decrease.

#2 Not reversing the suffix after swapping pivot and successor.

Wrong approach:

swap(nums, pivot, successor);
// missing reversal here

Correct approach:

swap(nums, pivot, successor);
reverse(nums, pivot + 1, nums.length - 1);

Root cause:

Forgetting that the suffix must be reset to ascending order to get the next permutation.

#3 Swapping pivot with any bigger element instead of the smallest bigger one.

Wrong approach:

for (int i = nums.length - 1; i > pivot; i--) {
if (nums[i] > nums[pivot]) {
swap(nums, pivot, i);
break;
}
}

Correct approach:

int successor = -1;
for (int i = nums.length - 1; i > pivot; i--) {
if (nums[i] > nums[pivot]) {
successor = i;
break;
}
}
swap(nums, pivot, successor);

Root cause:

Not choosing the right successor can cause incorrect next permutation.

Key Takeaways

Next Permutation finds the immediate next bigger arrangement of numbers by modifying the array in place.

It works by finding a pivot where the order breaks, swapping with the right successor, and reversing the suffix.

The algorithm runs in linear time and uses no extra memory, making it efficient for large arrays.

It handles duplicates correctly but does not guarantee stability of equal elements.

Understanding this algorithm helps solve many ordering and combinatorial problems efficiently.

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 larger than the current one.

3. Final Answer:

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

4. Quick Check:

   Next permutation = next bigger arrangement [OK]

Hint: Next permutation means next bigger arrangement [OK]

Common Mistakes:

• Thinking next permutation is sorting ascending
• Confusing next permutation with reversing array
• Assuming next permutation always moves smallest element front

2. Which of the following Java code snippets correctly swaps two elements arr[i] and arr[j] in an array?

easy

A. int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

B. arr[i] = arr[j]; arr[j] = arr[i];

C. int temp = arr[j]; arr[i] = arr[j]; arr[j] = temp;

D. arr[i] = arr[j]; arr[j] = arr[i] + arr[j];

Solution

1. Step 1: Understand swapping logic

   Swapping requires a temporary variable to hold one value to avoid overwriting.

2. Step 2: Check each option

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temp variable correctly to swap values.

3. Final Answer:

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option A

4. Quick Check:

   Swap needs temp variable [OK]

Hint: Use temp variable to swap two array elements [OK]

Common Mistakes:

• Overwriting one element without temp variable
• Using incorrect order causing same values
• Trying to swap without temp variable incorrectly

3. What is the output of the following Java code snippet?

int[] arr = {1, 3, 2};
nextPermutation(arr);
System.out.println(Arrays.toString(arr));

// nextPermutation method implements the standard next permutation algorithm

medium

A. [1, 2, 3]

B. [1, 3, 2]

C. [3, 1, 2]

D. [2, 1, 3]

Solution

1. Step 1: Identify pivot from right

   From right, find first pair where arr[i] < arr[i+1]. Here, arr[0]=1 < arr[1]=3, so pivot is index 0.

2. Step 2: Find element to swap with pivot

   From right, find element > arr[0]=1, which is arr[2]=2.

3. Step 3: Swap and reverse suffix

   Swap arr[0] and arr[2]: [2,3,1]. Reverse suffix after pivot index 0: reverse [3,1] to [1,3]. Final array: [2,1,3].

4. Final Answer:

   [2, 1, 3] -> Option D

5. Quick Check:

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

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

Common Mistakes:

• Not reversing suffix after swap
• Swapping with wrong element
• Confusing pivot selection

4. The following Java method attempts to implement next permutation but has a bug. What is the bug?

void nextPermutation(int[] arr) {
  int i = arr.length - 2;
  while (i >= 0 && arr[i] <= arr[i + 1]) {
    i--;
  }
  if (i >= 0) {
    int j = arr.length - 1;
    while (arr[j] <= arr[i]) {
      j--;
    }
    swap(arr, i, j);
  }
  reverse(arr, i + 1, arr.length - 1);
}

medium

A. The swap method is missing

B. The first while condition should be arr[i] >= arr[i + 1]

C. The first while loop condition is reversed; should be arr[i] > arr[i + 1]

D. The first while loop condition should be arr[i] > arr[i + 1] to find pivot correctly

Solution

1. Step 1: Analyze pivot search condition

   The pivot is found by moving left while arr[i] >= arr[i+1]. The code uses arr[i] <= arr[i+1], which is incorrect.

2. Step 2: Correct condition for pivot

   The condition should be arr[i] >= arr[i+1] to find the first decreasing element from right.

3. Final Answer:

   The first while condition should be arr[i] >= arr[i + 1] -> Option B

4. Quick Check:

   Pivot search needs arr[i] >= arr[i+1] [OK]

Hint: Pivot search uses arr[i] >= arr[i+1] condition [OK]

Common Mistakes:

• Using wrong comparison operator in pivot search
• Forgetting to reverse suffix after swap
• Missing swap or reverse method implementations

5. Given the array int[] arr = {5, 4, 7, 5, 3, 2}, what will be the array after applying the next permutation algorithm twice?

hard

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

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

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

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

Solution

1. Step 1: Find first next permutation

   Array: [5,4,7,5,3,2]
   Pivot: from right, arr[1]=4 < arr[3]=5? No, arr[1]=4 < arr[2]=7 yes, pivot=1
   Swap arr[1]=4 with next bigger from right: arr[3]=5 (since 5 > 4 and closest from right)
   Swap: [5,5,7,4,3,2]
   Reverse suffix after index 1: reverse [7,4,3,2] to [2,3,4,7]
   Result: [5,5,2,3,4,7]

2. Step 2: Find second next permutation

   Array: [5,5,2,3,4,7]
   Pivot: arr[4]=4 < arr[5]=7 yes, pivot=4
   Swap arr[4]=4 with next bigger from right: arr[5]=7
   Swap: [5,5,2,3,7,4]
   Reverse suffix after index 4: reverse [4] (single element, no change)
   Result: [5,5,2,3,7,4]

3. Final Answer:

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

4. Quick Check:

   Two next permutations applied correctly = [5,5,2,3,7,4] [OK]

Hint: Apply next permutation twice step-by-step carefully [OK]

Common Mistakes:

• Incorrect pivot selection
• Not reversing suffix after swap
• Swapping with wrong element