Next Permutation of Array in DSA Java - Build from Scratch

Next Permutation of Array

📖 Scenario: You are working on a program that helps find the next arrangement of numbers in a list, like finding the next page in a book of number orders.

🎯 Goal: Build a Java program that finds the next permutation of a given array of integers. If the array is the highest possible order, rearrange it to the lowest order.

📋 What You'll Learn

Create an integer array called nums with the exact values {1, 2, 3}.

Create an integer variable called i initialized to nums.length - 2.

Use a while loop to find the first index i from the right where nums[i] < nums[i + 1].

If such i is found, create an integer variable j initialized to nums.length - 1.

Use a while loop to find the first index j from the right where nums[j] > nums[i].

Swap nums[i] and nums[j].

Reverse the sub-array from i + 1 to the end of the array.

Print the final state of the nums array as a sequence of numbers separated by spaces.

💡 Why This Matters

🌍 Real World

Finding the next permutation is useful in generating combinations, solving puzzles, and optimizing sequences in games or scheduling.

💼 Career

Understanding permutations helps in algorithm design, coding interviews, and solving complex problems in software development.

1

Create the initial array

Create an integer array called nums with the exact values {1, 2, 3}.

DSA Java

# Create the integer array nums with values {1, 2, 3}
// Your code here

Hint

Use int[] nums = {1, 2, 3}; to create the array.

2

Find the first decreasing element from the right

Create an integer variable called i and set it to nums.length - 2. Then use a while loop to decrease i while i >= 0 and nums[i] >= nums[i + 1].

DSA Java

public class NextPermutation {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int i = nums.length - 2;
        // Use a while loop to find the first decreasing element from the right
        // Your code here
    }
}

Hint

Start from the second last index and move left while the current number is not less than the next.

3

Find the element to swap and swap

If i >= 0, create an integer variable j set to nums.length - 1. Use a while loop to decrease j while nums[j] <= nums[i]. Then swap nums[i] and nums[j]. Finally, reverse the sub-array from i + 1 to the end of the array.

DSA Java

public class NextPermutation {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // If i >= 0, find j and swap nums[i] and nums[j]
        // Then reverse the sub-array from i+1 to end
        // Your code here
    }
}

Hint

Swap the found elements and reverse the tail part of the array to get the next permutation.

4

Print the next permutation

Use a for loop to print all elements of the nums array separated by spaces on a single line.

DSA Java

public class NextPermutation {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        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;
        }
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
        // Print the nums array elements separated by spaces
        // Your code here
    }
}

Hint

Use a for loop and System.out.print to print each number with spaces.

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