3437. Permutations III 🔒

Problem Description

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The problem revolves around generating all permutations of the first n positive integers, with the added constraint that adjacent numbers must alternate in parity (odd/even). An effective approach to tackle this is through backtracking, which allows us to explore all potential permutations while adhering to the rules.

Solution Approach

Backtracking Design: We define a function dfs(i) to fill the i-th position in a permutation. The index i starts from 0 up to n-1.
Base Condition: If i equals n, it signifies that all positions in the permutation have been correctly filled. At this point, the current permutation is added to the list of valid permutations (ans).
Recursive Exploration: We then consider each integer j from 1 to n. A number j can be placed in the current position if:
- j has not been used yet (vis[j] is False).
- j is of different parity compared to the last inserted number in the permutation.
Backtracking Step: If the conditions are met, we include j and proceed to fill the next position by making a recursive call to dfs(i + 1). After exploring that path, we backtrack by marking j as not used and removing it from the current permutation (t).

Overall, this approach efficiently generates all possible alternating permutations using depth-first search, ensuring the permutations are produced in lexicographical order. This is facilitated by iterating sequentially from 1 to n during exploration.

Learn more about Backtracking patterns.

Solution Approach

The solution utilizes a backtracking approach to generate all valid alternating permutations. Here's how the implementation works:

Data Structures:
- t: A list that temporarily stores the current partial permutation being constructed.
- vis: A list of boolean values where vis[j] indicates whether the number j has been used in the current permutation.
Recursive Function dfs(i):
- Base Case: If i is greater than or equal to n, the permutation in t is complete, and it is added to the results ans.
- Recursive Case: Iterate over each number j from 1 to n.
  - Constraints:
    - Check if j is available (i.e., it hasn't been used, so vis[j] is False).
    - Ensure j can be placed next to the last number in t by checking their parity: t[-1] % 2 != j % 2.
  - Action:
    - Append j to t, marking j as used (vis[j] = True).
    - Call dfs(i + 1) to fill the next position.
    - After returning from recursion, backtrack by removing j from t and marking it as unused (vis[j] = False).
Initialization and Invocation:
- Start with an empty permutation (t = []) and all numbers available (vis = [False] * (n + 1)).
- Call dfs(0) to begin filling permutations from the first position.
Return: The list ans contains all lexicographically sorted alternating permutations.

This step-by-step permutation building provides a robust method to explore all valid combinations while adhering to the alternating parity rule, efficiently traversing the decision tree using backtracking.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example where n = 3. We want to find all alternating permutations of the integers 1, 2, 3.

Initialization:

Start with an empty permutation list t = [].
Initialize a vis list to keep track of used numbers, vis = [False, False, False, False] (since n = 3, the length is n + 1).

Process using Backtracking:

First Level (i = 0):
- We begin at the 0th position of the permutation.
- Consider placing each integer j (1 to 3):
  - For j = 1:
    - Not used (vis[1] = False).
    - Place 1 into t, so t = [1], mark 1 as used, vis = [False, True, False, False].
    - Recursively call dfs(1) to fill the next position.
Second Level (i = 1):
- We are at the 1st position, and t = [1].
- Consider each j:
  - For j = 1: Already used, skip.
  - For j = 2:
    - Not used (vis[2] = False).
    - Check parity: Previous number is 1 (odd), 2 is even, satisfies condition.
    - Place 2 into t, t = [1, 2], mark 2 as used, vis = [False, True, True, False].
    - Recursively call dfs(2) to fill the final position.
Third Level (i = 2):
- We are at the 2nd position, and t = [1, 2].
- Consider each j:
  - For j = 1: Already used, skip.
  - For j = 2: Already used, skip.
  - For j = 3:
    - Not used (vis[3] = False).
    - Check parity: Previous number is 2 (even), 3 is odd, satisfies condition.
    - Place 3 into t, t = [1, 2, 3], mark 3 as used, vis = [False, True, True, True].
    - Reached base condition i = 3 (all positions filled), add [1, 2, 3] to ans.
    - Backtrack: Remove 3, reset vis[3] = False, return to previous level i = 2.
Backtracking:
- At i = 2 with t = [1, 2], try next potential values (j) once 3 is backtracked.
- Continue exploring by changing the first choice (t = [1]) at i = 1, and eventually restarting from different j values at i = 0.

Repeat these steps to explore all valid alternating permutations ans = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].

Solution Implementation

1from typing import List
2
3class Solution:
4    def permute(self, n: int) -> List[List[int]]:
5        def dfs(index: int) -> None:
6            # Base case: if the current index reaches n, a permutation is complete
7            if index >= n:
8                ans.append(current_permutation[:])  # Append a copy of the current permutation
9                return
10          
11            # Iterate over possible values from 1 to n
12            for num in range(1, n + 1):
13                # Check if the number is not visited and follows the alternating even-odd property
14                if not visited[num] and (index == 0 or current_permutation[-1] % 2 != num % 2):
15                    current_permutation.append(num)  # Add the number to the current permutation
16                    visited[num] = True  # Mark the number as visited
17                    dfs(index + 1)  # Recurse to the next position
18                    visited[num] = False  # Unmark the number to backtrack
19                    current_permutation.pop()  # Remove the last number to try another option
20
21        ans = []  # List to store all valid permutations
22        current_permutation = []  # Current permutation being constructed
23        visited = [False] * (n + 1)  # Visited array to keep track of used numbers
24
25        # Start the depth-first search from index 0
26        dfs(0)
27
28        return ans
29

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    // List to hold all permutations
6    private List<int[]> result = new ArrayList<>();
7    // Boolean array to track visited numbers
8    private boolean[] visited;
9    // Array to store the current permutation
10    private int[] currentPermutation;
11    // Variable to store the length of permutations
12    private int length;
13
14    /**
15     * Method to generate all permutations of numbers 1 to n such that no two
16     * adjacent numbers have the same parity.
17     *
18     * @param n the upper bound of numbers (1 to n)
19     * @return a 2D array of all valid permutations
20     */
21    public int[][] permute(int n) {
22        this.length = n; // Set the length of permutation
23        currentPermutation = new int[n]; // Initialize the permutation array
24        visited = new boolean[n + 1]; // Initialize visited array
25        depthFirstSearch(0); // Start DFS to generate permutations
26        return result.toArray(new int[0][]); // Convert result list to 2D array
27    }
28
29    /**
30     * Helper method to perform depth-first search for generating permutations.
31     *
32     * @param index the current depth in the permutation array
33     */
34    private void depthFirstSearch(int index) {
35        if (index >= length) {
36            result.add(currentPermutation.clone()); // Add current permutation to result
37            return;
38        }
39
40        // Try placing each number from 1 to n
41        for (int number = 1; number <= length; number++) {
42            // Check if the number is not visited and has a different parity compared to the previous
43            if (!visited[number] && (index == 0 || currentPermutation[index - 1] % 2 != number % 2)) {
44                visited[number] = true; // Mark the number as visited
45                currentPermutation[index] = number; // Place the number in current position
46                depthFirstSearch(index + 1); // Recur for the next position
47                visited[number] = false; // Unmark the number for further permutations
48            }
49        }
50    }
51}
52

1class Solution {
2public:
3    std::vector<std::vector<int>> permute(int n) {
4        std::vector<std::vector<int>> ans;
5        std::vector<bool> visited(n + 1, false);  // Index-based from 1 to n
6        std::vector<int> currentPermutation;
7
8        // Depth-First Search function for generating permutations
9        std::function<void(int)> dfs = [&](int i) {
10            // If the current index is equal to n, we have a complete permutation
11            if (i == n) {
12                ans.push_back(currentPermutation);  // Add current permutation to results
13                return;  // Backtrack
14            }
15          
16            // Attempt to place numbers 1 through n in the current position
17            for (int j = 1; j <= n; ++j) {
18                // Check if the number is not visited and satisfies the even-odd rule
19                if (!visited[j] && (i == 0 || currentPermutation[i - 1] % 2 != j % 2)) {
20                    visited[j] = true;  // Mark the number as used
21                    currentPermutation.push_back(j);  // Add number to current permutation
22                    dfs(i + 1);  // Recurse for the next position
23                    currentPermutation.pop_back();  // Remove the number for backtracking
24                    visited[j] = false;  // Unmark the number
25                }
26            }
27        };
28      
29        dfs(0);  // Start the DFS with index 0
30        return ans;  // Return the list of permutations
31    }
32};
33

1function permute(n: number): number[][] {
2    // Array to store the resulting permutations
3    const ans: number[][] = [];
4  
5    // Array to track the numbers that have been used in the current permutation
6    const vis: boolean[] = Array(n + 1).fill(false);
7  
8    // Temporary array to build each permutation
9    const t: number[] = Array(n).fill(0);
10  
11    // Helper function to perform depth-first search to generate permutations
12    const dfs = (i: number) => {
13        // Base case: if the current index equals n, a complete permutation is formed
14        if (i >= n) {
15            ans.push([...t]);  // Store a copy of the current permutation
16            return;
17        }
18      
19        // Try placing each number from 1 to n in the current position
20        for (let j = 1; j <= n; ++j) {
21            // Ensure the number j is not already used and that adjacent numbers in the permutation differ in odd/even attribute
22            if (!vis[j] && (i === 0 || t[i - 1] % 2 !== j % 2)) {
23                vis[j] = true;  // Mark the number j as used
24                t[i] = j;       // Place the number j in the current position
25                dfs(i + 1);     // Move to the next position
26                vis[j] = false; // Unmark the number j, backtracking
27            }
28        }
29    };
30
31    // Start the recursive permutation generation
32    dfs(0);
33    return ans;  // Return the list of all valid permutations
34}
35

Time and Space Complexity

The time complexity of the code is O(n * n!) because the algorithm generates all permutations of numbers from 1 to n while considering additional constraints. During the recursive depth-first search, there are n! permutations, and for each permutation, operations proportional to n are carried out.

The space complexity of the code is O(n). This is primarily due to the space used by the recursion stack, which can go as deep as n, and additional space to store the current permutation t, which can also have at most n elements.

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

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don't know

3437. Permutations III 🔒

Problem Description

Intuition

Solution Approach

Solution Approach

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings