Skip to main content
Talentd

Permutations III - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBacktracking7 min readAsked at: Goldman Sachs
Practice this problem

Problem Statement

Given an integer n, an alternating permutation is a permutation of the first n positive integers such that no two adjacent elements are both odd or both even.

Return all such alternating permutations sorted in lexicographical order.

 

Example 1:

Input: n = 4

Output: [[1,2,3,4],[1,4,3,2],[2,1,4,3],[2,3,4,1],[3,2,1,4],[3,4,1,2],[4,1,2,3],[4,3,2,1]]

Example 2:

Input: n = 2

Output: [[1,2],[2,1]]

Example 3:

Input: n = 3

Output: [[1,2,3],[3,2,1]]

 

Constraints:

  • 1 <= n <= 10

Approach Overview

Problem Overview: Generate all permutations of numbers 1..n such that every pair of adjacent elements has different parity. In other words, an odd number must be followed by an even number and vice versa.

Approach 1: Brute Force Permutation + Validation (O(n! * n) time, O(n) space)

Generate every permutation of 1..n and check whether it satisfies the parity condition. For each permutation, iterate through the array and verify that perm[i] % 2 != perm[i+1] % 2. If any adjacent pair has the same parity, discard it. This approach is straightforward but inefficient because it explores all n! permutations even though most will be invalid. The validation step adds an additional O(n) scan per permutation.

Approach 2: Backtracking with Parity Pruning (O(n! * n) time, O(n) space)

Use backtracking to build permutations incrementally. Maintain a used array to track which numbers are already placed. When choosing the next number, check the last element in the current path. Only place a number if its parity differs from the previous value. This pruning avoids generating invalid permutations early in the search tree. The recursion explores only feasible branches, which reduces the constant factor compared to brute force while still having a worst‑case complexity of O(n! * n).

The algorithm works well because the constraint is local. You only need to compare the candidate value with the previous element in the current permutation. Each recursive call appends a valid number, marks it as used, and continues exploring until the permutation length reaches n. Store each valid permutation in the result list.

This pattern appears frequently in permutation problems involving constraints. The combination of a path array and a boolean used structure is a standard technique for problems involving arrays and backtracking. Constraint checks placed before recursion dramatically reduce unnecessary exploration.

Recommended for interviews: Backtracking with pruning is the expected solution. Brute force shows you understand permutation generation, but pruning based on parity demonstrates the ability to reduce the search space during recursion.

Solution

We design a function dfs(i), which represents filling the i-th position, with position indices starting from 0.

In dfs(i), if i geq n, it means all positions have been filled, and we add the current permutation to the answer array.

Otherwise, we enumerate the numbers j that can be placed in the current position. If j has not been used and j has a different parity from the last number in the current permutation, we can place j in the current position and continue to recursively fill the next position.

The time complexity is O(n times n!), and the space complexity is O(n). Here, n is the length of the permutation.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Permutation + ValidationO(n! * n)O(n)When demonstrating basic permutation generation before applying constraints
Backtracking with Parity PruningO(n! * n)O(n)General case; avoids exploring invalid permutations early

Frequently Asked Questions

Is Permutations III easy or hard?
Permutations III is usually classified as Medium. The permutation generation itself is straightforward, but recognizing that you should prune invalid branches during backtracking is the key insight.
Permutations III Python/Java solution
Python, Java, C++, Go, and TypeScript implementations all follow the same pattern: maintain a current path, track used numbers, and recursively add candidates whose parity differs from the last element. Once the path length reaches n, append it to the result.
How to solve Permutations III in O(n)?
Permutations III cannot be solved in O(n) time because the output itself can contain up to O(n!) permutations. The practical approach is backtracking with pruning, which still has factorial worst‑case complexity but avoids exploring clearly invalid branches.
What is the best approach for Permutations III?
Backtracking with pruning is the best approach. Build the permutation step by step and only add a number if its parity differs from the previous element. This avoids generating invalid permutations and keeps the search space smaller than brute force enumeration.
Is Permutations III asked at Google/Amazon/Meta?
Permutation generation with constraints is a common interview pattern at companies like Google, Amazon, and Meta. Variations often require pruning conditions such as parity rules, adjacency constraints, or duplicate handling during backtracking.
What data structure is used in Permutations III?
The solution typically uses an array or list to store the current permutation and a boolean array (or set) to track used numbers. Recursion implements the backtracking search while enforcing the parity constraint.
What is the time complexity of Permutations III?
The worst‑case time complexity is O(n! * n). The algorithm may generate many permutations, and copying or validating each permutation takes O(n). Space complexity is O(n) for the recursion stack and the used array, excluding the result list.

Ready to solve this problem?

Practice Permutations III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Permutations IV