Next Permutation of Array in DSA Java

Mental Model

Find the next bigger arrangement of numbers by changing the smallest possible part of the array.

Analogy: Imagine you have a row of books sorted in a certain order. To get the next order, you look from right to left to find the first book that can be swapped with a bigger one to its right, then rearrange the books after it to the smallest order.

Array: [1] -> [2] -> [3] -> [4] -> [5]
Indexes:  0      1      2      3      4

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Find the next permutation which is just bigger than [1, 2, 3]

Step 1: Find the first index from right where array[i] < array[i+1], here i=1 (2 < 3)

[1] -> [2] -> [3]

Why: We need to find the place where we can make the array bigger by swapping

Step 2: Find the first index from right where array[j] > array[i], here j=2 (3 > 2)

[1] -> [2] -> [3]

Why: We want to swap with the smallest bigger number on the right

Step 3: Swap array[i] and array[j], swap 2 and 3

[1] -> [3] -> [2]

Why: Swapping makes the array bigger but still close to original

Step 4: Reverse the subarray after i (index 2 to end), here only one element so no change

[1] -> [3] -> [2]

Why: Reversing makes the tail part smallest to get the next permutation

Result:

[1] -> [3] -> [2]

Annotated Code

DSA Java

import java.util.Arrays;

public class NextPermutation {
    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        // Find first decreasing element from right
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            // Find element just bigger than nums[i]
            while (nums[j] <= nums[i]) {
                j--;
            }
            // Swap nums[i] and nums[j]
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        // Reverse the subarray after i
        reverse(nums, i + 1, nums.length - 1);
    }

    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }
}

int i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; }

Find first index from right where nums[i] < nums[i+1]

if (i >= 0) { int j = nums.length - 1; while (nums[j] <= nums[i]) { j--; }

Find first index from right where nums[j] > nums[i]

int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;

Swap nums[i] and nums[j] to increase permutation minimally

reverse(nums, i + 1, nums.length - 1);

Reverse subarray after i to get smallest order

Output

[1, 3, 2]

Complexity Analysis

Time: O(n) because we scan the array a few times but only once each from right to left

Space: O(1) because we modify the array in place without extra space

vs Alternative: Naive approach would generate all permutations and find next, which is O(n!) and very slow

Edge Cases

Array is in descending order like [3, 2, 1]

The function reverses the whole array to the smallest permutation [1, 2, 3]

DSA Java

while (i >= 0 && nums[i] >= nums[i + 1]) { i--; }

Array has only one element like [1]

No change since no next permutation possible

DSA Java

while (i >= 0 && nums[i] >= nums[i + 1]) { i--; }

Array with repeated elements like [1, 5, 1]

Next permutation is correctly found as [5, 1, 1]

DSA Java

while (nums[j] <= nums[i]) { j--; }

When to Use This Pattern

When you need to find the next bigger arrangement of numbers or characters in order, use the next permutation pattern because it efficiently finds the closest bigger sequence.

Common Mistakes

Mistake: Not reversing the subarray after swapping, leading to incorrect next permutation
Fix: Always reverse the subarray after the swapped index to get the smallest tail

Mistake: Swapping with the wrong element that is not just bigger than nums[i]
Fix: Find the first element from right that is strictly greater than nums[i] before swapping

Summary

Finds the next lexicographically bigger permutation of the array in place.

Use when you want to generate permutations in order or find the next arrangement quickly.

The key is to find the first decreasing element from right, swap with just bigger element, then reverse the tail.

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