3470. Permutations IV LeetCode Solution

In this guide, you will get 3470. Permutations IV LeetCode Solution with the best time and space complexity. The solution to Permutations IV problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Permutations IV solution in C++
Permutations IV solution in Java
Permutations IV solution in Python
Additional Resources

3470. Permutations IV LeetCode Solution image

Problem Statement of Permutations IV

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, 2, 3, 4]
[1, 4, 3, 2]
[2, 1, 4, 3]
[2, 3, 4, 1]
[3, 2, 1, 4]
[3, 4, 1, 2] ← 6th permutation
[4, 1, 2, 3]
[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, 2, 3]
[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, 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

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n)

3470. Permutations IV LeetCode Solution in C++

class Solution:
  def permute(self, n: int, k: int) -> list[int]:
    ans = []
    isLookingForEven = True
    remainingNumbers = list(range(1, n + 1))

    for turn in range(n):
      remainingPermutations = (math.factorial((n - 1 - turn) // 2) *
                               math.factorial((n - turn) // 2))
      found = False
      for index, number in enumerate(remainingNumbers):
        if number % 2 != isLookingForEven and (turn > 0 or n % 2 == 1):
          continue
        if k <= remainingPermutations:
          ans.append(remainingNumbers.pop(index))
          isLookingForEven = ans[-1] % 2 == 0
          found = True
          break
        k -= remainingPermutations
      if not found:
        return []

    return ans
/* code provided by PROGIEZ */