Problem Description

Given an integer n, you need to find all alternating permutations of the first n positive integers (1, 2, 3, ..., n).

An alternating permutation is a permutation where no two adjacent elements have the same parity. In other words, odd and even numbers must alternate throughout the entire sequence - you cannot have two odd numbers next to each other, and you cannot have two even numbers next to each other.

For example, if n = 4, then [1, 2, 3, 4] is an alternating permutation because:

• 1 (odd) is followed by 2 (even)
• 2 (even) is followed by 3 (odd)
• 3 (odd) is followed by 4 (even)

However, [1, 3, 2, 4] would NOT be an alternating permutation because 1 (odd) is followed by 3 (odd), violating the alternating rule.

The task is to return all valid alternating permutations sorted in lexicographical order (dictionary order, where smaller numbers come first when comparing position by position from left to right).

The solution uses backtracking to build valid permutations. It maintains a visited array to track which numbers have been used, and at each position, it only places a number if:

1. The number hasn't been used yet
2. The number has different parity from the previous number in the permutation (or it's the first position)

The recursive function explores all valid possibilities and collects the complete alternating permutations.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves generating permutations of integers, not traversing nodes and edges in a graph structure.

Need to solve for kth smallest/largest?

• No: We need to find ALL valid alternating permutations, not just the kth smallest or largest one.

Involves Linked Lists?

• No: The problem works with permutations of integers stored in arrays/lists, not linked list data structures.

Does the problem have small constraints?

• Yes: Since we're generating all permutations of n integers, the constraints must be small. Permutations grow factorially (n!), which becomes computationally infeasible for large n. The problem asks for all valid permutations, which is only practical with small values of n.

Brute force / Backtracking?

• Yes: We need to explore all possible arrangements of numbers while ensuring the alternating parity constraint. Backtracking is perfect here because:
  • We build the permutation one position at a time
  • At each step, we try different valid numbers
  • We backtrack when we can't place a valid number or complete a permutation
  • We need to explore ALL valid possibilities, not just find one solution

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This aligns perfectly with the solution, which uses a recursive DFS function to build permutations incrementally, maintaining a visited array to track used numbers, and backtracking when necessary to explore all valid alternating permutations.

Intuition

When we need to generate all valid permutations with specific constraints, backtracking becomes our go-to strategy. Think of building the permutation as making a series of choices - at each position, we decide which number to place next.

The key insight here is that we need to enforce the alternating parity constraint dynamically as we build each permutation. We can't simply generate all permutations first and then filter them - that would be inefficient. Instead, we want to prune invalid branches early in our search tree.

Consider how we'd build an alternating permutation manually for n = 4:

• Start with position 0: We can place any number (1, 2, 3, or 4)
• Say we choose 1 (odd). For position 1, we can only place even numbers (2 or 4)
• If we choose 2, then position 2 must be odd (1 or 3, but 1 is already used, so only 3)
• Finally, position 3 must be even (only 4 remains)

This naturally suggests a recursive approach where:

1. We maintain a visited array to track which numbers we've already used
2. At each recursive call, we try placing each unused number that satisfies the parity constraint
3. The parity constraint is simple: current_number % 2 != previous_number % 2
4. We recursively build the rest of the permutation after placing each valid number
5. When we can't place any more numbers (either all positions filled or no valid options), we backtrack

The beauty of backtracking here is that it automatically handles the exploration of all possibilities while respecting our constraints. By checking the parity condition before making a recursive call, we avoid exploring branches that would lead to invalid permutations, making our solution efficient despite the exponential nature of permutations.

The lexicographical ordering comes naturally from trying numbers in ascending order (1 to n) at each position. This ensures we generate permutations in the desired sorted order without needing a separate sorting step.

Learn more about Backtracking patterns.

Solution Approach

The solution implements a depth-first search (DFS) with backtracking to generate all valid alternating permutations. Let's break down the implementation step by step:

Core Function Structure: The main function permute(n) sets up the necessary data structures and calls a helper function dfs(i) which recursively builds the permutations.

Data Structures Used:

1. ans = []: Stores all valid alternating permutations found
2. t = []: Temporary list that builds the current permutation being explored
3. vis = [False] * (n + 1): Boolean array to track which numbers (1 to n) have been used in the current permutation. We use size n+1 to directly index by number (ignoring index 0)

The DFS Function: The dfs(i) function represents filling the i-th position (0-indexed) of the permutation:

1. Base Case: When i >= n, all positions have been filled. We've found a complete valid permutation, so we add a copy of t to our answer: ans.append(t[:])

2. Recursive Case: For position i, we try each number from 1 to n:

   for j in range(1, n + 1):

3. Constraint Checking: Before placing number j at position i, we verify:

   • not vis[j]: The number hasn't been used yet
   • i == 0 or t[-1] % 2 != j % 2: Either this is the first position, OR the parity of j differs from the last number in our current permutation

   The parity check t[-1] % 2 != j % 2 ensures alternating odd/even pattern - if the last number is odd (remainder 1), the next must be even (remainder 0), and vice versa.

4. Backtracking Pattern: When a valid number j is found:

   t.append(j)        # Place the number
   vis[j] = True      # Mark as used
   dfs(i + 1)         # Recursively fill next position
   vis[j] = False     # Backtrack: mark as unused
   t.pop()            # Backtrack: remove the number

Why This Works:

• By trying numbers in order (1 to n), we naturally generate permutations in lexicographical order
• The parity constraint is enforced at each step, preventing invalid branches from being explored
• The backtracking ensures we explore all possible valid combinations systematically
• The visited array prevents number reuse within a single permutation

Time Complexity: O(n! × n) in the worst case, as we might generate up to n! permutations and each takes O(n) to build and copy.

Space Complexity: O(n) for the recursion stack and temporary arrays, not counting the output storage.

Example Walkthrough

Let's walk through the solution with n = 3 to see how the backtracking algorithm builds all alternating permutations.

Initial Setup:

• Numbers available: 1, 2, 3
• ans = [] (stores final results)
• t = [] (current permutation being built)
• vis = [False, False, False, False] (index 0 unused, indices 1-3 track if numbers 1-3 are used)

Building the Permutations:

Branch 1: Start with 1 (odd)

• Position 0: Place 1 → t = [1], vis[1] = True
• Position 1: Need even number (2 is the only even available)
  • Place 2 → t = [1, 2], vis[2] = True
  • Position 2: Need odd number (only 3 is available and odd)
    • Place 3 → t = [1, 2, 3], vis[3] = True
    • All positions filled! Add [1, 2, 3] to ans
    • Backtrack: Remove 3, vis[3] = False, t = [1, 2]
  • No more options for position 2
  • Backtrack: Remove 2, vis[2] = False, t = [1]
• No more even numbers for position 1
• Backtrack: Remove 1, vis[1] = False, t = []

Branch 2: Start with 2 (even)

• Position 0: Place 2 → t = [2], vis[2] = True
• Position 1: Need odd number (1 or 3 available)
  • Try 1 → t = [2, 1], vis[1] = True
    • Position 2: Need even number (only 2, but already used!)
    • No valid options, backtrack: Remove 1, vis[1] = False, t = [2]
  • Try 3 → t = [2, 3], vis[3] = True
    • Position 2: Need even number (only 2, but already used!)
    • No valid options, backtrack: Remove 3, vis[3] = False, t = [2]
• Backtrack: Remove 2, vis[2] = False, t = []

Branch 3: Start with 3 (odd)

• Position 0: Place 3 → t = [3], vis[3] = True
• Position 1: Need even number (2 is the only even available)
  • Place 2 → t = [3, 2], vis[2] = True
  • Position 2: Need odd number (only 1 is available and odd)
    • Place 1 → t = [3, 2, 1], vis[1] = True
    • All positions filled! Add [3, 2, 1] to ans
    • Backtrack: Remove 1, vis[1] = False, t = [3, 2]
  • No more options for position 2
  • Backtrack: Remove 2, vis[2] = False, t = [3]
• No more even numbers for position 1
• Backtrack: Remove 3, vis[3] = False, t = []

Final Result: ans = [[1, 2, 3], [3, 2, 1]]

Notice how:

• Starting with 2 (even) led to dead ends because we only have one even number when n=3
• The algorithm automatically prunes invalid branches by checking parity before recursing
• Lexicographical order is maintained by trying numbers 1, 2, 3 in that order at each position

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × n!)

The algorithm uses backtracking to generate permutations with a specific constraint (alternating parity). In the worst case:

• The DFS explores a tree where each level represents choosing one number from 1 to n
• At each position, we iterate through all n numbers to find valid candidates
• The number of valid permutations can be up to n! in certain cases
• For each valid permutation found, we create a copy of the current path t[:] which takes O(n) time
• Therefore, the total time complexity is O(n × n!) where the n factor comes from both the iteration at each level and the copying operation

Space Complexity: O(n)

The space complexity consists of:

• The recursion stack depth which can go up to n levels: O(n)
• The temporary array t storing the current permutation path: O(n)
• The visited array vis of size n+1: O(n)
• The output array ans stores all valid permutations, but this is typically not counted as auxiliary space since it's the required output

The dominant space usage comes from the recursion stack and auxiliary arrays, giving us O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Create a Copy When Adding to Results

The Pitfall: A very common mistake is adding the reference to the current permutation list directly to the results:

if position >= n:
    result.append(current_permutation)  # WRONG! This adds a reference

This causes all elements in result to point to the same list object. Since backtracking modifies current_permutation in place, all stored "permutations" will end up being empty lists after the algorithm completes.

The Solution: Always create a copy when storing the permutation:

if position >= n:
    result.append(current_permutation[:])  # Correct: creates a new list
    # Alternative: result.append(list(current_permutation))

2. Incorrect Parity Check Logic

The Pitfall: Writing the parity check incorrectly, such as:

# WRONG: This checks if both are odd or both are even
if not used[number] and (position == 0 or current_permutation[-1] % 2 == number % 2):

Or using bitwise operations incorrectly:

# WRONG: & has lower precedence than !=
if not used[number] and (position == 0 or current_permutation[-1] & 1 != number & 1):

The Solution: Ensure the parity check verifies that adjacent numbers have different remainders when divided by 2:

# Correct: ensures different parity
if not used[number] and (position == 0 or current_permutation[-1] % 2 != number % 2):
# Alternative with proper parentheses for bitwise:
if not used[number] and (position == 0 or (current_permutation[-1] & 1) != (number & 1)):

3. Off-by-One Error in the Visited Array

The Pitfall: Creating a visited array of size n instead of n+1:

used = [False] * n  # WRONG: can't directly index by number

This leads to index errors when trying to access used[n] or requires adjusting indices throughout the code (using used[number-1]), which is error-prone.

The Solution: Create the array with size n+1 to allow direct indexing by number:

used = [False] * (n + 1)  # Correct: index 0 unused, indices 1 to n for numbers

4. Not Properly Resetting State During Backtracking

The Pitfall: Forgetting to reset the used array or remove the number from the current permutation:

current_permutation.append(number)
used[number] = True
backtrack(position + 1)
# WRONG: Missing backtracking steps

This causes numbers to remain marked as used even after backtracking, preventing valid permutations from being found.

The Solution: Always include both backtracking operations after the recursive call:

current_permutation.append(number)
used[number] = True
backtrack(position + 1)
used[number] = False  # Reset the used flag
current_permutation.pop()  # Remove the number

5. Inefficient Base Case Check

The Pitfall: Using len(current_permutation) == n instead of position >= n:

if len(current_permutation) == n:  # Works but less efficient
    result.append(current_permutation[:])

While this works, it requires computing the length at each recursive call, which is O(n) in some implementations.

The Solution: Use the position parameter which is already being tracked:

if position >= n:  # More efficient
    result.append(current_permutation[:])