Next Permutation - Java Solution

1. Introduction

This blog post is dedicated to solving the "Next Permutation" problem, a fascinating challenge that involves rearranging numbers to form the next lexicographically greater permutation. It's a common problem that tests one's understanding of algorithms related to permutations and array manipulation.

Problem

Given an array of integers nums, the objective is to rearrange the array to its next permutation in lexicographical order. If no such permutation exists (i.e., the array is in descending order), the array should be rearranged to its lowest possible order (ascending order). The solution must be implemented in-place with only constant extra memory.

2. Solution Steps

1. Find the first decreasing element from the end of the array. Let's call it pivot.

2. If the pivot is not found, it means the array is in descending order. Reverse the entire array to make it ascending and return.

3. Find the smallest element greater than the pivot from the right side of pivot and swap them.

4. Reverse the sub-array to the right of the original pivot position.

5. The resulting array is the next permutation.

3. Code Program

public class NextPermutation {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        nextPermutation(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    // Function to transform nums into the next permutation
    public static void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;

        // Step 1: Find the pivot
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // Step 2: If pivot is not found, reverse the whole array
        if (i < 0) {
            reverse(nums, 0, nums.length - 1);
            return;
        }

        // Step 3: Swap the pivot with the next greater element
        int j = nums.length - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        swap(nums, i, j);

        // Step 4: Reverse the sub-array to the right of the pivot
        reverse(nums, i + 1, nums.length - 1);
    }

    // Helper method to swap elements in the array
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // Helper method to reverse a sub-array
    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start++, end--);
        }
    }
}

Output:

1 3 2

Explanation:

1. nextPermutation: This function modifies nums to its next permutation.

2. It starts by finding the first decreasing element (pivot) from the end.

3. If no such pivot is found, the array is reversed to get the lowest permutation.

4. If a pivot is found, it swaps pivot with the smallest element greater than pivot found to its right.

5. It then reverses the sub-array to the right of the original pivot position.

6. This rearrangement results in the next lexicographical permutation.

7. The function uses helper methods swap and reverse for array manipulation, ensuring in-place transformation with O(1) extra memory.

8. The algorithm efficiently finds the next permutation with O(n) time complexity, where n is the length of the input array.