Next Permutation of Array in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Next Permutation on a Simple Array

What is the output of the following Java code after calling nextPermutation on the array?

DSA Java

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

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

private void reverse(int[] nums, int start) {
    int i = start, j = nums.length - 1;
    while (i < j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        i++;
        j--;
    }
}

A [1, 3, 2]

B [3, 2, 1]

C [1, 2, 3]

D [2, 1, 3]

💡 Hint

Look for the first decreasing element from the right and swap it with the next bigger element.

The next permutation algorithm finds the first element from the right that is smaller than its next element, swaps it with the next bigger element on the right, then reverses the suffix. For [1,2,3], the next permutation is [1,3,2].

❓ Predict Output

intermediate

Next Permutation Output for Descending Array

What will be the output after applying nextPermutation on this array?

DSA Java

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

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

private void reverse(int[] nums, int start) {
    int i = start, j = nums.length - 1;
    while (i < j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        i++;
        j--;
    }
}

A [3, 1, 2]

B [3, 2, 1]

C [1, 2, 3]

D [2, 3, 1]

💡 Hint

If the array is in descending order, the next permutation is the smallest permutation.

When the array is sorted in descending order, the next permutation is the array sorted in ascending order, which is the smallest permutation.

🔧 Debug

advanced

Identify the Bug in Next Permutation Implementation

What error will this code produce when running nextPermutation on the array [1, 2, 2]?

DSA Java

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

private void reverse(int[] nums, int start) {
    int i = start, j = nums.length - 1;
    while (i < j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        i++;
        j--;
    }
}

A Infinite loop

B No error, outputs [2, 1, 2]

C ArrayIndexOutOfBoundsException

D Outputs [1, 2, 2] (no change)

💡 Hint

Check the comparison operators in the while loops carefully.

The code uses '>=' and '<=' which causes it to miss the correct pivot and swap, resulting in no change to the array.

🧠 Conceptual

advanced

Understanding the Purpose of Reversing the Suffix

Why does the next permutation algorithm reverse the suffix of the array after swapping the pivot?

A To sort the suffix in descending order to get the largest permutation

B To sort the suffix in ascending order to get the next smallest permutation

C To shuffle the suffix randomly for variety

D To remove duplicates from the suffix

💡 Hint

Think about the order of elements after the pivot swap.

After swapping the pivot with the next bigger element, the suffix is still in descending order. Reversing it sorts it ascendingly, giving the next smallest permutation.

🚀 Application

expert

Number of Next Permutations to Return to Original Array

Given the array [1, 2, 3], how many times must you apply nextPermutation to return to the original array?

A 6

B 3

C 5

D 4

💡 Hint

Consider how many unique permutations exist for 3 distinct elements.

There are 3! = 6 permutations of [1, 2, 3]. Applying nextPermutation 6 times cycles through all permutations and returns to the original array.

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