Next Permutation of Array in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the purpose of the Next Permutation algorithm?

It finds the next lexicographically greater permutation of an array of numbers. If no such permutation exists, it rearranges the array to the lowest possible order (sorted ascending).

intermediate

In the Next Permutation algorithm, what is the significance of finding the 'pivot' index?

The pivot is the first index from the right where the number is smaller than the number immediately after it. It marks where the next permutation change starts.

intermediate

Why do we reverse the suffix after the pivot in the Next Permutation algorithm?

Because the suffix is in descending order, reversing it makes it the smallest ascending order, ensuring the next permutation is just one step bigger than the current.

beginner

What happens if the entire array is in descending order when applying Next Permutation?

It means the current permutation is the highest possible. The algorithm reverses the entire array to get the lowest permutation (ascending order).

intermediate

Show the step-by-step changes for the array [1, 3, 2] when applying Next Permutation.

1. Find pivot: index 0 (1 < 3)
2. Find successor: index 2 (2 > 1)
3. Swap pivot and successor: [2, 3, 1]
4. Reverse suffix after pivot: reverse [3, 1] to [1, 3]
Result: [2, 1, 3]

What is the first step in finding the next permutation of an array?

A Swap the first and last elements

B Reverse the entire array

C Find the first number from the right that is smaller than the number after it

D Sort the array in ascending order

The algorithm starts by finding the pivot, which is the first number from the right smaller than its next number.

If no pivot is found in the array, what does the Next Permutation algorithm do?

A Reverses the entire array to ascending order

B Swaps the first two elements

C Returns the array as is

D Sorts the array in descending order

If the array is in descending order, the algorithm reverses it to get the lowest permutation.

After finding the pivot, what is the next step in the Next Permutation algorithm?

A Sort the suffix in descending order

B Reverse the entire array

C Swap the pivot with the first element

D Find the smallest number larger than the pivot from the right

We find the successor, the smallest number larger than the pivot from the right side, to swap with the pivot.

Why do we reverse the suffix after swapping the pivot and successor?

A To get the highest possible permutation

B To get the lowest possible permutation after the pivot

C To sort the entire array

D To swap the first and last elements

Reversing the suffix puts it in ascending order, ensuring the next permutation is just one step bigger.

What is the next permutation of [1, 2, 3]?

A [1, 3, 2]

B [3, 2, 1]

C [2, 1, 3]

D [1, 2, 3]

The next permutation after [1, 2, 3] is [1, 3, 2] by swapping 2 and 3 and reversing the suffix.

Explain the steps of the Next Permutation algorithm in your own words.

Think about how to get the next bigger number by changing the array minimally.

Describe what happens when the input array is sorted in descending order and Next Permutation is applied.

Consider the meaning of no next bigger permutation.

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