LeetCode 3437 - Permutations III

We are given a single integer n, and we need to generate all permutations of the numbers from 1 to n. However, not every permutation is valid. A permutation is considered an alternating permutation if every pair of adjacent elements has different parity.

leetcodemediumarraybacktracking

LeetCode Problem 3437

Difficulty: 🟡 Medium
Topics: Array, Backtracking

Solution

LeetCode 3437 - Permutations III

Problem Understanding

We are given a single integer n, and we need to generate all permutations of the numbers from 1 to n.

However, not every permutation is valid. A permutation is considered an alternating permutation if every pair of adjacent elements has different parity. In other words:

  • An odd number must always be followed by an even number.
  • An even number must always be followed by an odd number.
  • No two neighboring numbers can both be odd.
  • No two neighboring numbers can both be even.

The task is to return all valid alternating permutations in lexicographical order.

A permutation uses every integer from 1 through n exactly once.

For example, when n = 4, the numbers are:

1, 2, 3, 4

The permutation:

[1, 2, 3, 4]

is valid because the parities alternate:

odd -> even -> odd -> even

The permutation:

[1, 3, 2, 4]

is invalid because:

1 and 3 are both odd

The constraint is:

1 <= n <= 10

Although 10! = 3,628,800 permutations exist, generating all permutations and filtering afterward would be wasteful. Instead, we should construct only valid permutations from the start.

Important edge cases include:

  • n = 1, where the only permutation is [1].
  • n = 2, where both permutations are valid.
  • Odd values of n, where one parity appears more frequently than the other.
  • Situations where choosing a number with the wrong parity would make it impossible to complete the permutation.

Approaches

Brute Force

The most straightforward solution is to generate every permutation of the numbers 1...n.

For each permutation, we scan adjacent pairs and verify that their parities alternate. If the permutation satisfies the condition, we add it to the answer.

This approach is correct because every possible permutation is examined exactly once, and we explicitly check whether it satisfies the definition of an alternating permutation.

The problem is efficiency. There are n! permutations, and each requires O(n) time to validate. For n = 10, this becomes extremely expensive.

Optimal Approach: Backtracking with Parity Pruning

The key observation is that we do not need to generate invalid permutations at all.

While constructing a permutation, the only property that matters for the next choice is the parity of the previously chosen number.

If the last chosen number is:

  • Odd, the next number must be even.
  • Even, the next number must be odd.

Therefore, during backtracking we can immediately reject any candidate whose parity matches the previous element.

This pruning dramatically reduces the search space because many branches are never explored.

To obtain lexicographical order automatically, we try candidate numbers in increasing order. Standard depth first backtracking will then generate valid permutations in lexicographical order.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n! × n) O(n) Generate every permutation and validate afterward
Optimal O(A × n) O(n) Generate only alternating permutations, where A is the number of valid alternating permutations

Here, A denotes the number of alternating permutations produced.

Algorithm Walkthrough

  1. Create a list containing the numbers from 1 to n.
  2. Maintain a boolean array used where used[i] indicates whether number i has already been placed into the current permutation.
  3. Maintain a list current representing the partially constructed permutation.
  4. Start a depth first search.
  5. If the length of current becomes n, we have built a complete alternating permutation. Copy it into the answer list.
  6. Otherwise, iterate through numbers from 1 to n in increasing order.
  7. Skip a number if it has already been used.
  8. If current is not empty, compare the parity of the candidate number with the parity of the last element:
  • If both are odd, skip.
  • If both are even, skip.
  1. If the candidate satisfies the parity requirement:
  • Mark it as used.
  • Append it to current.
  • Continue the recursive search.
  • After recursion returns, remove it and mark it unused.
  1. Continue until all possibilities have been explored.

Because numbers are considered in ascending order at every recursive level, the generated permutations naturally appear in lexicographical order.

Why it works

At every recursive step, the algorithm maintains the invariant that the partial permutation already satisfies the alternating parity condition. Any candidate that would violate this invariant is rejected immediately. Since every valid continuation is explored and every invalid continuation is pruned, the search generates every alternating permutation exactly once. Iterating through candidates in increasing order guarantees lexicographical ordering of the final output.

Python Solution

from typing import List

class Solution:
    def permute(self, n: int) -> List[List[int]]:
        result = []
        current = []
        used = [False] * (n + 1)

        def backtrack() -> None:
            if len(current) == n:
                result.append(current[:])
                return

            for num in range(1, n + 1):
                if used[num]:
                    continue

                if current and (current[-1] % 2) == (num % 2):
                    continue

                used[num] = True
                current.append(num)

                backtrack()

                current.pop()
                used[num] = False

        backtrack()
        return result

The solution uses a classic backtracking framework.

The used array tracks which numbers have already appeared in the current permutation. This prevents duplicates and ensures each permutation contains every number exactly once.

The current list stores the partial permutation being built. Before adding a new number, the algorithm checks whether its parity differs from the parity of the last chosen number.

Whenever the length of current reaches n, a complete alternating permutation has been constructed. A copy of the permutation is appended to result.

The recursive search explores all valid choices and backtracks after each recursive call so that other possibilities can be explored.

Because numbers are tried in ascending order, the resulting permutations are automatically produced in lexicographical order.

Go Solution

func permute(n int) [][]int {
	var result [][]int
	current := make([]int, 0, n)
	used := make([]bool, n+1)

	var backtrack func()

	backtrack = func() {
		if len(current) == n {
			permutation := make([]int, n)
			copy(permutation, current)
			result = append(result, permutation)
			return
		}

		for num := 1; num <= n; num++ {
			if used[num] {
				continue
			}

			if len(current) > 0 && (current[len(current)-1]%2) == (num%2) {
				continue
			}

			used[num] = true
			current = append(current, num)

			backtrack()

			current = current[:len(current)-1]
			used[num] = false
		}
	}

	backtrack()
	return result
}

The Go implementation follows the same algorithmic structure as the Python version.

Because slices are reference types, a fresh copy of current must be created before appending it to result. Otherwise, later modifications during backtracking would affect already stored permutations.

No overflow concerns exist because all values are at most 10.

Worked Examples

Example 1

Input:

n = 4

Numbers:

1, 2, 3, 4

Initial state:

Current Available
[] {1,2,3,4}

Choose 1.

Current Available
[1] {2,3,4}

Only even numbers may follow.

Choose 2.

Current Available
[1,2] {3,4}

Only odd numbers may follow.

Choose 3.

Current Available
[1,2,3] {4}

Choose 4.

Current Available
[1,2,3,4] {}

First solution found:

[1,2,3,4]

Backtracking continues and eventually generates:

[
 [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

Search tree:

[]
├── 1
│   └── 2
└── 2
    └── 1

Generated permutations:

[[1,2],[2,1]]

Example 3

Input:

n = 3

Numbers:

1, 2, 3

Start with 1.

[1]

Only even numbers can follow.

[1,2]

Remaining number:

3

Result:

[1,2,3]

Start with 2.

[2]

Remaining odd numbers:

1, 3

Neither branch can be completed because the final remaining number would have the same parity as its neighbor.

Start with 3.

[3,2,1]

Result:

[3,2,1]

Final answer:

[[1,2,3],[3,2,1]]

Complexity Analysis

Measure Complexity Explanation
Time O(A × n) Each valid permutation of length n is generated once
Space O(n) Recursion stack, current permutation, and used array

The algorithm explores only valid alternating branches. If A denotes the number of alternating permutations, then each generated permutation requires O(n) work to construct and copy into the result. The auxiliary space consists of the recursion stack, the current permutation, and the used array, all of which require linear space.

Test Cases

from typing import List

s = Solution()

assert s.permute(1) == [[1]]  # single element

assert s.permute(2) == [
    [1, 2],
    [2, 1]
]  # smallest non-trivial case

assert s.permute(3) == [
    [1, 2, 3],
    [3, 2, 1]
]  # odd n example

assert s.permute(4) == [
    [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]
]  # provided example

result = s.permute(5)

for permutation in result:
    for i in range(len(permutation) - 1):
        assert permutation[i] % 2 != permutation[i + 1] % 2
# every adjacent pair alternates parity

assert result == sorted(result)
# lexicographical ordering

for permutation in result:
    assert sorted(permutation) == [1, 2, 3, 4, 5]
# every permutation uses all numbers exactly once

Test Summary

Test Why
n = 1 Smallest possible input
n = 2 Both permutations should be valid
n = 3 Odd sized input with limited valid answers
n = 4 Verifies sample output exactly
n = 5 parity validation Ensures alternating condition holds
n = 5 ordering check Verifies lexicographical ordering
n = 5 permutation validity Ensures all numbers appear exactly once

Edge Cases

Single Element Input

When n = 1, there are no adjacent pairs to check. A common mistake is to apply parity constraints even though no adjacency exists. The implementation handles this naturally because the first number can always be chosen, producing the single valid permutation [[1]].

Odd Number of Elements

For odd values of n, the counts of odd and even numbers differ by one. Some partial constructions may become impossible to complete even though they currently satisfy the parity rule. The backtracking algorithm handles this correctly because it explores only feasible continuations and simply fails to reach length n on dead-end branches.

Lexicographical Ordering

A common bug is generating all valid permutations and sorting afterward, or exploring numbers in arbitrary order. The implementation always considers candidates from 1 through n in ascending order at every recursion level. This guarantees that valid permutations are produced directly in lexicographical order without any extra sorting step.

Parity Violations During Construction

Many permutations become invalid as soon as two adjacent numbers share the same parity. A naive implementation might build the entire permutation before detecting the problem. The solution checks parity immediately before each insertion, pruning invalid branches early and avoiding unnecessary work.