Frontend School

Generate Alternating Parity Permutations

DSA
medium

Generate Alternating Parity Permutations

Medium
Recursion
Backtracking
Permutations
Arrays

Overview

In many combinatorial problems, generating sequences with specific properties is a core task. For instance, in data validation, cryptographic key generation, or even game design, we might need to produce sequences where adjacent elements follow a particular rule. This problem asks you to generate all unique permutations of a given length, where adjacent elements must strictly alternate in parity (even/odd).

What you need to do / Task

Your task is to implement a function generateAlternatingPermutations that finds all distinct permutations of a specified length k, using numbers from 1 to n (inclusive). The critical constraint is that any two adjacent numbers in a generated permutation must have different parities (one even, one odd).

Specifically, you must:

  1. Generate permutations of length k.
  2. Use numbers from the set {1, 2, ..., n}.
  3. Ensure all numbers within a single permutation are unique.
  4. Enforce the alternating parity rule: for any arr[i] and arr[i+1] in a permutation, arr[i] % 2 != arr[i+1] % 2.

Input & output

Function Signature:

function generateAlternatingPermutations(n: number, k: number): number[][];

Input:

  • n: A positive integer representing the upper bound (inclusive) for the numbers available for permutations. Numbers will be chosen from [1, n].
  • k: A positive integer representing the desired length of each permutation.

Output:

  • An array of arrays of numbers (number[][]). Each inner array represents a valid permutation satisfying all the given constraints. The order of permutations in the output array does not matter, but the order of elements within each permutation does.

Clarifications

  • If k is greater than n, it's impossible to form a permutation with k unique elements from 1 to n. In this case, return an empty array [].
  • The numbers 1 through n are available for selection. Each number can only be used once within a single permutation.
  • Parity check: A number is even if num % 2 === 0, and odd if num % 2 !== 0.

Examples

1

Example 1

Input:

n = 3, k = 2

Output:

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

Note:

For n=3, k=2:

  • [1,2]: 1 (odd), 2 (even) - valid.
  • [2,1]: 2 (even), 1 (odd) - valid.
  • [2,3]: 2 (even), 3 (odd) - valid.
  • [3,2]: 3 (odd), 2 (even) - valid. Other permutations like [1,3] are invalid because 1 and 3 are both odd. [1,1] is invalid because elements must be unique.
2

Example 2

Input:

n = 4, k = 3

Output:

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

Note:

All listed permutations satisfy the alternating parity and uniqueness constraints. For example, [1,2,3]: 1(O)-2(E) is valid, 2(E)-3(O) is valid. [1,3,2] would be invalid because 1 and 3 are both odd.

3

Example 3

Input:

n = 2, k = 3

Output:

[]

Note:

It's impossible to form a permutation of length 3 using unique numbers from 1 to 2. Therefore, an empty array is returned.

Constraints

Constraints & assumptions

  • 1 <= k <= n <= 8
  • The input n and k will always be positive integers.
  • The numbers in the permutations must be unique.

Out of scope

  • Optimizations beyond standard recursive backtracking (e.g., memoization, dynamic programming, or highly optimized bit manipulation) are not expected given the small constraints.
  • Error handling for invalid input types (e.g., non-numeric n or k).

What interviewers evaluate

  • Correctness of Recursive Logic: The ability to structure the problem as a recursive backtracking search.
  • Constraint Handling: Accurate implementation of both the unique element and alternating parity constraints.
  • Base Cases: Correctly identifying and handling the termination conditions for the recursion.
  • State Management: Efficiently managing the current permutation being built and the set of available (or used) numbers.

Loading editor...