Next Permutation of Array in DSA Rust

Mental Model

Find the next bigger arrangement of numbers by changing the smallest part possible. If none exists, start over with the smallest arrangement.

Analogy: Imagine you have a combination lock with digits. To get the next code, you try to increase the last digit. If it can't go higher, you move left until you find a digit you can increase, then reset the digits to the right to the smallest order.

Array: [1, 2, 3, 4]
Indexes:  0  1  2  3

We look from right to left to find where the order breaks:
Example: 1 -> 2 -> 3 -> 4
               ↑
           pivot here if next number is larger

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Find the next permutation after [1, 2, 3], which should be [1, 3, 2]

Step 1: Find the first index from the right where the number is smaller than the number after it (pivot).

[1, 2, 3]
Indexes: 0  1  2
Pivot found at index 1 (value 2) because 2 < 3

Why: We need to find where the ascending order breaks from the right to know where to increase.

Step 2: Find the first number from the right that is greater than the pivot (value 2).

[1, 2, 3]
Indexes: 0  1  2
Number at index 2 (3) is greater than pivot 2

Why: We want to swap pivot with the next bigger number to get the next permutation.

Step 3: Swap pivot (2) with this number (3).

[1, 3, 2]
Indexes: 0  1  2
After swapping pivot and next bigger number

Why: Swapping increases the number just enough to get the next permutation.

Step 4: Reverse the subarray to the right of the pivot index to get the smallest order.

[1, 3, 2]
Indexes: 0  1  2
Subarray after pivot is just one element (2), so reversing keeps it same

Why: Reversing ensures the tail is the smallest possible to get the immediate next permutation.

Result:

[1, 3, 2]

Annotated Code

DSA Rust

fn next_permutation(nums: &mut [i32]) {
    if nums.len() < 2 {
        return;
    }
    // Step 1: Find pivot
    let mut i = nums.len() - 2;
    while nums[i] >= nums[i + 1] {
        if i == 0 { break; }
        i -= 1;
    }
    // Step 2: If pivot found, find next bigger number
    if nums[i] < nums[i + 1] {
        let mut j = nums.len() - 1;
        while nums[j] <= nums[i] {
            j -= 1;
        }
        nums.swap(i, j); // Step 3: Swap
    }
    // Step 4: Reverse suffix
    let mut left = if nums[i] < nums[i + 1] { i + 1 } else { 0 };
    let mut right = nums.len() - 1;
    while left < right {
        nums.swap(left, right);
        left += 1;
        right -= 1;
    }
}

fn main() {
    let mut arr = vec![1, 2, 3];
    next_permutation(&mut arr);
    println!("{:?}", arr);
}

let mut i = nums.len() - 2; while nums[i] >= nums[i + 1] { if i == 0 { break; } i -= 1; }

Find pivot index from right where nums[i] < nums[i+1]

if nums[i] < nums[i + 1] { let mut j = nums.len() - 1; while nums[j] <= nums[i] { j -= 1; } nums.swap(i, j); }

Find next bigger number than pivot from right and swap

let mut left = if nums[i] < nums[i + 1] { i + 1 } else { 0 }; let mut right = nums.len() - 1; while left < right { nums.swap(left, right); left += 1; right -= 1; }

Reverse the suffix after pivot to get smallest order

Output

[1, 3, 2]

Complexity Analysis

Time: O(n) because we scan the array from right to left a few times but only once overall

Space: O(1) because all operations are done in place without extra storage

vs Alternative: Compared to generating all permutations and sorting, this is much faster and uses less memory

Edge Cases

Array is in descending order, e.g. [3, 2, 1]

No pivot found, so the entire array is reversed to the smallest order [1, 2, 3]

DSA Rust

if i == 0 { break; }

Array has only one element, e.g. [1]

Function returns immediately, no change

DSA Rust

if nums.len() < 2 { return; }

Array with repeated elements, e.g. [1, 5, 5]

Next permutation is found correctly as [5, 1, 5]

DSA Rust

while nums[j] <= nums[i] { j -= 1; }

When to Use This Pattern

When asked to find the next bigger arrangement of numbers or letters in order, use the next permutation pattern to efficiently find it without generating all permutations.

Common Mistakes

Mistake: Not reversing the suffix after swapping pivot and next bigger number
Fix: Always reverse the subarray after the pivot index to get the smallest next permutation

Mistake: Incorrectly handling the case when no pivot is found (array is descending)
Fix: If no pivot found, reverse the entire array to get the smallest permutation

Summary

Finds the next lexicographically bigger permutation of the array in place.

Use when you need the immediate next arrangement of elements in order.

The key is to find the pivot from right, swap with next bigger number, then reverse the suffix.

Practice

1. What does the next_permutation algorithm do to an array of numbers?

easy

A. It rearranges the array to the next lexicographically greater permutation.

B. It sorts the array in ascending order.

C. It reverses the array.

D. It finds the maximum element in the array.

Solution

1. Step 1: Understand the purpose of next_permutation

   The algorithm finds the next arrangement of elements that is just larger than the current one in dictionary order.

2. Step 2: Compare with other options

   Sorting or reversing changes order but does not guarantee the next lexicographical permutation. Finding max element is unrelated.

3. Final Answer:

   It rearranges the array to the next lexicographically greater permutation. -> Option A

4. Quick Check:

   Next permutation = next lexicographically greater order [OK]

Hint: Next permutation means next bigger order arrangement [OK]

Common Mistakes:

• Confusing next permutation with sorting
• Thinking it reverses the array always
• Assuming it finds max element

2. Which of the following Rust code snippets correctly swaps two elements in a vector nums at indices i and j?

easy

A. nums.swap(i, j) -> ();

B. nums[i] = nums[j]; nums[j] = nums[i];

C. nums.swap(i, j);

D. nums.swap_elements(i, j);

Solution

1. Step 1: Recall Rust vector swap method

   Rust's standard Vec<T> has a method swap(i, j) to exchange elements at indices i and j.

2. Step 2: Check other options for correctness

   nums[i] = nums[j]; nums[j] = nums[i]; incorrectly assigns values without temporary storage, causing wrong swap. nums.swap_elements(i, j); uses a non-existent method. nums.swap(i, j) -> (); has invalid syntax.

3. Final Answer:

   nums.swap(i, j); -> Option C

4. Quick Check:

   Correct swap method = nums.swap(i, j) [OK]

Hint: Use nums.swap(i, j) to swap elements in Rust vector [OK]

Common Mistakes:

• Assigning without temp variable causing overwrite
• Using non-existent methods
• Incorrect syntax with arrows or extra symbols

3. What is the output of the following Rust code that finds the next permutation of nums = vec![1, 3, 2]?

let mut nums = vec![1, 3, 2];
if next_permutation(&mut nums) {
    println!("{:?}", nums);
} else {
    println!("No next permutation");
}

fn next_permutation(nums: &mut Vec<i32>) -> bool {
    let n = nums.len();
    if n < 2 { return false; }
    let mut i = n - 2;
    while i != usize::MAX && nums[i] >= nums[i + 1] {
        if i == 0 { break; }
        i -= 1;
    }
    if i == usize::MAX || nums[i] >= nums[i + 1] {
        nums.reverse();
        return false;
    }
    let mut j = n - 1;
    while nums[j] <= nums[i] {
        j -= 1;
    }
    nums.swap(i, j);
    nums[i + 1..].reverse();
    true
}

medium

A. [2, 1, 3]

B. [1, 2, 3]

C. [1, 3, 2]

D. No next permutation

Solution

1. Step 1: Identify pivot index i

   Starting from right, find i where nums[i] < nums[i+1]. For [1,3,2], i=0 because 1 < 3.

2. Step 2: Find j to swap with i

   From right, find j where nums[j] > nums[i]. Here j=2 (value 2 > 1).

3. Step 3: Swap and reverse suffix

   Swap nums[0] and nums[2]: [2,3,1]. Then reverse suffix after i: reverse [3,1] to [1,3]. Result: [2,1,3].

4. Step 4: Check code logic carefully

   Code breaks loop early if i=0 and condition met, so i=0 is pivot. But code returns false and reverses if no pivot found. Here pivot found, so returns true and prints new nums.

5. Final Answer:

   [2, 1, 3] -> Option A

6. Quick Check:

   Next permutation of [1,3,2] = [2,1,3] [OK]

Hint: Find pivot i, swap with j, reverse suffix [OK]

Common Mistakes:

• Not reversing suffix after swap
• Wrong pivot index calculation
• Confusing when to return false

4. The following Rust function attempts to implement next permutation but has a bug. What is the bug?

fn next_permutation(nums: &mut Vec<i32>) -> bool {
    let n = nums.len();
    if n < 2 { return false; }
    let mut i = n - 2;
    while nums[i] >= nums[i + 1] {
        i -= 1;
    }
    if nums[i] >= nums[i + 1] {
        nums.reverse();
        return false;
    }
    let mut j = n - 1;
    while nums[j] <= nums[i] {
        j -= 1;
    }
    nums.swap(i, j);
    nums[i + 1..].reverse();
    true
}

medium

A. The suffix reversal is missing.

B. The loop misses checking when i == 0, causing panic on underflow.

C. The swap method is used incorrectly.

D. The function does not return a boolean.

Solution

1. Step 1: Analyze the while loop condition

   The loop uses while nums[i] >= nums[i + 1] and decrements i. When i reaches 0 and condition holds, next decrement causes underflow (usize wraps to large number).

2. Step 2: Check consequences

   This causes panic or incorrect behavior. The correct approach is to use i != usize::MAX or check before decrementing to avoid underflow.

3. Final Answer:

   The loop misses checking when i == 0, causing panic on underflow. -> Option B

4. Quick Check:

   Loop underflow bug = missing i == 0 check [OK]

Hint: Check loop index underflow when decrementing unsigned integers [OK]

Common Mistakes:

• Ignoring unsigned integer underflow
• Incorrect swap usage
• Forgetting to reverse suffix

5. Given a vector nums = vec![3, 2, 1], which is the highest permutation, what will be the state of nums after applying the next permutation function that returns false when no next permutation exists?

hard

A. [3, 2, 1]

B. Original vector unchanged

C. Empty vector

D. [1, 2, 3]

Solution

1. Step 1: Identify if next permutation exists

   For [3, 2, 1], the array is in descending order, which is the highest permutation. No next permutation exists.

2. Step 2: Apply algorithm behavior when no next permutation

   The algorithm reverses the entire array to the lowest permutation and returns false.

3. Final Answer:

   [1, 2, 3] -> Option D

4. Quick Check:

   Highest permutation reversed = lowest permutation [OK]

Hint: No next permutation means reverse to lowest order [OK]

Common Mistakes:

• Expecting no change when no next permutation
• Returning empty vector incorrectly
• Confusing highest and lowest permutations