LeetCode Problem 3470

Difficulty: 🔴 Hard
Topics: Array, Math, Combinatorics, Enumeration

Solution

LeetCode 3470 - Permutations IV

Problem Understanding

We are given two integers, n and k.

We must consider all permutations of the numbers 1 through n that satisfy an alternating parity condition. In a valid permutation, every pair of adjacent elements must have different parity. In other words:

• Odd must be followed by even.
• Even must be followed by odd.

No two neighboring numbers may both be odd or both be even.

Among all valid alternating permutations, we sort them in normal lexicographical order and return the k-th one. If fewer than k valid alternating permutations exist, we return an empty list.

The value of n can be as large as 100, which immediately rules out generating permutations explicitly because 100! is astronomically large. The value of k is at most 10^15, which is much smaller than the number of possible alternating permutations. This suggests that we should construct the answer directly using combinatorial counting rather than enumerating all valid permutations.

Several edge cases are important:

• n = 1, where the single permutation is always valid.
• Situations where k exceeds the total number of alternating permutations.
• Odd values of n, where there is one more odd number than even numbers.
• Even values of n, where either parity may start the permutation.
• Very large counts, which can exceed 10^15, requiring count capping to avoid overflow.

Approaches

Brute Force

A brute force solution would generate every permutation of 1..n, check whether adjacent elements alternate parity, keep the valid ones, sort them lexicographically, and then return the k-th valid permutation.

This approach is correct because it explicitly examines every possible permutation and filters out invalid ones. However, it is completely infeasible. Even for n = 15, there are already more than a trillion permutations. Since n can reach 100, brute force is impossible.

Key Insight

The crucial observation is that once the parity pattern is fixed, counting the number of valid completions becomes easy.

Suppose we know:

• How many odd numbers remain.
• How many even numbers remain.
• Which parity the next position must have.

The parity sequence of all remaining positions is then completely determined. For example, if the next position must be odd, the remaining parity pattern is:

odd, even, odd, even, ...

The only freedom left is choosing which odd numbers occupy the odd slots and which even numbers occupy the even slots.

If there are:

• o remaining odd numbers
• e remaining even numbers

then the number of assignments is simply:

o! × e!

provided that the remaining parity pattern requires exactly o odd slots and e even slots. Otherwise the count is zero.

This allows us to build the answer lexicographically. At each position we try candidates in ascending order, count how many valid permutations begin with that candidate, and skip entire blocks until we locate the block containing the desired k-th permutation.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n!)	Generates all permutations
Optimal	O(n²)	O(n)	Uses combinatorial counting and lexicographic construction

Algorithm Walkthrough

1. Compute factorials up to 50 because there can be at most 50 odd numbers and 50 even numbers when n ≤ 100.
2. Cap all factorial values at a large constant such as 10^18. Since k ≤ 10^15, we never need exact counts beyond that threshold.
3. Maintain the set of unused numbers.
4. Define a counting function:

• Input: remaining odd count o, remaining even count e, and the parity required for the next position.
• Let m = o + e.
• Determine how many odd and even slots the remaining parity pattern requires.
• If the counts do not match those requirements, return 0.
• Otherwise return o! × e!.

5. Build the permutation one position at a time.
6. For the current position, iterate through all unused numbers in ascending order.
7. A candidate is valid only if:

• It is the first position, or
• Its parity differs from the previously chosen number.

8. Temporarily choose the candidate and compute how many valid completions exist after it.
9. If that count is smaller than k, skip all those permutations by subtracting the count from k.
10. Otherwise, the desired permutation lies in this block. Permanently choose the candidate and move to the next position.
11. If no candidate can accommodate the current value of k, then fewer than k valid permutations exist and we return an empty list.
12. Continue until all positions are filled.

Why it works

At every step, lexicographical order groups permutations into contiguous blocks sharing the same prefix. The counting function tells us exactly how many valid permutations belong to each block. By skipping entire blocks whose size is smaller than k, we effectively perform combinatorial ranking and unranking. Because every valid permutation belongs to exactly one block and the blocks are processed in lexicographical order, the algorithm always selects the correct k-th alternating permutation.

Python Solution

from typing import List

class Solution:
    def permute(self, n: int, k: int) -> List[int]:
        INF = 10**18

        fact = [1] * 51
        for i in range(1, 51):
            fact[i] = min(INF, fact[i - 1] * i)

        def mul_cap(a: int, b: int) -> int:
            if a == 0 or b == 0:
                return 0
            if a > INF // b:
                return INF
            return min(INF, a * b)

        def count_remaining(odd_cnt: int, even_cnt: int, next_parity: int) -> int:
            length = odd_cnt + even_cnt

            if length == 0:
                return 1

            if next_parity == 1:
                required_odd = (length + 1) // 2
                required_even = length // 2
            else:
                required_even = (length + 1) // 2
                required_odd = length // 2

            if odd_cnt != required_odd or even_cnt != required_even:
                return 0

            return mul_cap(fact[odd_cnt], fact[even_cnt])

        unused = list(range(1, n + 1))

        odd_total = (n + 1) // 2
        even_total = n // 2

        answer = []
        prev_parity = -1

        for pos in range(n):
            found = False

            for x in unused:
                parity = x & 1

                if pos > 0 and parity == prev_parity:
                    continue

                odd_left = odd_total - (1 if parity == 1 else 0)
                even_left = even_total - (1 if parity == 0 else 0)

                if pos == n - 1:
                    ways = 1
                else:
                    ways = count_remaining(
                        odd_left,
                        even_left,
                        1 - parity
                    )

                if ways < k:
                    k -= ways
                    continue

                answer.append(x)
                unused.remove(x)

                odd_total = odd_left
                even_total = even_left
                prev_parity = parity

                found = True
                break

            if not found:
                return []

        return answer

The implementation begins by precomputing factorial values for all possible odd and even counts. Since only counts up to 50 are needed, the table is very small.

The helper function count_remaining determines how many alternating completions exist once the next required parity is known. The parity pattern uniquely determines how many odd and even slots remain. If the available counts do not match those requirements, no completion exists.

The main loop constructs the permutation from left to right. For every unused candidate in lexicographical order, it computes the size of the corresponding block of valid permutations. If the block is smaller than k, the entire block is skipped. Otherwise, that candidate must belong to the desired permutation and is permanently selected.

Go Solution

func permute(n int, k int64) []int {
	const INF int64 = 1_000_000_000_000_000_000

	fact := make([]int64, 51)
	fact[0] = 1
	for i := 1; i <= 50; i++ {
		if fact[i-1] > INF/int64(i) {
			fact[i] = INF
		} else {
			v := fact[i-1] * int64(i)
			if v > INF {
				v = INF
			}
			fact[i] = v
		}
	}

	mulCap := func(a, b int64) int64 {
		if a == 0 || b == 0 {
			return 0
		}
		if a > INF/b {
			return INF
		}
		res := a * b
		if res > INF {
			return INF
		}
		return res
	}

	var countRemaining func(int, int, int) int64
	countRemaining = func(oddCnt, evenCnt, nextParity int) int64 {
		length := oddCnt + evenCnt

		if length == 0 {
			return 1
		}

		var requiredOdd, requiredEven int

		if nextParity == 1 {
			requiredOdd = (length + 1) / 2
			requiredEven = length / 2
		} else {
			requiredEven = (length + 1) / 2
			requiredOdd = length / 2
		}

		if oddCnt != requiredOdd || evenCnt != requiredEven {
			return 0
		}

		return mulCap(fact[oddCnt], fact[evenCnt])
	}

	unused := make([]int, n)
	for i := 0; i < n; i++ {
		unused[i] = i + 1
	}

	oddTotal := (n + 1) / 2
	evenTotal := n / 2

	ans := make([]int, 0, n)
	prevParity := -1

	for pos := 0; pos < n; pos++ {
		found := false

		for idx, x := range unused {
			parity := x & 1

			if pos > 0 && parity == prevParity {
				continue
			}

			oddLeft := oddTotal
			evenLeft := evenTotal

			if parity == 1 {
				oddLeft--
			} else {
				evenLeft--
			}

			var ways int64
			if pos == n-1 {
				ways = 1
			} else {
				ways = countRemaining(
					oddLeft,
					evenLeft,
					1-parity,
				)
			}

			if ways < k {
				k -= ways
				continue
			}

			ans = append(ans, x)

			unused = append(unused[:idx], unused[idx+1:]...)

			oddTotal = oddLeft
			evenTotal = evenLeft
			prevParity = parity

			found = true
			break
		}

		if !found {
			return []int{}
		}
	}

	return ans
}

The Go version follows exactly the same logic. The main implementation difference is that slice manipulation is used to remove a selected element from the list of unused numbers. All combinatorial counts are stored in int64, and values are capped at 10^18 to avoid overflow.

Worked Examples

Example 1

Input

n = 4
k = 6

Initial state:

Variable	Value
oddTotal	2
evenTotal	2
unused	[1,2,3,4]
k	6

Position 0:

Candidate	Completions
1	2
2	2
3	2

The first block contributes 2 permutations.

k = 6 - 2 = 4

The second block contributes another 2.

k = 4 - 2 = 2

The third block contributes 2 permutations, which contains the desired answer.

Choose 3.

Position 1:

unused = [1,2,4]
required parity = even
k = 2

Candidate	Completions
2	1
4	1

Skip candidate 2.

k = 1

Choose 4.

Position 2:

unused = [1,2]
required parity = odd

Choose 1.

Position 3:

unused = [2]

Choose 2.

Result:

[3,4,1,2]

Example 2

Input

n = 3
k = 2

Position 0:

Candidate	Completions
1	1
2	0
3	1

Skip the first block.

k = 1

Choose 3.

The remaining forced choices are:

3 -> 2 -> 1

Result:

[3,2,1]

Example 3

Input

n = 2
k = 3

Valid permutations:

[1,2]
[2,1]

Only two valid alternating permutations exist.

The algorithm skips both available blocks and eventually finds no candidate capable of containing the third permutation.

Result:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each position scans the remaining unused numbers
Space	O(n)	Stores unused numbers, factorial table, and answer

The factorial table is constant sized because only values up to 50! are needed. The dominant cost comes from iterating through the remaining candidates at each position, giving a quadratic running time. Since n ≤ 100, this is easily fast enough.

Test Cases

s = Solution()

assert s.permute(4, 6) == [3, 4, 1, 2]      # example 1
assert s.permute(3, 2) == [3, 2, 1]         # example 2
assert s.permute(2, 3) == []                # example 3

assert s.permute(1, 1) == [1]               # smallest input
assert s.permute(1, 2) == []                # k out of range

assert s.permute(2, 1) == [1, 2]            # first valid permutation
assert s.permute(2, 2) == [2, 1]            # last valid permutation

assert s.permute(3, 1) == [1, 2, 3]         # first lexicographic answer
assert s.permute(3, 3) == []                # only two valid permutations

assert len(s.permute(10, 1)) == 10          # larger n
assert s.permute(4, 9) == []                # only 8 valid permutations

result = s.permute(100, 1)                  # maximum n
assert len(result) == 100

Test Summary

Test	Why
(4, 6)	Official example
(3, 2)	Official example
(2, 3)	Out of range example
(1, 1)	Minimum valid input
(1, 2)	Minimum out of range case
(2, 1)	First lexicographic permutation
(2, 2)	Last valid permutation
(3, 1)	Odd n, first answer
(3, 3)	Odd n, invalid k
(10, 1)	Larger balanced parity counts
(4, 9)	k larger than total count
(100, 1)	Maximum constraint

Edge Cases

k Exceeds the Number of Valid Alternating Permutations

This is the most important corner case. A naive implementation might assume that the requested permutation always exists. During construction, the algorithm repeatedly subtracts entire lexicographic blocks. If every block is exhausted and no valid candidate remains, the function returns an empty list. This correctly handles all out of range values of k.

Odd Number of Elements

When n is odd, there is one more odd number than even numbers. Not every starting parity is feasible. For example, with n = 3, a permutation starting with an even number cannot be completed because there are not enough even numbers to maintain alternation. The counting function detects this automatically by verifying that the available odd and even counts exactly match the parity pattern requirements.

Very Large Combinatorial Counts

Factorials grow extremely quickly. Even 50! is far larger than any built in integer type used in many languages. Since the problem only needs to compare counts against k ≤ 10^15, the implementation caps all counts at 10^18. This preserves all ordering decisions while preventing overflow.

Single Remaining Position

When the permutation has only one position left, there is exactly one completion if the current prefix is valid. The implementation explicitly treats the zero length remainder as a count of 1, ensuring the final selection step behaves correctly.