Parity Alternating Sequences (Medium) — Practice with Code Visualizer

Given a positive integer n, your task is to generate all valid arrangements of numbers from 1 to n where consecutive elements must have different parity (one must be odd and the other must be even). In other words, no two adjacent numbers in the sequence can both be odd or both be even.

A parity-alternating sequence is an arrangement of the first n positive integers where every adjacent pair switches between odd and even values. For example, in the sequence [2, 1, 4, 3], we alternate between even (2), odd (1), even (4), and odd (3) — satisfying the parity constraint for all adjacent pairs.

Return all such valid parity-alternating sequences in lexicographically sorted order. Each sequence must be a permutation containing every integer from 1 to n exactly once.

For n = 4, we have numbers {1, 2, 3, 4} where odd = {1, 3} and even = {2, 4}. Each valid sequence alternates between odd and even numbers. For example, [1,2,3,4] alternates: 1 (odd) → 2 (even) → 3 (odd) → 4 (even). All 8 valid sequences are returned in lexicographical order.

With n = 2, we have one odd number (1) and one even number (2). Both [1,2] and [2,1] are valid since adjacent elements have different parity. The sequences are returned sorted lexicographically.

For n = 3, we have odd = {1, 3} and even = {2}. Since there's only one even number, it must be placed in the middle to satisfy the alternating constraint. Thus only [1,2,3] and [3,2,1] are valid sequences.

Return all such valid parity-alternating sequences in lexicographically sorted order. Each sequence must be a permutation containing every integer from 1 to n exactly once.

With n = 2, we have one odd number (1) and one even number (2). Both [1,2] and [2,1] are valid since adjacent elements have different parity. The sequences are returned sorted lexicographically.

Parity Alternating Sequences

Hints

Parity Alternating Sequences

Hints