Next Permutation of Array in DSA Go

Mental Model

Find the next bigger arrangement of numbers by changing the smallest possible part of the array.

Analogy: Imagine you have a lock with numbers. To get the next code, you try to increase the last digits without changing the earlier ones too much, like counting up in a special way.

Array: [1] -> [2] -> [3] -> [4] -> [5]
Indexes:  0      1      2      3      4

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Find the next permutation which is just bigger than [1, 2, 3]

Step 1: Find the first index from right where array[i] < array[i+1]

[1, 2, 3] ↑i=1 (since 2 < 3)

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

Step 2: Find the first index from right where array[j] > array[i]

[1, 2, 3] ↑j=2 (3 > 2)

Why: We find a number just bigger than array[i] to swap and get a bigger permutation

Step 3: Swap array[i] and array[j]

[1, 3, 2]

Why: Swapping makes the number bigger but still close to original

Step 4: Reverse the subarray after index i

[1, 3, 2]

Why: Reversing makes the tail the smallest possible to get the next permutation

Result:

[1, 3, 2]

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func nextPermutation(nums []int) {
	n := len(nums)
	if n <= 1 {
		return
	}

	// Step 1: Find the first index i from right where nums[i] < nums[i+1]
	i := n - 2
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}

	// Step 2: If such index found, find j from right where nums[j] > nums[i]
	if i >= 0 {
		j := n - 1
		for nums[j] <= nums[i] {
			j--
		}

		// Step 3: Swap nums[i] and nums[j]
		nums[i], nums[j] = nums[j], nums[i]
	}

	// Step 4: Reverse the subarray from i+1 to end
	reverse(nums, i+1, n-1)
}

func reverse(nums []int, start, end int) {
	for start < end {
		nums[start], nums[end] = nums[end], nums[start]
		start++
		end--
	}
}

func main() {
	arr := []int{1, 2, 3}
	nextPermutation(arr)
	for i, v := range arr {
		if i > 0 {
			fmt.Print(", ")
		}
		fmt.Print(v)
	}
	fmt.Println()
}

i := n - 2 for i >= 0 && nums[i] >= nums[i+1] { i-- }

Find the first index from right where the order breaks (nums[i] < nums[i+1])

if i >= 0 { j := n - 1 for nums[j] <= nums[i] { j-- } nums[i], nums[j] = nums[j], nums[i] }

Find element just bigger than nums[i] from right and swap

reverse(nums, i+1, n-1)

Reverse the tail to get the smallest order after swap

Output

1, 3, 2

Complexity Analysis

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

Space: O(1) because we modify the array in place without extra storage

vs Alternative: Naive approach would generate all permutations and sort them, which is O(n!) and very inefficient

Edge Cases

array is in descending order like [3, 2, 1]

The function reverses the entire array to the smallest permutation [1, 2, 3]

DSA Go

i := n - 2
for i >= 0 && nums[i] >= nums[i+1] {
	i--
}

array has only one element like [1]

No change happens as there is no next permutation

DSA Go

if n <= 1 {
	return
}

array has repeated elements like [1, 5, 5]

Next permutation correctly swaps and reverses to get [5, 1, 5]

DSA Go

for i >= 0 && nums[i] >= nums[i+1] {
	i--
}

When to Use This Pattern

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

Common Mistakes

Mistake: Not reversing the tail after swapping, resulting in a wrong next permutation
Fix: Always reverse the subarray after the swapped index to get the smallest tail

Mistake: Swapping the wrong elements or not finding the correct indices i and j
Fix: Carefully find i as the first decreasing element from right and j as the first element bigger than nums[i] from right

Summary

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

Use when you need the next order arrangement without generating all permutations.

The key is to find the first decreasing element from right, swap with just bigger element, then reverse the tail.

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