Step by Step logic of how I got my Mathematical O(n^2) approach.
First observation, there are limited ways a permutation can "alternate" based on if n is even or odd.Once  a permutation starts with an odd, it is forced to alt



### First observation, there are limited ways a permutation can "alternate" based on if n is even or odd.

Once  a permutation starts with an odd, it is forced to alternate odd, even, odd, even for the rest of the perm and vice versa with even. 

For any number $n$, 
    - **if n is even then there are an equal number of evens and odds from 1-n**
    - **if n is odd then there is 1 more odd than even from 1-n**
ex: {1, 2, 3} - two odds, one even. {1, 2, 3, 4} two odds, two evens.

Since the even and odds are unbalanced in the odd case, the only way to alternate is by "sandwiching the evens like {odd even odd}, so odds must go first.

Since the evens and odds are balanced in the even case, either even or odd can go first.

Thus:

### If *n* is odd the permutation must follow the pattern:
- $$ \{odd, even, odd, even, \dots, odd\}$$
### If *n* is even the permutation can be in one of two valid patterns:
- $$ \{odd, even, odd, even, odd, \dots, even\}$$
- $$ \{even, odd, even, odd, even, \dots, odd\}$$

Since the odd n only has 1 possible permutation pattern, should observe this "simpler" case first and hope doing so gives insight into how to go about the even case.

---

# The Odd Case:
#### From 1-n there are:
$\frac{n+1}{2}$ odd numbers.
$\frac{n-1}{2}$ even numbers.


Since the pattern cannot change and only whatever odd or even number go into each place in the permutation pattern can vary, Each valid permutation corresponds to  **permutation of the odd numbers and a permutation of the even numbers**. Thus, the total number of valid permutations is:
$$(\left(\frac{n-1}{2}\right)! \times \left(\frac{n+1}{2}\right)!)$$
This can act as a base, where if $k$ exceeds this value we return an empty list.

## Building the Permutation

#### Choosing the First few numbers

The first number must be an odd number due to the pattern constraint.
Since whatever odd number we choose, we still have the same amount of remaining evens and odds left to use after it, the number of permutations that start with any given number should be the same. 

i.e. for n = 7, if m perms exist starting with  a 1, then m perms also exist starting with a 3, 5, and a 7.

Since we've chosen an odd number, there are now: 
$\frac{n-1}{2}$ odd numbers.
$\frac{n-1}{2}$ even numbers.

The number of valid permutations for each choice of the first number = number of valid permutations of the remaining numbers after choice which is:
$$\left(\frac{n-1}{2}\right)! \times \left(\frac{n-1}{2}\right)!$$

let $$m = \left(\frac{n-1}{2}\right)! \times \left(\frac{n-1}{2}\right)!$$
Since we want to priortize getting earlier numbers first at all costs when lexicographically minimizing/ordering, can group each starting number in increasing order and define their range based on this value.

Thus the first number can be found by determining which of the ranges below k falls into:

- $1$ first if $k \in [1, m]$
- $3$ first if $k \in [1 + m, 2 \times m]$
- $5$ first if $k \in [1 + 2 \times m, 3 \times m]$
- ....

More generally, the first number is the $s$th odd number $(2s-1)$ if:
$k \in \left[ 1 + (s-1) \times m, s \times m \right]$


Once the first number is selected, we can look at selecting the second as a sort of similar smaller subproblem for evens.

We only need to look at the space of smaller subperms that start with the selected, start. A space already known to have a size = $m$.

the lowest perm in the space has $k = 1 + (s-1) \times m$ while highest has $k = s \times m$. Can reduce this range to a 1 to m re-indexing for 1 represeenting the lowest possible sub-palindrome and m representing the highest. This can simply be done by taking $k= k \mod m$ with the exception of $k \equiv 0 \mod m$ mapping to k = m instead, as want the highest $(s-1)\times m$ to map to highest k instead of 0.

as choosing one even for the second group leaves us with:
$\frac{n-1}{2}$ odd numbers.
$\frac{n-3}{2}$ even numbers.

the number of subpermutations/suffixs after the second choice $m_2 = \left(\frac{n-3}{2}\right)! \times \left(\frac{n-1}{2}\right)!$

using the same logic as 1st choice, the second choice ranges  are as follows:
    - 2 if $k \in [1, m_2]$
    - 4 if $k \in [1 + m_2, 2 \times m_2]$
    ...

with the generalized $s$th even number $(2s)$:
$k \in \left[ 1 + (s-1) \times m_2, s \times m_2 \right]$


Since the second choice process seemed very similar to the first, this approach seems ready to be generalized to the ith position/choice, as such a generalization will allow all positions and thus the whole permutation to be calculated. 

#### Generalizing for Position $i$ or selecting the $ith$ number.

After selecting the first $i$ numbers, the number of valid permutations remaining depends on whether $i$ is odd or even:

If $i$ is odd:
$[\left(\frac{n-i}{2} \right)!]^2$


If $i$ is even:
$\left(\frac{n-i-1}{2} \right)! \times \left(\frac{n-i+1}{2} \right)!$

Note: This can be combined into the following expression for both polarities:
$$\lfloor \frac{n-i}{2} \rfloor! \times \lceil \frac{n-i}{2} \rceil!$$

So only, need to repeat the process of k ranges and modular reduction in previous steps using $m_i = \lfloor \frac{n-i}{2} \rfloor! \times \lceil \frac{n-i}{2} \rceil!$

There is one difference for the general case, however:
as these are no longer the first choices for each polarity, the $sth$ odd or even available in the permutation is no longer simply $2s-1$ or $2s$, as some of the odds and evens have been already chosen.

For example, if we already chose 1 earlier, than 3 should instead "act" like 1, replacing it as the lowest odd number for later permutations to choose.

Thus, instead of calculating the value of the $s$th odd or even for any range using those formulas, can maintain a sorted list of all the available odd and even numbers, indexing into the $s$th one and removing it from the list for future subpermutations whenever we need to choose the $s$th smallest even or odd.


This covers all the steps we would need to calculate the odd case, thus the odd case is solved.

---



# The Even Case: 
For even $n$, we have:
- $$ \{odd, even, odd, even, odd, \dots, even\}$$ 
- $$ \{even, odd, even, odd, even, \dots, odd\}$$

Both have $\frac{n}{2}$ in each polarity group, giving the polariity groups $\frac{n}{2}!$  perms respectively or 
$(\frac{n}{2}!)^2$ combined.
            Since can choose either ordering of 2 for each relative polarity perm pair, total number of perms = $2 \times (\frac{n}{2}!)^2$ 
Thus, if $k > 2 \times (\frac{n}{2}!)^2$, return empty

Since count of evens = count of odds, starting with any odd should result in the same number of perms starting with it as both any odd or any even.

This means every starting value should have the same number of perms, and diviiding perms equally amongst n start values gives $\frac{2 \times (\frac{n}{2}!)^2}{n}$ perms each. Factoring out an $\frac{n}{2}$ from one of the factorial terms and multiplying it by the 2 outside gives an n to cancel the denominator, making the expression equivalent to $(\frac{n}{2} - 1)! \times (\frac{n}{2})$! perms.

            
 let $t = (\frac{n}{2} - 1)! \times (\frac{n}{2})$
since lexicographic prioritizes the first overe all first, this divides even cases into ranges

start with 1 for k in range [1, t]start with 2 for k in range [1 + t, 2*t]
for general case start with m for k in range [1 + (m-1)*t, m*t]

after selecting starting num, split into cases based on if starting num is even or odd
            
#### If choose even first $$ \{even, odd, even, odd, even, \dots, odd\}$$

observe: suffix after even = $$\{odd, even, odd, even, \dots, odd\}$$

This suffix is identical to the odd case, so can use oddCase(n-1, (k % t) (if k % t == 0, then use t instead))
            
#### if choose odd first $$ \{odd, even, odd, even, odd, \dots, even\}$$ 
observe: suffix after first = $$\{even, odd, even, odd, \dots, even\}$$ 

this suffix is precisely the **polarity inverse of the odd case** (meaning every odd in this suffix is an even in the odd n permutation and vice versa). 

Since only the relative ordering of the numbers matters for logic in the odd case, not any properties of the odd or evens selected for the permutation, can re-use the oddcase logic for this case, also taking the mod like in choose even first case, but further swapping all evens and odd references within the odd case to ensure the opposite pattern.



---

Both even and odd cases have been resolved, meaning all cases have been solved now (the code for which is implemented below)

## Time complexity: 
Since the even case preprocessing just does $O(1)$ computations and an $O(n)$ operation copying in the odd suffix, the it's time complexity is dominated by the odd case part (and the odd case is obviously aswell)

The odd case loops with n iterations, each iteration doing some $O(1)$ math operations, including the "oddChosenM" method as well as the stadard language ops. Thus of each itr is dominated by the removeFromPolarityGroup $O(n)$ operation, as it has to make a whole new array of evens or odds after the current 1 is selected. 

This makes the odd case $O(n^2)$

This method could likely be reduced to $O(log(n))$ or $O(1)$ using a better data structure/strategy, thus reducing overall time complexity to $O(nlogn)$ or $O(n)$. This is likely somewhat trivial to implement, but vastly unnecessary in practice given the constraints and nature of the problem.


Thus the time complexity is $O(n^2)$


## Space complexity: 
$O(n)$ for odd and even arrays as well as permutation array(s).
# Code
```java []
class Solution { 

    public static final long[] INT_RANGE_FACTORIALS = {1L, 1L, 2L, 6L, 24L, 120L, 720L, 5040L, 40320L, 362880L, 3628800L, 39916800L, 479001600L};
    public int[] permute(int n, long k) {
        if(n % 2 == 1) {
           return permuteOddN(n, k, makeOddArr(n), mak



Arr(n));
        } else {
            int[] res = new int[n];
            long t = factorialSquare(n/2 - 1); //t = (n/2 - 1)! * (n/2)! = ((n/2 - 1)!)^2 * (n/2)
            if(t < Long.MAX_VALUE) t *= (n/2); //bound t by max if the sq exceeds it so not to overflow, lower's won't overflow as max possible = 12!^2 * 13 < Long_MAX
            
            int startNumber = 1 + (int)((k-1)/t);
            if(startNumber > n) return new int[0];

            res[0] = startNumber;
            k %= t;
            if(k == 0) k = t;

            int[] evens = makeEvenArr(n), odds = makeOddArr(n);
     
            if(startNumber % 2 == 0) {
                evens = removeFromPolarityGroup(evens, startNumber/2 - 1);
            } else {
                odds = removeFromPolarityGroup(odds, startNumber/2);
            }

            int[] polarity1 = startNumber % 2 == 0 ? odds : evens;
            int[] polarity2 = startNumber % 2 == 0 ? evens : odds;
            int[] suffix =  permuteOddN(n-1, k, polarity1, polarity2);

            for(int i = 1; i < n; i++) {
                res[i] = suffix[i-1];
            }

            return res;
        }
        
    }

    private static int[] permuteOddN(int n, long k, int[] odds, int[] evens) {
        long prevTerm = oddChosenM(n, 0);
        if(prevTerm < k) return new int[0];

        int[] res = new int[n], polarityGroup = odds;
        for(int i = 0; i < n; i++) {
            k %= prevTerm; 
            if(k == 0) k = prevTerm;
            if(k == 0) { //this means k = prevTerm, so k was max perm possible from here, so just greedily maximize without needing to process further
                maximizePerm(res, evens, odds, i, n);
                break;
            }

            long term = oddChosenM(n, i+1);
            /*find the term group: if in the jth group: (j-1)*term < k <= j*term, so (j-1) < k/term <= j, this is equiv to floor((k-1)/term) = j-1. 
            this selects j-1th group, so +1 (doesn't need a +1 in code as this offset accounts for the 0 index arr vs 1 index group)*/
            int group = (int)((k-1)/term);
            
            if(i % 2 == 0) {
                res[i] = odds[group];
                odds = removeFromPolarityGroup(odds, group);
            } else {
                res[i] = evens[group];
                evens = removeFromPolarityGroup(evens, group);
            }
            prevTerm = term;
        }
        return res;
    }
    private static long oddChosenM(int n, int m) {
        long factSq = factorialSquare((n-m)/2);
        if(factSq == Long.MAX_VALUE) return Long.MAX_VALUE;
        return factSq * (m % 2 == 0 ? (n-m+1)/2 : 1);
    }
    
    private static long factorialSquare(int num) {
        if(num >= INT_RANGE_FACTORIALS.length) return Long.MAX_VALUE;
        return INT_RANGE_FACTORIALS[num]*INT_RANGE_FACTORIALS[num];
    }

    private static int[] removeFromPolarityGroup(int[] polarityGroup, int index) {
        int val = polarityGroup[index];
        int[] newPolGroup = new int[polarityGroup.length-1];

        for(int i = 0; i < index; i++) newPolGroup[i] = polarityGroup[i];
        for(int i = index; i < newPolGroup.length; i++) newPolGroup[i] = polarityGroup[i+1];
    
        return newPolGroup;
    }

    private static void maximizePerm(int[] res, int[] evens, int[] odds, int i, int n) {
        int evensRight = evens.length, oddsRight = odds.length;
        for(int j = i; j < n; j+=2) {
            if(i % 2 == 0) {
                res[j] = evens[--evensRight];
                if(j+1 < n) res[j+1] = odds[--oddsRight];
            } else {
                res[j] = odds[--oddsRight];
                if(j+1 < n) res[j+1] = evens[--evensRight];
            }
        }
    }

    private static int[] makeEvenArr(int n) {
        int[] evens = new int[n/2];
        for(int i = 0; i < evens.length; i++) {
            evens[i] = (2*(i+1));
        }
        return evens;
    }

    private static int[] makeOddArr(int n) {
        int[] odds = new int[(n+1)/2];
        for(int i = 0; i < odds.length; i++) {
            odds[i] = 2*i + 1;
        }
        return odds;
    }

    
}
```
['Math', 'Combinatorics', 'Java']