Skip to main content

Leetcode 31: Next Permutation

 

1. Problem Statement (Simple Explanation):


You’re given an array of integers nums representing a permutation.

You must rearrange nums in-place to form the next lexicographically greater permutation.

  • If such a permutation exists: transform nums into it.

  • If not (i.e., nums is the highest permutation), rearrange nums into the lowest possible order (sorted ascending).

Constraints:

  • In-place (only constant extra memory).

  • 1 <= nums.length <= 100

  • 0 <= nums[i] <= 100


2. Examples:


Example 1:

Input: nums = [1,2,3]

Permutations in order:

[1,2,3]

[1,3,2]  <-- next

[2,1,3]

[2,3,1]

[3,1,2]

[3,2,1]

Output: [1,3,2]


Example 2:

Input: nums = [3,2,1]

This is the largest permutation. The next permutation wraps to the smallest:

Output: [1,2,3]


Example 3:

Input: nums = [1,1,5]

Next permutations:

[1,1,5]

[1,5,1]  <-- next

[5,1,1]

Output: [1,5,1]


3. Intuition – Classic Next Permutation Algorithm:


We want the next lexicographically larger arrangement. Think of the array as a number; we want the smallest number larger than the current using the same digits.

Algorithm idea (standard):

  1. Scan from right to left to find the first index i where:

nums[i] < nums[i+1]

This is the pivot where the descending order breaks.

  1. If no such i exists (array is fully non-increasing from left to right, like [3,2,1]), then this is the last permutation.

  2. So we just reverse the entire array to get the first permutation (ascending).

  1. If such i is found:

    • Find the smallest element greater than nums[i] on the right side (i.e., in nums[i+1 .. end]).

    • Because the right side is non-increasing, we can find this by scanning from the right until we find the first nums[j] > nums[i].

  2. Swap nums[i] and nums[j].

  3. Reverse the subarray nums[i+1 .. end]:

    • This makes the suffix the lowest possible order (ascending) after the pivot so that the whole array is the next lexicographically smallest arrangement.


4. Pseudo code:



Complexity:


For all implementations:

  • Time: O(n) – we scan from the right, then potentially scan again and reverse a suffix.

  • Space: O(1) extra – in-place operations only.


Example Walkthrough – [1,2,3]:


  • From right:

    • i = 1: nums[1]=2 < nums[2]=3 → pivot at i = 1.

  • Find j from right such that nums[j] > nums[1]:

    • j = 2, nums[2]=3 > 2.

  • Swap → [1,3,2].

  • Reverse suffix i+1..end → i+1 = 2 → only [2] → stays [1,3,2].


Example Walkthrough – [3,2,1]:


  • From right:

    • i = 1: 2 >= 1 → continue.

    • i = 0: 3 >= 2 → continue.

    • i = -1 → no pivot (array is descending).

  • Since i < 0, reverse entire array:

    • [1,2,3].


5. Java code:



6. C code:



7. C++ code:



8. Python code:



9. JavaScript code:


Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more