Next Permutation-Leetcode 31 Solution

The Next Permutation problem (LeetCode #31) involves rearranging a sequence of numbers into its next lexicographical permutation. If the sequence is already the largest possible permutation, it should be rearranged into the smallest (sorted in ascending order). Below is a detailed breakdown of the approaches to solve this problem, from naive to optimal, with Java implementations.

Problem Statement for Next Permutation

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Naive Approach to Next Permutation

The naive approach involves generating all permutations of the array, sorting them, and finding the next lexicographical permutation. While this approach is computationally expensive (O(n!)O(n!)O(n!)), it is useful for educational purposes to understand the problem.

Steps:

1. Generate all permutations of the array.
2. Sort the permutations.
3. Find the current permutation in the sorted list and return the next one (or the first permutation if the current one is the largest).

Java Implementation:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class NaiveNextPermutation {
    public void nextPermutation(int[] nums) {
        // Step 1: Generate all permutations
        List<List<Integer>> permutations = new ArrayList<>();
        permute(nums, 0, permutations);

        // Step 2: Sort the permutations
        List<Integer> current = new ArrayList<>();
        for (int num : nums) {
            current.add(num);
        }
        Collections.sort(permutations, (a, b) -> {
            for (int i = 0; i < a.size(); i++) {
                if (!a.get(i).equals(b.get(i))) {
                    return a.get(i) - b.get(i);
                }
            }
            return 0;
        });

        // Step 3: Find the next permutation
        int index = 0;
        for (int i = 0; i < permutations.size(); i++) {
            if (permutations.get(i).equals(current)) {
                index = i;
                break;
            }
        }

        List<Integer> nextPermutation = permutations.get((index + 1) % permutations.size());

        // Update the input array
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nextPermutation.get(i);
        }
    }

    private void permute(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(permutation);
            return;
        }

        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1, result);
            swap(nums, start, i);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

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

Explanation:

1. Generate Permutations: Using recursion, the permute function generates all permutations of the array.
2. Sort Permutations: Sorting ensures that the permutations are arranged in lexicographical order.
3. Find Next Permutation: Locate the current permutation in the sorted list and return the next one.

Drawbacks:

• Time Complexity: O(n!) for generating and sorting permutations.
• Space Complexity: O(\n) for storing all permutations.

Use this approach for learning purposes, as it is impractical for larger arrays. This approach is inefficient with a time complexity of O(n!) due to the factorial number of permutations.

Optimal Solution: Lexicographic Algorithm

The optimal solution uses an in-place modification with O(n)O(n)O(n) time complexity.

Steps:

1. Find the first decreasing element from the end:
   Traverse the array from right to left to find the first index i where nums[i] > nums[i-1]. This indicates the point where the order can be increased.
2. Find the element to swap:
   From the end of the array, find the smallest element greater than nums[i-1] and swap them.
3. Reverse the suffix:
   Reverse the subarray starting from index i to transform it into the smallest lexicographical order.

Implementation:

public class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        
        // Step 1: Find the first decreasing element
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        if (i >= 0) { // If the array is not in descending order
            // Step 2: Find the next larger element to swap
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        
        // Step 3: Reverse the suffix
        reverse(nums, i + 1, n - 1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

Explanation of Code

1. Finding i: The loop ensures we find the pivot where the order breaks.
2. Finding j: This identifies the smallest number that can replace nums[i] to ensure the sequence grows minimally.
3. Swapping and Reversing: After swapping, reversing the suffix ensures the minimal increase in order.

Complexity Analysis

• Time Complexity: O(n)
  Finding i and j and reversing the suffix all run in linear time.
• Space Complexity: O(1)
  In-place modifications ensure constant space usage.