Next Permutation of Array in DSA Java - Execution Trace

Concept Flow - Next Permutation of Array

Start from end

↓

Find first i where arr[i

Yes↓

Find j from end where arr[j

↓

Swap arr[i

↓

Reverse subarray from i+1 to end

↓

Done

↓

Reverse whole array

↓

Done

Find the first decreasing element from the right, swap it with a just larger element on the right, then reverse the tail to get the next permutation.

Execution Sample

DSA Java

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

This code finds the next lexicographical permutation of the array.

Execution Table

Step	Operation	i	j	Array State	Pointer Changes	Visual State
1	Initialize i at length-2	4	-	[1, 2, 3, 6, 5, 4]	i=4	1 -> 2 -> 3 -> 6 -> 5 -> 4
2	Check arr[i] >= arr[i+1]	3	-	5 >= 4? True	i=4 -> 3	1 -> 2 -> 3 -> 6 -> 5 -> 4
3	Check arr[i] >= arr[i+1]	2	-	3 >= 6? False	Stop decrement i	1 -> 2 -> 3 -> 6 -> 5 -> 4
4	Initialize j at end	2	5	[1, 2, 3, 6, 5, 4]	j=5	1 -> 2 -> 3 -> 6 -> 5 -> 4
5	Find j where arr[j] > arr[i]	2	5	4 > 3? True	Stop decrement j	1 -> 2 -> 3 -> 6 -> 5 -> 4
6	Swap arr[i] and arr[j]	2	5	Swap arr[2]=3 and arr[5]=4	Array updated	1 -> 2 -> 4 -> 6 -> 5 -> 3
7	Reverse subarray from i+1 to end	2	5	Reverse arr[3..5]: [6,5,3]	Array updated	1 -> 2 -> 4 -> 3 -> 5 -> 6
8	Done	-	-	Final array: [1, 2, 4, 3, 5, 6]	-	1 -> 2 -> 4 -> 3 -> 5 -> 6

💡 i found at index 2, next permutation generated by swapping and reversing tail

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	After Step 7	Final
i	4	3	2	2	2	2	-
j	-	-	-	5	5	5	-
Array	[1,2,3,6,5,4]	[1,2,3,6,5,4]	[1,2,3,6,5,4]	[1,2,3,6,5,4]	[1,2,4,6,5,3]	[1,2,4,3,5,6]	[1,2,4,3,5,6]

Key Moments - 3 Insights

Why do we start looking for i from the second last element, not the last?

Because we compare arr[i] with arr[i+1], so i must be less than length-1 to avoid out-of-bound errors. See execution_table steps 1-3 where i starts at length-2.

What if no i is found where arr[i] < arr[i+1]?

It means the array is in descending order, the highest permutation. We reverse the whole array to get the lowest permutation. This is not shown in this example but is part of the concept flow.

Why do we reverse the subarray after swapping?

Because the subarray after i was in descending order, reversing it makes it ascending, giving the next smallest permutation after the swap. See execution_table steps 7-8.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of i?

A 3

B 2

C 1

D 5

💡 Hint

Check the 'i' column in execution_table row with Step '3'

At which step does the array first change?

A Step 7

B Step 5

C Step 6

D Step 8

💡 Hint

Look for the first 'Swap' operation in the 'Operation' column and check the 'Array State'

If the array was already in descending order, what would happen?

A We reverse the entire array

B We swap the first two elements

C We do nothing

D We reverse only the last two elements

💡 Hint

Refer to the concept_flow where if no i is found, the whole array is reversed

Concept Snapshot

Next Permutation Algorithm:
1. Find the first index i from right where arr[i] < arr[i+1]
2. If found, find j from right where arr[j] > arr[i]
3. Swap arr[i] and arr[j]
4. Reverse the subarray from i+1 to end
If no i found, reverse entire array
This gives the next lexicographically greater permutation.

Full Transcript

The next permutation algorithm finds the next lexicographically greater arrangement of numbers. We start from the right end and find the first element that is smaller than the one after it. This index is called i. If such an i exists, we find another index j from the right where the element is greater than arr[i]. We swap arr[i] and arr[j]. Then we reverse the subarray after i to get the smallest order. If no such i exists, the array is in descending order, so we reverse the whole array to get the smallest permutation. This process ensures we get the next permutation in order.

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