Next Permutation of Array in DSA Go - Deep Dive

Overview - Next Permutation of Array

What is it?

Next Permutation of Array is a way to rearrange numbers in an array to get the next bigger arrangement in order. If the array is already the biggest possible order, it resets to the smallest order. This helps find the next sequence in a list of all possible orders without listing them all. It works by changing the array in place, without extra space.

Why it matters

Without this method, finding the next bigger arrangement would mean generating all possible orders and sorting them, which is slow and uses a lot of memory. Next Permutation lets programs quickly jump to the next order, which is useful in puzzles, games, and algorithms that try different combinations. It makes tasks like generating permutations efficient and practical.

Where it fits

Before learning this, you should understand arrays and how to swap elements. After this, you can learn about generating all permutations, backtracking, and combinatorial algorithms that use permutations to solve complex problems.

Mental Model

Core Idea

Next Permutation finds the next bigger number by changing the array from right to left, swapping and reversing parts to get the smallest bigger arrangement.

Think of it like...

Imagine you have a row of books arranged by height. To find the next taller arrangement, you look from right to left to find the first book that can be swapped with a taller one on its right, then reorder the books after it to be as short as possible.

Array: [1, 2, 3, 6, 5, 4]
Step 1: Find pivot (from right, first decrease): 3 at index 2
Step 2: Find successor (just bigger than pivot): 4 at index 5
Step 3: Swap pivot and successor: [1, 2, 4, 6, 5, 3]
Step 4: Reverse suffix after pivot: [1, 2, 4, 3, 5, 6]

Build-Up - 7 Steps

1

Foundation

Understanding Permutations and Order

Concept: What permutations are and how arrays can represent ordered sequences.

A permutation is a way to arrange items in order. For example, [1, 2, 3] can be arranged as [1, 3, 2], [2, 1, 3], etc. These arrangements can be ordered from smallest to largest by comparing elements from left to right. Understanding this order helps us find the 'next' arrangement.

Result

You know that permutations can be listed in order and that each has a unique position in this list.

Understanding the order of permutations is key to finding the next arrangement without checking all possibilities.

2

Foundation

Swapping and Reversing Array Parts

Concept: How to swap two elements and reverse a part of an array.

Swapping means exchanging two elements in an array. Reversing means flipping the order of elements in a part of the array. For example, swapping elements at positions 1 and 3 in [1, 2, 3, 4] gives [1, 4, 3, 2]. Reversing from position 2 to 3 changes [1, 4, 3, 2] to [1, 4, 2, 3].

Result

You can change the array order by swapping and reversing parts.

Mastering these operations allows you to rearrange arrays efficiently, which is essential for next permutation.

3

Intermediate

Finding the Pivot Point

🤔Before reading on: do you think the pivot is found scanning from left or right? Commit to your answer.

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

To find the pivot, start from the end of the array and move left until you find an element smaller than the one to its right. This pivot marks where the next bigger permutation can start. If no such element exists, the array is the biggest permutation.

Result

You identify the position where the array stops increasing from the right.

Knowing where the array stops increasing helps locate the exact point to change for the next bigger arrangement.

4

Intermediate

Finding the Successor and Swapping

🤔Before reading on: do you think the successor is the smallest or largest element bigger than the pivot? Commit to your answer.

Concept: The successor is the smallest element to the right of the pivot that is bigger than the pivot.

After finding the pivot, scan from the end to find the successor. Swap the pivot and successor to make the array bigger but as small as possible. This step moves the pivot to a slightly bigger value.

Result

The array is now bigger but not yet the next permutation.

Swapping with the smallest bigger element ensures the next permutation is just one step bigger, not a big jump.

5

Intermediate

Reversing the Suffix After Pivot

Concept: After swapping, reverse the part of the array after the pivot to get the smallest order.

The part of the array after the pivot was in decreasing order. Reversing it makes it increasing, which is the smallest order possible. This completes the next permutation.

Result

The array now represents the next bigger permutation in order.

Reversing the suffix resets it to the smallest order, ensuring the next permutation is the immediate next bigger sequence.

6

Advanced

Handling the Last Permutation Case

🤔Before reading on: do you think the last permutation returns an error or resets? Commit to your answer.

Concept: If no pivot is found, the array is the biggest permutation and should reset to the smallest by reversing the whole array.

When the array is in descending order, it is the last permutation. The next permutation is the first one, which is the array sorted ascending. We reverse the entire array to achieve this.

Result

The array resets to the smallest permutation.

Recognizing the last permutation and resetting prevents errors and completes the cycle of permutations.

7

Expert

In-Place Algorithm and Time Complexity

🤔Before reading on: do you think next permutation requires extra memory or can be done in place? Commit to your answer.

Concept: Next Permutation is done in place with O(n) time and O(1) extra space by scanning and swapping elements.

The algorithm scans the array from right to left twice and swaps elements without extra arrays. This makes it efficient for large arrays and practical in real systems.

Result

You understand the algorithm is optimal in time and space.

Knowing the algorithm is in place and linear time explains why it is widely used in performance-critical applications.

Under the Hood

The algorithm works by scanning the array from right to left to find the pivot where the order breaks ascending. Then it finds the successor to swap with the pivot, ensuring the next bigger number. Finally, it reverses the suffix to get the smallest order after the pivot. This uses the property that the suffix is in descending order before reversal.

Why designed this way?

This design avoids generating all permutations by directly computing the next one. It leverages the sorted order of suffixes to minimize changes and uses in-place operations to save memory. Alternatives like generating all permutations or sorting would be slower or use more space.

Array: [a0, a1, ..., apivot, ..., an-1]
Step 1: Find pivot p where a[p] < a[p+1]
Step 2: Find successor s > a[p] in suffix
Step 3: Swap a[p] and a[s]
Step 4: Reverse suffix from p+1 to end

  ┌─────────────┐
  │ prefix     │
  ├─────────────┤
  │ pivot (p)  │
  ├─────────────┤
  │ suffix     │
  └─────────────┘

Suffix is descending before reversal, ascending after.

Myth Busters - 4 Common Misconceptions

Quick: Does next permutation always increase the first element? Commit yes or no.

Common Belief: Next permutation always changes the first element to a bigger number.

Reality: Next permutation changes the rightmost pivot element, which may not be the first element.

Why it matters: Assuming the first element always changes leads to wrong implementations that miss the correct pivot and produce incorrect permutations.

Quick: Is reversing the suffix optional after swapping? Commit yes or no.

Common Belief: After swapping pivot and successor, the suffix order does not matter.

Reality: Reversing the suffix is essential to get the smallest order after the pivot, ensuring the next permutation is immediate.

Why it matters: Skipping reversal results in permutations that are bigger but not the next immediate one, breaking correctness.

Quick: Does next permutation require extra memory to store permutations? Commit yes or no.

Common Belief: Next permutation needs extra arrays or memory to store permutations.

Reality: Next permutation works in place with constant extra space by swapping and reversing elements.

Why it matters: Thinking extra memory is needed can lead to inefficient solutions unsuitable for large data.

Quick: If the array is in descending order, is there a next bigger permutation? Commit yes or no.

Common Belief: If the array is descending, there is no next bigger permutation.

Reality: If the array is descending, the next permutation is the smallest one (ascending order).

Why it matters: Not resetting to the smallest permutation causes infinite loops or errors in algorithms cycling through permutations.

Expert Zone

1

The pivot is always the rightmost element where the ascending order breaks, ensuring minimal change for next permutation.

2

Reversing the suffix after swapping is equivalent to sorting it because the suffix is guaranteed to be in descending order before reversal.

3

The algorithm's in-place nature avoids overhead, but careful index management is needed to avoid off-by-one errors.

When NOT to use

Next Permutation is not suitable when you need all permutations at once or when permutations must be generated in a custom order. In such cases, backtracking or heap's algorithm are better alternatives.

Production Patterns

Used in combinatorial optimization, generating next states in puzzles, lexicographic ordering in databases, and algorithms that require stepping through permutations efficiently without full enumeration.

Connections

Lexicographic Order

Next Permutation generates the next sequence in lexicographic order.

Understanding lexicographic order helps grasp why the algorithm finds the next bigger arrangement by minimal changes.

Backtracking Algorithms

Next Permutation can be used to generate permutations iteratively instead of recursively backtracking.

Knowing next permutation offers an iterative alternative to backtracking for permutation generation, useful in memory-limited environments.

Music Composition Patterns

Both use permutations to explore different sequences of notes or elements.

Recognizing permutation patterns in music helps appreciate how next permutation explores ordered sequences efficiently.

Common Pitfalls

#1 Not finding the correct pivot from right to left.

Wrong approach:

for i := 0; i < len(nums)-1; i++ {
if nums[i] < nums[i+1] {
pivot = i
}
}

Correct approach:

pivot := -1
for i := len(nums)-2; i >= 0; i-- {
if nums[i] < nums[i+1] {
pivot = i
break
}
}

Root cause:

Scanning from left to right misses the rightmost pivot, leading to incorrect next permutation.

#2 Not reversing the suffix after swapping pivot and successor.

Wrong approach:

swap(nums, pivot, successor)
// missing reversal of suffix

Correct approach:

swap(nums, pivot, successor)
reverse(nums, pivot+1, len(nums)-1)

Root cause:

Forgetting to reverse leaves the suffix in descending order, not the smallest order needed.

#3 Trying to find successor by scanning from left instead of right.

Wrong approach:

for i := 0; i < len(nums); i++ {
if nums[i] > nums[pivot] {
successor = i
break
}
}

Correct approach:

for i := len(nums)-1; i > pivot; i-- {
if nums[i] > nums[pivot] {
successor = i
break
}
}

Root cause:

Successor must be the rightmost element bigger than pivot to ensure minimal increase.

Key Takeaways

Next Permutation finds the next bigger arrangement by changing the array from right to left, swapping a pivot with a successor, then reversing the suffix.

The pivot is the first element from the right that is smaller than its next element, marking where the next permutation starts.

Swapping the pivot with the smallest bigger element (successor) ensures the next permutation is just one step bigger.

Reversing the suffix after the pivot resets it to the smallest order, completing the next permutation.

If the array is the biggest permutation (descending order), next permutation resets it to the smallest (ascending 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