NUHMAN.com

Introduction

LeetCode 31: Next Permutation is a classic array manipulation problem that requires finding the next lexicographically greater permutation of a given integer sequence.

If such an arrangement isn’t possible (i.e., the array is in descending order), we return the lowest possible order (ascending sort).

This problem is fundamental in understanding permutations, greedy logic, and in-place transformation.

Problem Statement

Rearrange the given array of integers into its next lexicographically greater permutation.

If no such permutation exists, rearrange it as the lowest possible order (i.e., sorted in ascending order). The replacement must be in-place with only constant extra memory.

Examples

go

Input: nums = [1,2,3]
Output: [1,3,2]
go

Input: nums = [3,2,1]
Output: [1,2,3]
go

Input: nums = [1,1,5]
Output: [1,5,1]

Approach: In-Place Next Permutation Algorithm

🔁 Steps:

1. Find the first decreasing element from the end:
2. Scan from right to left to find the first index i such that nums[i] < nums[i+1].
3. Find just-larger element from the end:
4. Find the smallest element on the right of i that is larger than nums[i] (say index j) and swap nums[i] with nums[j].
5. Reverse the subarray from i+1 to end:
6. This ensures we get the next smallest lexicographical sequence.

Go Implementation

go

package main

import (
	"fmt"
)

func nextPermutation(nums []int) {
	n := len(nums)
	i := n - 2

	// Step 1: Find first decreasing element from right
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}

	if i >= 0 {
		// Step 2: Find the just larger element from the end
		j := n - 1
		for j >= 0 && nums[j] <= nums[i] {
			j--
		}
		// Swap nums[i] and nums[j]
		nums[i], nums[j] = nums[j], nums[i]
	}

	// Step 3: Reverse the tail
	reverse(nums, i+1, n-1)
}

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

Example Walkthrough

go

Input: [1, 3, 2]

1. Find `i`: nums[0] = 1, nums[1] = 3 > 2 → so i = 0
2. Find `j`: nums[2] = 2 > nums[0] = 1 → j = 2
3. Swap: nums = [2, 3, 1]
4. Reverse from index 1: [2, 1, 3] ✅

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

Key Takeaways

• Understand how to manipulate permutations lexicographically.
• Be careful with edge cases like descending sorted arrays.
• Efficient in-place operations are key for interviews and optimization.