Next Permutation of Array in DSA Rust - Execution Trace

Concept Flow - Next Permutation of Array

Start from right end

↓

Find first pair where nums[i

↓

If no such pair, reverse whole array -> Done

No↓

Find element nums[j

↓

Swap nums[i

↓

Reverse subarray nums[i+1:

↓

Done with next permutation

Find the next lexicographically greater permutation by identifying a pivot, swapping, and reversing the suffix.

Execution Sample

DSA Rust

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

This code finds the next permutation of the array by swapping and reversing parts of it.

Execution Table

Step	Operation	Index i	Index j	Array State	Pointer Changes
1	Initialize i to n-2	3	-	[1, 2, 3, 6, 5, 4]	i=3, j=undefined
2	Check nums[i] >= nums[i+1]	3	-	6 >= 5 is True	i=3
3	Decrement i	2	-	[1, 2, 3, 6, 5, 4]	i=2
4	Check nums[i] >= nums[i+1]	2	-	3 >= 6 is False	i=2
5	Find j from right where nums[j] > nums[i]	2	5	[1, 2, 3, 6, 5, 4]	j=5
6	Check nums[j] <= nums[i]	2	5	4 <= 3 is False	j=5
7	Swap nums[i] and nums[j]	2	5	[1, 2, 4, 6, 5, 3]	Swapped indices 2 and 5
8	Reverse subarray from i+1 to end	2	-	Reverse nums[3..6]	Reversed suffix
9	Array after reverse	2	-	[1, 2, 4, 3, 5, 6]	Final array state
10	End	-	-	[1, 2, 4, 3, 5, 6]	Next permutation found

💡 Completed next permutation by swapping pivot and successor, then reversing suffix.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	Final
i	3	2	2	2	2	2
j	-	-	5	5	5	5
Array	[1, 2, 3, 6, 5, 4]	[1, 2, 3, 6, 5, 4]	[1, 2, 3, 6, 5, 4]	[1, 2, 4, 6, 5, 3]	[1, 2, 4, 3, 5, 6]	[1, 2, 4, 3, 5, 6]

Key Moments - 3 Insights

Why do we start looking for i from the right end of the array?

Because the next permutation changes the smallest suffix possible. Starting from the right finds the longest non-increasing suffix to modify, as shown in steps 2-4.

Why do we reverse the subarray after swapping?

After swapping, the suffix is still in descending order. Reversing it makes it the smallest ascending order, ensuring the next permutation is just one step bigger, as in steps 8-9.

What if no i is found where nums[i] < nums[i+1]?

It means the array is in descending order, the highest permutation. We reverse the whole array to get the lowest permutation. This case is not in this example but is handled by the if condition in the code.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of i after step 4?

A 2

B 3

C 1

D 4

💡 Hint

Check the 'Index i' column at step 4 in the execution_table.

At which step does the array change from [1, 2, 3, 6, 5, 4] to [1, 2, 4, 6, 5, 3]?

A Step 6

B Step 7

C Step 5

D Step 8

💡 Hint

Look for the 'Swap nums[i] and nums[j]' operation in the execution_table.

If the array was already in descending order, what would the algorithm do?

A Swap the first two elements

B Do nothing

C Reverse the entire array

D Swap the last two elements

💡 Hint

Refer to the key moment about no i found where nums[i] < nums[i+1].

Concept Snapshot

Next Permutation Algorithm:
- Find the first index i from right where nums[i] < nums[i+1]
- If none, reverse entire array (lowest permutation)
- Else find j from right where nums[j] > nums[i]
- Swap nums[i] and nums[j]
- Reverse subarray nums[i+1..end]
- Result is next lexicographically greater permutation

Full Transcript

The next permutation algorithm finds the next lexicographically greater arrangement of numbers. It starts from the right end to find the first pair where the left number is smaller than the right. If none is found, the array is reversed to the smallest order. Otherwise, it finds a number just larger than this pivot from the right, swaps them, and reverses the suffix to get the next permutation. This process ensures the smallest increase possible in the sequence.

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