Next Permutation
Find the next lexicographically greater permutation of numbers in O(n) time and O(1) space. If the current permutation is the last one, rearrange to the smallest permutation (sorted order). This algorithm is essential for generating all permutations in sorted order without recursion, used in combinatorial optimization, constraint satisfaction, and generating test cases. The algorithm is elegant and optimal.
Visualization
Interactive visualization for Next Permutation
Interactive visualization with step-by-step execution
Implementation
1function nextPermutation(nums: number[]): void {
2 let i = nums.length - 2;
3
4 while (i >= 0 && nums[i] >= nums[i + 1]) {
5 i--;
6 }
7
8 if (i >= 0) {
9 let j = nums.length - 1;
10 while (nums[j] <= nums[i]) {
11 j--;
12 }
13 [nums[i], nums[j]] = [nums[j], nums[i]];
14 }
15
16 reverse(nums, i + 1);
17}
18
19function reverse(nums: number[], start: number): void {
20 let end = nums.length - 1;
21 while (start < end) {
22 [nums[start], nums[end]] = [nums[end], nums[start]];
23 start++;
24 end--;
25 }
26}Deep Dive
Theoretical Foundation
Next Permutation finds the lexicographically next arrangement by making the smallest possible change. Key observation: to get next permutation, we need to increase the sequence as minimally as possible. Algorithm: (1) Find rightmost ascending pair (i, i+1) where arr[i] < arr[i+1]. This identifies the position to change. (2) Find the smallest element in arr[i+1...n-1] that's greater than arr[i], swap them. (3) Reverse arr[i+1...n-1] to get the smallest arrangement. If no ascending pair exists, array is in descending order (last permutation), so reverse entire array to get first permutation. Time: O(n), Space: O(1).
Complexity
Time
O(n)
O(n)
O(n)
Space
O(1)
Applications
Industry Use
Generating all permutations iteratively
Combinatorial optimization problems
Test case generation
Traveling Salesman Problem enumeration
Anagram generation in lexicographic order
C++ STL algorithm implementation
Use Cases
Related Algorithms
GCD (Euclidean Algorithm)
Compute the Greatest Common Divisor (GCD) of two integers using the Euclidean algorithm. Dating back to around 300 BC and appearing in Euclid's Elements, it's one of the oldest algorithms still in common use. The algorithm is based on the principle that GCD(a,b) = GCD(b, a mod b) and is remarkably efficient with O(log min(a,b)) time complexity. The GCD is the largest positive integer that divides both numbers without remainder.
LCM (Least Common Multiple)
Calculate the Least Common Multiple (LCM) of two integers - the smallest positive integer that is divisible by both numbers. The LCM is intimately related to the GCD through the formula: LCM(a,b) = |a×b| / GCD(a,b). This relationship allows us to compute LCM efficiently using the Euclidean algorithm for GCD, achieving O(log min(a,b)) time complexity instead of naive factorization methods.
Sieve of Eratosthenes
Ancient and highly efficient algorithm to find all prime numbers up to a given limit n. Invented by Greek mathematician Eratosthenes of Cyrene (276-194 BC), this sieve method systematically eliminates multiples of primes, leaving only primes in the array. With O(n log log n) time complexity, it remains one of the most practical algorithms for generating large lists of primes, vastly superior to trial division which runs in O(n² / log n) time.
Prime Factorization
Decompose a positive integer into its unique prime factor representation. Every integer greater than 1 can be expressed as a product of prime numbers in exactly one way (Fundamental Theorem of Arithmetic). This algorithm uses trial division optimized to check only up to √n, as any composite number must have a prime factor ≤ √n. Returns a map of prime factors to their powers, e.g., 360 = 2³ × 3² × 5¹.