Next Permutation of Array in DSA Go - Execution Trace

Concept Flow - Next Permutation of Array

Start from right end

↓

Find first i where nums[i

Yes↓

Find j from right where nums[j

↓

Swap nums[i

↓

Reverse nums[i+1:

↓

Done

No↓

Reverse whole array (last permutation)

Find the first decreasing element from right, swap it with a just larger element on right, then reverse the suffix to get the next permutation.

Execution Sample

DSA Go

nums := []int{1, 2, 3}
// Find i
// Find j
// Swap nums[i], nums[j]
// Reverse suffix

This code finds the next lexicographical permutation of the array nums.

Execution Table

Step	Operation	Index i	Index j	Array State	Pointer Changes
1	Start with array	-	-	[1, 2, 3]	i = -, j = -
2	Find i where nums[i] < nums[i+1]	i=1	-	[1, 2, 3]	i=1 (nums[1]=2 < nums[2]=3)
3	Find j where nums[j] > nums[i]	1	2	[1, 2, 3]	j=2 (nums[2]=3 > nums[1]=2)
4	Swap nums[i] and nums[j]	1	2	[1, 3, 2]	Swapped nums[1] and nums[2]
5	Reverse suffix from i+1 to end	1	2	[1, 3, 2]	Reversed suffix nums[2:] (only one element)
6	Done - next permutation found	-	-	[1, 3, 2]	Final array state
7	If no i found (descending order)	-	-	[3, 2, 1]	Reverse whole array to [1, 2, 3]

💡 Execution stops after reversing suffix or reversing whole array if no next permutation.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
i	-	1	1	1	1	-
j	-	-	2	2	2	-
nums	[1, 2, 3]	[1, 2, 3]	[1, 2, 3]	[1, 3, 2]	[1, 3, 2]	[1, 3, 2]

Key Moments - 3 Insights

Why do we look for the first i from the right where nums[i] < nums[i+1]?

Because this identifies the pivot where the array stops increasing from the right. The next permutation must change this pivot to get a bigger number. See step 2 in execution_table.

Why do we reverse the suffix after swapping?

Because the suffix after i is in descending order. Reversing it makes it the smallest order, ensuring the next permutation is just one step bigger. See step 5 in execution_table.

What if the array is in descending order and no i is found?

Then the array is the highest permutation. We reverse the whole array to get the lowest permutation (step 7).

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the value of i?

A 0

B 1

C 2

D -

💡 Hint

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

At which step is the array suffix reversed?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the operation 'Reverse suffix' in execution_table.

If the array is [3, 2, 1], what operation happens according to step 7?

A Reverse whole array

B Swap elements

C Find i and j

D No change

💡 Hint

Step 7 describes the case when no i is found and the array is reversed.

Concept Snapshot

Next Permutation Algorithm:
1. Find the first index i from right where nums[i] < nums[i+1].
2. Find index j from right where nums[j] > nums[i].
3. Swap nums[i] and nums[j].
4. Reverse the subarray nums[i+1:] to get the next permutation.
If no i found, reverse whole array to get lowest permutation.

Full Transcript

The next permutation algorithm finds the next bigger arrangement of numbers in an array. It starts from the right end to find the first position i where the number is smaller than the next one. Then it finds a number j to the right that is just bigger than nums[i]. It swaps these two numbers and reverses the part of the array after i to get the smallest bigger number. If the array is in descending order, it reverses the whole array to get the smallest permutation. This process ensures we get the next permutation in lexicographical order.

Practice

1. What does the next permutation of an array represent?

easy

A. The next lexicographically greater arrangement of the array elements

B. The array sorted in ascending order

C. The array reversed

D. The smallest element moved to the front

Solution

1. Step 1: Understand the concept of permutation order

   Permutations can be ordered lexicographically like words in a dictionary.

2. Step 2: Define next permutation

   The next permutation is the next arrangement that is just larger than the current one in this order.

3. Final Answer:

   The next lexicographically greater arrangement of the array elements -> Option A

4. Quick Check:

   Next permutation = next bigger arrangement [OK]

Hint: Think of next permutation as next dictionary word [OK]

Common Mistakes:

• Confusing next permutation with sorting
• Thinking it always reverses the array
• Assuming it moves smallest element to front

2. Which Go code snippet correctly swaps two elements nums[i] and nums[j] in an array?

easy

A. swap(nums[i], nums[j])

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

C. nums[i], nums[j] = nums[j], nums[i]

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

Solution

1. Step 1: Recall Go multiple assignment syntax

   Go allows swapping two variables in one line using multiple assignment.

2. Step 2: Identify correct swap syntax

   The syntax nums[i], nums[j] = nums[j], nums[i] swaps values correctly without temporary variable.

3. Final Answer:

   nums[i], nums[j] = nums[j], nums[i] -> Option C

4. Quick Check:

   Go swap uses multiple assignment [OK]

Hint: Use Go's multiple assignment for swapping [OK]

Common Mistakes:

• Using undefined swap function
• Forgetting temporary variable in manual swap
• Assigning both to same value causing loss

3. What is the output of the following Go code that finds the next permutation of nums := []int{1, 3, 2}?

func nextPermutation(nums []int) {
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }
    if i >= 0 {
        j := len(nums) - 1
        for nums[j] <= nums[i] {
            j--
        }
        nums[i], nums[j] = nums[j], nums[i]
    }
    left, right := i+1, len(nums)-1
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

func main() {
    nums := []int{1, 3, 2}
    nextPermutation(nums)
    fmt.Println(nums)
}

medium

A. [1, 2, 3]

B. [2, 1, 3]

C. [1, 3, 2]

D. [3, 1, 2]

Solution

1. Step 1: Find first decreasing element from right

   Starting from index 1 (value 3), check if nums[i] >= nums[i+1]. At i=1, 3 >= 2 true, i=0, 1 >= 3 false, so i=0.

2. Step 2: Find element just larger than nums[i]

   From right, find j where nums[j] > nums[i] (nums[0]=1). j=2 (value 2) > 1, swap nums[0] and nums[2]. Array becomes [2,3,1]. Reverse suffix from i+1=1 to end: reverse [3,1] to [1,3]. Final array: [2,1,3].

3. Final Answer:

   [2, 1, 3] -> Option B

4. Quick Check:

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

Hint: Swap and reverse suffix after first decreasing index [OK]

Common Mistakes:

• Not reversing suffix after swap
• Swapping wrong elements
• Stopping at first decreasing element without swap

4. Identify the bug in this Go code snippet for next permutation:

func nextPermutation(nums []int) {
    i := len(nums) - 1
    for i > 0 && nums[i] <= nums[i-1] {
        i--
    }
    if i > 0 {
        j := len(nums) - 1
        for nums[j] <= nums[i-1] {
            j--
        }
        nums[i-1], nums[j] = nums[j], nums[i-1]
    }
    left, right := i, len(nums)-1
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

medium

A. The initial index i should start at len(nums) - 2, not len(nums) - 1

B. The swap should be between nums[i] and nums[j], not nums[i-1] and nums[j]

C. The reversal should start from i-1, not i

D. The loop conditions should use < instead of >

Solution

1. Step 1: Check starting index for finding first decreasing element

   The algorithm must start checking from second last element (len(nums)-2) to compare with next element.

2. Step 2: Identify impact of starting at len(nums)-1

   Starting at len(nums)-1 compares last element with out-of-range index, causing incorrect behavior or skipping needed checks.

3. Final Answer:

   The initial index i should start at len(nums) - 2, not len(nums) - 1 -> Option A

4. Quick Check:

   Start i at len(nums)-2 for correct next permutation [OK]

Hint: Start i at second last index to find decreasing pair [OK]

Common Mistakes:

• Starting i at last index causing index errors
• Swapping wrong elements
• Incorrect reversal range

5. Given an array nums := []int{3, 2, 1}, what will be the next permutation after applying the standard next permutation algorithm? Explain why.

hard

A. [3, 2, 1] because it is already the highest permutation

B. [3, 1, 2] because swapping first and last elements gives next permutation

C. [2, 3, 1] because reversing the array gives next permutation

D. [1, 2, 3] because the array is in descending order, so next permutation is the lowest ascending order

Solution

1. Step 1: Check if array is in descending order

   Array [3, 2, 1] is strictly descending, meaning it is the highest permutation possible.

2. Step 2: Apply next permutation rule for highest permutation

   When highest permutation is reached, next permutation is the lowest ascending order, which is [1, 2, 3].

3. Final Answer:

   [1, 2, 3] because the array is in descending order, so next permutation is the lowest ascending order -> Option D

4. Quick Check:

   Descending array next permutation = ascending array [OK]

Hint: If descending, next permutation is ascending sorted array [OK]

Common Mistakes:

• Thinking next permutation is same as current if descending
• Swapping wrong elements instead of reversing whole array
• Not resetting to lowest permutation after highest