NEXT PERMUTATION

 

Next Permutation 

Introduction

A permutation is an arrangement of elements in a particular order. The next permutation refers to the next greater arrangement of numbers in lexicographical (dictionary) order.

If no such permutation exists ( the array is in descending order), we rearrange it into the smallest possible order (ascending).

Problem Statement

Given an array nums[], find the next lexicographically greater permutation of its elements.

  • Modify the array in-place

  • Use constant extra space

Example

Input:

nums = [1, 2, 3]

Output:

[1, 3, 2]

Solution Code

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 1;
        while (i > 0 && nums[i-1] >= nums[i]) {
            i--;
        }

        if (i == 0) {
            reverse(nums, 0, nums.length-1);
            return;
        }

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

        swap(nums, i-1, j);
        reverse(nums, i, nums.length-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) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Approach Used: Lexicographical Permutation Logic

Idea

We find the next greater permutation by modifying the array minimally.

How It Works

Step 1: Find the “breaking point”

Traverse from right to left and find the first index i such that:

nums[i-1] < nums[i]

 This is where the order can be increased

Step 2: If no such point exists

  • The array is in descending order

  • Reverse the entire array to get the smallest permutation

Step 3: Find the next greater element

From the right side, find the first element greater than nums[i-1] and swap them

Step 4: Reverse the remaining part

Reverse the subarray from index i to end

This ensures the next smallest arrangement after the swap

Why This Approach Was Chosen

  • Finds the next permutation in O(n) time

  • Uses constant extra space

  • Avoids generating all permutations (which is very expensive)

Alternative Approaches

  • Generate all permutations and sort them
     Time Complexity: O(n!)
     Not practical

Why not used?
Too inefficient for large inputs

Time and Space Complexity

  • Time Complexity: O(n)

  • Space Complexity: O(1)

Important Observations

  • The suffix after index i is always in descending order

  • Reversing it makes it the smallest possible order

  • This ensures we get the next permutation, not just any greater one

Example Walkthrough

Input:

[2, 3, 1]

Steps:

  • Find breaking point = 2 < 3

  • Swap 2 and 3= [3, 2, 1]

  • Reverse suffix = [3, 1, 2]

Output:

[3, 1, 2]

Conclusion

The next permutation problem is a great example of applying logical thinking to achieve an optimal solution. By identifying the correct position to modify and rearranging only a part of the array, we efficiently compute the next lexicographical permutation in linear time.

Comments

Post a Comment

Popular posts from this blog

THE DELIVERY MAN

  The Delivery Man – Python List Operations  Introduction Lists in Python are used to store multiple items in a single variable. They are flexible, allowing us to add, remove, update, and manipulate elements easily. In this task, different list operations are performed to simulate a delivery man's workflow. 1. Creating a list and accessing an item items = ["Notebook", "Pencil", "Eraser", "Ruler", "Marker"] print(items[2]) Approach: Indexing Why: Lists use zero-based indexing, so the third item is accessed using index 2. 2. Adding a new item items.append("Glue Stick") print(items) Approach: append() method Why: It adds an item at the end of the list, which is ideal for adding new deliveries. 3. Inserting an item items.insert(2, "Highlighter") print(items) Approach: insert() method Why: Used when we need to add an item at a specific position instead of the end. 4. Removing an item items.remove("Ruler...
Read more

EC2 LAUNCHING

  EC2 Step 1: Launch EC2 Instance Go to: AWS Console --> EC2 --> Launch Instance Configure: Name : my-web-server AMI : Amazon Linux 2 (easy for beginners) Instance Type : t2.micro (free tier) Step 2: Key Pair Create or select a key pair. Step 3: Network Settings  Allow these: SSH (port 22) --> for login  HTTP (port 80) --> for web access Step 4: Launch Instance Click Launch Instance Step 5: Connect to Instance Use: EC2 --> Connect --> EC2 Instance Connect (easiest) OR via terminal: with this command. for this you have to download the pem files while selecting the key pair.  ssh -i your-key.pem ec2-user@<public-ip> Step 6: Install Web Server For Amazon Linux: sudo yum update -y sudo yum install httpd -y Step 7: Start Web Server sudo systemctl start httpd sudo systemctl enable httpd Step 8: Add a Web Page echo "Hello from EC2" | sudo tee /var/www/html/index.html Step 9: Get Public IP Go to EC2 d...
Read more

SORT A LINKED LIST USING MERGE SORT

  Sort a Linked List using Merge Sort Introduction Sorting a linked list efficiently is a common problem in data structures. Unlike arrays, linked lists do not allow direct access to elements, so algorithms like quicksort are not ideal. Merge Sort is the best choice for linked lists because: It does not require random access It works efficiently with node-based structures Problem Statement Given the head of a linked list: Sort the list in ascending order Return the sorted linked list Example Input: 10 -> 30 -> 20 -> 40 -> 60 -> 50 Output: 10 -> 20 -> 30 -> 40 -> 50 -> 60 Solution Code class Solution: def mergeSort(self, head): if not head or not head.next: return head mid = self.getMiddle(head) next_to_mid = mid.next mid.next = None left = self.mergeSort(head) right = self.mergeSort(next_to_mid) return self.merge(left, right) def getMiddle(self,...
Read more