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.

Description Hints 1 Solution

3437. Permutations III

Medium86.2% acceptance1 companyPremium elsewhere, free here

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

Asked at 1 company

Goldman Sachs

Topics

Array Backtracking

Hints open one at a time

Hint 1

Use backtracking to generate permutations of the first n positive integers while ensuring that each added number alternates between odd and even.

Still stuck?Read the written solution.

Open solution