Next Permutation - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Next Permutation" Problem in Go

Difficulty: Medium | Tags: Array, Two Pointers

Introduction

The "Next Permutation" problem requires finding the lexicographically next greater permutation of an array. If no such permutation exists, the array should be rearranged into the smallest possible order. This problem is fundamental in understanding permutations and array manipulations.

Problem Analysis

Given an array of integers, the task is to rearrange it into the next lexicographically greater permutation. For example, the next permutation of [1,2,3] is [1,3,2], while [3,2,1] cycles back to [1,2,3]. The solution must be in-place with constant extra memory.

Solution Approach

The solution involves three steps: 1) Find the first decreasing element from the end. 2) Swap it with the smallest larger element found after it. 3) Reverse the suffix to ensure the smallest possible order. This approach efficiently finds the next permutation without generating all permutations.

Go Implementation


func nextPermutation(nums []int) {
    n := len(nums)
    i := n - 2
    // Step 1: Find the first decreasing element
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }
    if i >= 0 {
        j := n - 1
        // Step 2: Find the smallest larger element to swap
        for j >= 0 && nums[j] <= nums[i] {
            j--
        }
        nums[i], nums[j] = nums[j], nums[i]
    }
    // Step 3: Reverse the suffix
    left, right := i+1, n-1
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

Complexity Analysis

The algorithm runs in O(n) time, where n is the length of the array, as it performs a linear scan and a reversal. The space complexity is O(1) since the operations are done in-place.

Testing and Examples

Test cases:
1. Input: [1,2,3] → Output: [1,3,2]
2. Input: [3,2,1] → Output: [1,2,3]
3. Input: [1,1,5] → Output: [1,5,1]
Edge cases include single-element arrays and already descending arrays.

Best Practices and Tips

Key takeaways: Always handle edge cases like single-element arrays. Ensure the in-place requirement is met. The three-step approach is efficient and avoids brute-force methods. Practice similar permutation problems to reinforce understanding.

Read more