Next Permutation
Finding the next permutation of an array can be done through the following steps:
Find the First Decreasing Element: Traverse the array from right to left and find the first number that is smaller than the number immediately to its right.
Find the Next Larger Element: If a smaller number is found, then traverse the array again from right to left and find the first number that is larger than the found smaller number.
Swap the Elements: Swap the smaller number with the found larger number.
Reverse the Subarray: Reverse the subarray to the right of the original position of the smaller number.
Sort if No Permutation Found: If no smaller number is found, then the array is sorted in descending order, and there is no next permutation. In this case, sort the array in ascending order.
Here’s the code:


This solution modifies the array nums
inplace to contain the next permutation and uses constant extra memory.
The time complexity is (O(n)), where (n) is the length of the array, as all the steps involve linear traversals or operations on the array. The space complexity is (O(1)) as we are modifying the array in place and not using any additional space.
Identifying Problem Isomorphism
“Next Permutation” requires you to rearrange numbers into the lexicographically next greater permutation of numbers. If such an arrangement is not possible, it must be rearranged as the lowest possible order.
An approximate isomorphic problem is “Permutations II”, which requires generating all possible unique permutations from a collection of numbers. Both problems deal with permutations of an array, but the tasks are distinct.
A simpler problem is “Permutations”. Here, the task is just to generate all possible permutations from a collection of numbers without having to worry about duplicates or ordering.
A more complex problem is “Permutation Sequence”, where you’re given two numbers n and k, and have to return the kth permutation sequence. This requires a more intricate understanding of permutations and their orderings.
From simpler to more complex:
 “Permutations”  Only requires generating all permutations.
 “Next Permutation”  Requires finding the lexicographically next greater permutation.
 “Permutations II”  Requires generating all unique permutations, adding complexity with the consideration of duplicates.
 “Permutation Sequence”  Requires determining the kth permutation sequence, adding complexity with an additional parameter and the requirement to find a specific permutation sequence.
These share the theme of permutations but the specific tasks and conditions vary. This is an approximate mapping based on the shared theme.


Problem Classification
Permutation
Language Agnostic Coding Drills
Variable assignment
 Learn how to create and assign values to variables.
Lists
 Understand what a list is, how to create one and access its elements.
Basic Arithmetic operations
 Learn how to perform basic arithmetic operations such as subtraction (
=
) and addition.
 Learn how to perform basic arithmetic operations such as subtraction (
Loops (while loops)
 Learn about loops in programming, focusing specifically on
while
loops.
 Learn about loops in programming, focusing specifically on
Conditional Statements (if)
 Understand the
if
statement and how it’s used to make decisions in the code.
 Understand the
Comparisons
 Learn about comparison operators such as
>
,<=
.
 Learn about comparison operators such as
Indexes in Lists
 Understand how indexing works in lists, including negative indexing.
List Slicing
 Learn how to slice a list to get a subset of the list.
List methods (reverse)
 Learn about the
reverse
method that’s used to reverse a list.
 Learn about the
Multiple assignments
 Understand how to swap values of variables or list elements in one line.
 Defining Classes and Methods
 Understand how to define a class and methods, including the
self
keyword.
 Inplace methods
 Understand methods that modify data structures inplace without creating a new copy.
Here is the progression of difficulty:
 Variable assignment
 Basic Arithmetic operations
 Lists
 Indexes in Lists
 Conditional Statements (if)
 Loops (while loops)
 Comparisons
 Multiple assignments
 List Slicing
 List methods (reverse)
 Defining Classes and Methods
 Inplace methods
Targeted Drills in Python
 Variable assignment


 Basic Arithmetic operations


 Lists


 Indexes in Lists


 Conditional Statements (if)


 Loops (while loops)


 Comparisons


 Multiple assignments


 List Slicing


 List methods (reverse)


 Defining Classes and Methods


 Inplace methods


title: Next Permutation excerpt: This article show how to generate next permutation using recursion. tags: twopointersmovingtowardseachother swap
The term lexicographically means alphabetically ordered. In this problem it means next greater permutation:
1,2,3 => 1,3,2 (This permutation is the next highest value)
Somehow we need to find the smallest increase that results in the next permutation.
If the permutation is: [3,2,1]
[3,1,2] [1,3,2]
[1,2,3,3] [1,3,2,3]
[1,2,3,4,5,6,7,8,9] [1,2,3,4,5,6,7,9,8]
We only need one swap operation to find the next biggest number. If the numbers are in descending order:
Pick the permutation that is in the last location and return it.
output = [[p1], ….. [pn]]
If the numbers in the input is in ascending order:
output = [[p1], [p2]]
The next permutation is the second permutation generated by the DFS.
Assumptions
 We cannot assume that the numbers are sorted.
 There could be duplicates
 We cannot modify the order in which the integers appear in the input.
Example 4 is the base case [x] => [x]
[1,2] => [2,1]
We need to find the next lexicographic permutation of the given list of numbers rather than the number formed by the given array.
Implementation


Building Blocks
 Two Pointers Moving Towards Each Other
 Swap