What is the time complexity of Next Permutation?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Next Permutation?

This problem uses Array, Two Pointers. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Next Permutation?

Insight 1: The core idea is to find a decreasing sequence from the right. If the entire array is decreasing, it is the largest permutation, and we should reverse it to obtain the smallest permutation. Insight 2: To find the next greater permutation, we need to find the smallest element to the right of a pivot that is greater than the pivot, and then swap them.

Which companies ask LeetCode 31. Next Permutation in interviews?

This problem is frequently asked at Accenture, Adobe, Amazon, Apple, Arcesium and 26 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Next Permutation - LeetCode 31 Solution

Next Permutation - Complete Solution Guide

Next Permutation is LeetCode problem 31, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 permutati

Detailed Explanation

The problem asks us to find the next lexicographically greater permutation of a given array of integers. If no such greater permutation exists (i.e., the array is already in descending order), we need to rearrange the array into its smallest possible order (ascending order). The solution must be performed in-place, meaning we cannot use additional memory that scales with the size of the input array. In simpler terms, we need to rearrange the numbers in the array to form the next bigger number possible, treating the array as a single large number, and if no bigger number exists, sort it in ascending order.

Solution Approach

The solution involves four main steps. First, we scan the array from right to left to find the first element `nums[i]` that is smaller than its immediate right neighbor `nums[i+1]`. This element `nums[i]` is our 'pivot'. If no such element is found, it means the array is in descending order, and we reverse the entire array. Second, if a pivot is found, we search the subarray to the right of `nums[i]` for the smallest element that is greater than `nums[i]`. Third, we swap the pivot with this element. Finally, we reverse the subarray to the right of the pivot to create the smallest possible arrangement for the remaining elements.

Step-by-Step Algorithm

Step 1: Start from the second last element (index n-2) and move towards the beginning of the array to find the first element nums[i] that is smaller than its next element nums[i+1]. If no such element is found (i becomes -1), the array is in descending order, and go to step 4.
Step 2: If i >= 0 (a pivot is found), start from the end of the array and move towards i+1 to find the smallest element nums[j] that is greater than nums[i].
Step 3: Swap nums[i] and nums[j].
Step 4: Reverse the subarray from index i+1 to the end of the array (index n-1). If i was -1, this step reverses the entire array.

Key Insights

Insight 1: The core idea is to find a decreasing sequence from the right. If the entire array is decreasing, it is the largest permutation, and we should reverse it to obtain the smallest permutation.
Insight 2: To find the next greater permutation, we need to find the smallest element to the right of a pivot that is greater than the pivot, and then swap them.
Insight 3: Reversing the sequence to the right of the pivot ensures that the remaining part of the number is as small as possible, resulting in the next lexicographical permutation.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers.

Companies

Asked at: Accenture, Adobe, Amazon, Apple, Arcesium, Bloomberg, ByteDance, DE Shaw, DoorDash, Goldman Sachs, HashedIn, IBM, Infosys, Intuit, J.P. Morgan, LinkedIn, Meta, Microsoft, Mitsogo, Nike, Paytm, Rubrik, ServiceNow, TikTok, Uber, Upstart, VMware, Yahoo, Zepto, Zoho, tcs.

Next Permutation | LeetCode 31

Medium

Array Two Pointers

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;

        // Step 1: Find the first element from the right that is smaller than its next element.
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // If such an element is found (the array is not in descending order)
        if (i >= 0) {
            // Step 2: Find the smallest element in the suffix (to the right of i)
            // that is larger than nums[i].
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            
            // Step 3: Swap these two elements.
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        // Step 4: Reverse the suffix starting from i + 1.
        // If no such element i was found (i = -1), this will reverse the whole array.
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 31: Next Permutation - Detailed explanation and solution approaches.

Topics

Array Two Pointers

Companies

AccentureAdobeAmazonAppleArcesiumBloombergByteDanceDE Shaw

Stats

Difficulty:Medium

Languages:4

Companies:31

Problem #:31

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Step 1: Start from the second last element (index n-2) and move towards the beginning of the array to find the first element nums[i] that is smaller than its next element nums[i+1]. If no such element is found (i becomes -1), the array is in descending order, and go to step 4.
2
Step 2: If i >= 0 (a pivot is found), start from the end of the array and move towards i+1 to find the smallest element nums[j] that is greater than nums[i].
3
Step 3: Swap nums[i] and nums[j].
4
Step 4: Reverse the subarray from index i+1 to the end of the array (index n-1). If i was -1, this step reverses the entire array.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The algorithm iterates through the array at most three times: once to find the pivot, once to find the element to swap with the pivot, and once to reverse the suffix. Each of these iterations takes O(n) time. The swapping and reversing operations are done in place. Therefore, the overall time complexity is O(n). The algorithm uses only a few extra variables, so the space complexity is O(1), which means constant extra space.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using Built-in Permutation Functions (for understanding)

Generate all permutations of the array and then find the one that comes next lexicographically. This is mainly for understanding the concept. In practice, it's inefficient.

Time: O(n! * n) - generating permutations is factorial and comparing them takes O(n)Space: O(n! * n) - to store all permutations

Trade-offs: This approach is much less efficient than the in-place solution, both in terms of time and space. It's primarily useful for educational purposes to understand the concept of permutations, but impractical for large arrays.

✨

Key Insights

1Insight 1: The core idea is to find a decreasing sequence from the right. If the entire array is decreasing, it is the largest permutation, and we should reverse it to obtain the smallest permutation.
2Insight 2: To find the next greater permutation, we need to find the smallest element to the right of a pivot that is greater than the pivot, and then swap them.
3Insight 3: Reversing the sequence to the right of the pivot ensures that the remaining part of the number is as small as possible, resulting in the next lexicographical permutation.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Edge Cases

Edge case 1: Input array is already in descending order (e.g., [3, 2, 1]). The algorithm correctly identifies this case by not finding a pivot (i becomes -1) and then reverses the entire array, resulting in the smallest permutation [1, 2, 3].
Edge case 2: Input array is in ascending order (e.g., [1, 2, 3]). The algorithm finds the pivot at index 1 (value 2). It then finds the smallest element to the right that's greater than 2, which is 3. It swaps 2 and 3, resulting in [1, 3, 2]. Then it reverses the suffix [2], which is trivially [2], keeping it [1,3,2].
Edge case 3: Input array with duplicate elements (e.g., [1, 1, 5]). The algorithm handles duplicate elements correctly as the comparison operators used (>= and <=) will find the correct pivot and swap element.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where the input array is already in descending order. Failing to reverse the entire array in this case will result in an incorrect answer.

✗Common mistake 2: Incorrectly identifying the pivot or the element to swap with the pivot. It's crucial to find the *smallest* element to the right of the pivot that is *greater* than the pivot.

✗Common mistake 3: Forgetting to reverse the suffix after the swap. This ensures that the remaining portion of the array is in ascending order, producing the next lexicographical permutation.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Task scheduling. Finding the next optimal arrangement of tasks in a schedule, where the tasks have priorities and dependencies.

🏦Real-world scenario 2: Route optimization. Finding the next best route for a delivery truck or salesperson, considering factors such as distance, traffic, and customer locations.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 2, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Next Permutation"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?