Permutations III - Practice Coding Problems

Permutations III - Problem

Array Backtracking Medium

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.

For example, if n = 4, the integers are [1, 2, 3, 4]. A valid alternating permutation would be [1, 2, 3, 4] since adjacent pairs (1,2), (2,3), and (3,4) alternate between odd and even.

Input & Output

Example 1 — Basic Case

$ Input: n = 4

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

💡 Note: For n=4, we need permutations of [1,2,3,4] where no adjacent elements have the same parity. Valid permutations alternate between odd and even numbers.

Example 2 — Small Case

$ Input: n = 3

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

💡 Note: For n=3 with numbers [1,2,3]: [1,2,3] works (odd-even-odd), [2,1,4] is invalid (4 > n), correct result is [[1,2,3],[2,3,1]]

Example 3 — Edge Case

$ Input: n = 1

› Output: [[1]]

💡 Note: Single element always forms valid alternating permutation since there are no adjacent pairs to violate constraint

Constraints

0 ≤ n ≤ 8
Result must be sorted in lexicographical order

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=4, we work with numbers [1,2,3,4]

Process

Find arrangements where adjacent elements have different parity

Output

Return all valid alternating permutations in lexicographical order

Key Takeaway

🎯 Key Insight: Use backtracking to build permutations step-by-step, only adding numbers that maintain the alternating odd-even pattern

Asked in

G Google 35 M Microsoft 28 a Amazon 22

Brief HTML summary: The key insight is to use backtracking to generate only valid alternating permutations by checking the odd-even constraint at each step. Best approach is optimized backtracking which prunes invalid branches early. Time: O(valid permutations × n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Backtracking	O(valid permutations × n)	O(n)	Build permutations step by step, pruning invalid branches early
Generate All Permutations	O(n! × n)	O(n!)	Generate all possible permutations and filter valid ones

Optimized Backtracking — Algorithm Steps

Start with empty permutation
At each position, try numbers that alternate with the previous
If a choice violates alternating rule, skip it (prune)
Continue recursively until complete permutation is built

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Empty

Begin with empty permutation

Add Valid

Only add numbers that maintain alternating pattern

Prune Invalid

Skip branches that would violate constraint

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int result[1000][10];
int resultCount = 0;
bool used[11];
int current[10];
int currentSize = 0;
int n_global;

void backtrack() {
    if (currentSize == n_global) {
        for (int i = 0; i < n_global; i++) {
            result[resultCount][i] = current[i];
        }
        resultCount++;
        return;
    }
    
    for (int num = 1; num <= n_global; num++) {
        if (used[num]) continue;
        
        // Check alternating constraint
        if (currentSize > 0) {
            int prev = current[currentSize - 1];
            if ((prev % 2) == (num % 2)) {
                continue; // Both odd or both even
            }
        }
        
        // Valid choice
        current[currentSize] = num;
        currentSize++;
        used[num] = true;
        backtrack();
        used[num] = false;
        currentSize--;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    
    n_global = n;
    resultCount = 0;
    currentSize = 0;
    
    for (int i = 0; i <= n; i++) {
        used[i] = false;
    }
    
    if (n == 0) {
        printf("[]\n");
        return 0;
    }
    
    backtrack();
    
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        printf("[");
        for (int j = 0; j < n; j++) {
            printf("%d", result[i][j]);
            if (j < n - 1) printf(",");
        }
        printf("]");
        if (i < resultCount - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(valid permutations × n)

Only explores valid branches, but still needs to generate all valid permutations

✓ Linear Growth

Space Complexity

O(n)

Recursion depth is n, plus current permutation storage

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler