Skip to main content
Talentd

Permutations IV - Solution & Explanation

HardArrayMathCombinatoricsEnumeration3 min read
Practice this problem

Problem Statement

Given two integers, n and k, 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 the k-th alternating permutation sorted in lexicographical order. If there are fewer than k valid alternating permutations, return an empty list.

 

Example 1:

Input: n = 4, k = 6

Output: [3,4,1,2]

Explanation:

The lexicographically-sorted alternating permutations of [1, 2, 3, 4] are:

  1. [1, 2, 3, 4]
  2. [1, 4, 3, 2]
  3. [2, 1, 4, 3]
  4. [2, 3, 4, 1]
  5. [3, 2, 1, 4]
  6. [3, 4, 1, 2] ← 6th permutation
  7. [4, 1, 2, 3]
  8. [4, 3, 2, 1]

Since k = 6, we return [3, 4, 1, 2].

Example 2:

Input: n = 3, k = 2

Output: [3,2,1]

Explanation:

The lexicographically-sorted alternating permutations of [1, 2, 3] are:

  1. [1, 2, 3]
  2. [3, 2, 1] ← 2nd permutation

Since k = 2, we return [3, 2, 1].

Example 3:

Input: n = 2, k = 3

Output: []

Explanation:

The lexicographically-sorted alternating permutations of [1, 2] are:

  1. [1, 2]
  2. [2, 1]

There are only 2 alternating permutations, but k = 3, which is out of range. Thus, we return an empty list [].

 

Constraints:

  • 1 <= n <= 100
  • 1 <= k <= 1015

Approach Overview

Problem Overview: You are given n and an index k. The task is to construct the k-th permutation of numbers 1..n that satisfies the required parity ordering constraint (odd and even placement rules). Instead of generating all permutations, you need to enumerate only the valid ones and return the k-th in lexicographic order.

Approach 1: Brute Force Permutation Enumeration (O(n! * n) time, O(n) space)

Generate every permutation of 1..n using backtracking or next_permutation. For each permutation, check whether the parity condition holds (for example, alternating odd/even positions). Maintain a counter of valid permutations and stop once the k-th valid one appears. This approach is easy to implement but extremely slow because the permutation count grows factorially. Even with pruning, the worst‑case time is O(n! * n) since each permutation must be validated.

Approach 2: Combinatorics + Lexicographic Enumeration (O(n^2) time, O(n) space)

Instead of generating permutations explicitly, count how many valid permutations start with a given prefix. Split the numbers into odd and even groups, then determine which type of number must appear at each index according to the parity rule. When constructing the permutation, iterate through the remaining candidates in sorted order. For each candidate, temporarily place it and compute how many valid permutations can be formed with the remaining numbers using combinatorial counting (factorials of remaining odd/even counts).

If the number of permutations starting with that candidate is less than k, skip the entire block and subtract that count from k. Otherwise, fix that number in the permutation and continue building the next position. This technique avoids generating unnecessary permutations and directly jumps to the correct lexicographic block. Counting relies on simple factorial math and tracking how many odd and even values remain.

This strategy combines combinatorics with controlled enumeration. The array of remaining numbers is updated after each placement, so candidate scanning adds an O(n) factor per position, giving an overall O(n^2) time complexity with O(n) auxiliary space.

Recommended for interviews: The combinatorics counting approach is what interviewers expect. Brute force shows that you understand permutation generation, but it fails scalability. The optimized solution demonstrates stronger reasoning about permutation blocks, factorial counting, and constrained enumeration across an array of remaining values.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Permutation GenerationO(n! * n)O(n)Useful only for very small n or for validating correctness during development.
Combinatorics + Lexicographic EnumerationO(n^2)O(n)Best general solution. Efficiently jumps over permutation blocks using factorial counting.

Video Solution

3470. Permutations IV (Leetcode Hard) • Programming Live with Larry • 335 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Permutations IV easy or hard?
Permutations IV is considered a hard problem because it requires recognizing that brute-force permutation generation is infeasible. The challenge is converting the problem into combinatorial counting and constructing the k-th valid permutation without enumerating all possibilities.
Permutations IV Python/Java solution
Most implementations follow the same structure: maintain remaining numbers, check parity validity for each position, and use factorial counting to skip invalid permutation blocks. The logic translates directly to Python, Java, C++, or Go with only minor syntax differences.
How to solve Permutations IV in O(n^2)?
Maintain two sets of remaining numbers (odd and even). At each index, determine which parity is allowed and iterate through candidates in sorted order. For each candidate, compute how many valid permutations remain using factorial counts of unused numbers. Skip entire blocks until the k-th permutation is located.
What is the best approach for Permutations IV?
The most efficient solution uses combinatorics with lexicographic enumeration. Instead of generating every permutation, the algorithm counts how many valid permutations can start with each candidate number and skips entire blocks. This reduces the complexity from factorial time to about O(n^2) while using O(n) extra space.
Is Permutations IV asked at Google/Amazon/Meta?
Permutation enumeration with combinatorial counting is a common interview theme at companies like Google, Amazon, and Meta. Variants involving k-th permutation, constrained permutations, or combinatorics-based skipping appear frequently in hard interview rounds.
What data structure is used in Permutations IV?
The solution mainly uses arrays or lists to track remaining numbers, along with counters for odd and even elements. Factorial values or precomputed combinatorial counts are used to determine how many permutations exist for a partial prefix.
What is the time complexity of Permutations IV?
The optimized solution runs in O(n^2) time. Each position of the permutation iterates through remaining candidates and performs constant-time combinatorial counting using factorial values. Space complexity is O(n) for tracking remaining numbers and parity counts.

Ready to solve this problem?

Practice Permutations IV with our built-in code editor and test cases.

Practice on FleetCode
Previous

Permutations III