Next Permutation of Array in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the purpose of the Next Permutation algorithm?

It finds the next lexicographically greater permutation of an array of numbers. If no such permutation exists, it rearranges the array to the lowest possible order (sorted ascending).

intermediate

In the Next Permutation algorithm, what is the significance of finding the first decreasing element from the right?

It identifies the pivot point where the array can be changed to get a bigger permutation. This element is the first one from the right that is smaller than its next element.

intermediate

Why do we reverse the suffix after swapping in the Next Permutation algorithm?

Because the suffix after the pivot is in descending order, reversing it makes it the smallest ascending order, ensuring the next permutation is the immediate next bigger one.

beginner

What happens if the Next Permutation algorithm does not find a pivot (no decreasing element from right)?

It means the array is in the highest possible order. The algorithm reverses the entire array to get the lowest order (sorted ascending).

intermediate

Show the step-by-step transformation of the array [1, 3, 2] using Next Permutation.

1. Find pivot: 1 (since 1 < 3) at index 0
2. Find element just bigger than pivot from right: 2 at index 2
3. Swap pivot and this element: [2, 3, 1]
4. Reverse suffix after pivot index: suffix is [3, 1], reversed to [1, 3]
5. Final array: [2, 1, 3]

What does the Next Permutation algorithm do if the array is sorted in descending order?

A Reverses the array to ascending order

B Leaves the array unchanged

C Sorts the array in descending order again

D Swaps the first two elements

If the array is in descending order, it is the highest permutation, so the algorithm reverses it to the lowest ascending order.

In Next Permutation, what is the first step to find the pivot?

A Find the smallest element in the array

B Find the first element from left that is smaller than the next

C Find the largest element in the array

D Find the first element from right that is smaller than the next

The pivot is the first element from the right that is smaller than the element after it.

After swapping the pivot, what operation is done on the suffix in Next Permutation?

A Sort the suffix in descending order

B Reverse the suffix

C Leave the suffix unchanged

D Swap the first two elements of the suffix

The suffix is reversed to get the smallest ascending order after the pivot swap.

What is the time complexity of the Next Permutation algorithm?

A O(n log n)

B O(n^2)

C O(n)

D O(1)

The algorithm scans the array a few times linearly, so it runs in O(n) time.

Which of these arrays is the next permutation of [1, 2, 3]?

A [1, 3, 2]

B [3, 2, 1]

C [2, 1, 3]

D [1, 2, 3]

The next permutation after [1, 2, 3] is [1, 3, 2].

Explain the steps of the Next Permutation algorithm and why each step is necessary.

Think about how to get the next bigger arrangement of numbers.

Describe what happens when the input array is already the highest permutation in Next Permutation algorithm.

Consider the array sorted descending.

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