# Sort Even and Odd Indices Independently
**Difficulty:** EASY
[External](https://leetcode.com/problems/sort-even-and-odd-indices-independently)
Canonical: https://scaleengineer.com/dsa/problems/sort-even-and-odd-indices-independently
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Zoho](https://scaleengineer.com/companies/zoho)
---
## Problem
You are given a **0-indexed** integer array `nums`. Rearrange the values of `nums` according to the following rules:

1. Sort the values at **odd indices** of `nums` in **non-increasing** order.  
  * For example, if `nums = [4,**1**,2,**3**]` before this step, it becomes `[4,**3**,2,**1**]` after. The values at odd indices `1` and `3` are sorted in non-increasing order.
2. Sort the values at **even indices** of `nums` in **non-decreasing** order.  
  * For example, if `nums = [**4**,1,**2**,3]` before this step, it becomes `[**2**,1,**4**,3]` after. The values at even indices `0` and `2` are sorted in non-decreasing order.

Return _the array formed after rearranging the values of_ `nums`.

**Example 1:**

**Input:** nums = [4,1,2,3]
**Output:** [2,3,4,1]
**Explanation:** 
First, we sort the values present at odd indices (1 and 3) in non-increasing order.
So, nums changes from [4,**1**,2,**3**] to [4,**3**,2,**1**].
Next, we sort the values present at even indices (0 and 2) in non-decreasing order.
So, nums changes from [**4**,1,**2**,3] to [**2**,3,**4**,1].
Thus, the array formed after rearranging the values is [2,3,4,1].

**Example 2:**

**Input:** nums = [2,1]
**Output:** [2,1]
**Explanation:** 
Since there is exactly one odd index and one even index, no rearrangement of values takes place.
The resultant array formed is [2,1], which is the same as the initial array. 

**Constraints:**

* `1 <= nums.length <= 100`
* `1 <= nums[i] <= 100`

# Approaches
## Separate, Sort, and Merge
This approach follows the problem description directly. We first separate the numbers at even and odd indices into two different lists. Then, we sort these lists according to the specified rules (non-decreasing for even-indexed values, non-increasing for odd-indexed values). Finally, we merge the sorted values back into the original array at their respective even and odd positions.
**Time:** O(N log N), where N is the number of elements in `nums`. The dominant operations are sorting the `evenNums` and `oddNums` lists, each of which has approximately N/2 elements. Sorting takes O((N/2)log(N/2)), which simplifies to O(N log N). The initial separation and final merging steps both take O(N) time. · **Space:** O(N), where N is the number of elements in `nums`. We use two auxiliary lists, `evenNums` and `oddNums`, whose combined size is equal to N.
**Pros:** Simple and intuitive to understand and implement.; Works for any range of numbers, not just the constrained `1 <= nums[i] <= 100`.
**Cons:** Not the most efficient in terms of time complexity due to the comparison-based sort.; Requires extra space proportional to the input size.
### Explanation
The core idea is to isolate the two subproblems (sorting even-indexed elements and sorting odd-indexed elements) and solve them independently before combining the results.
1.  Initialize two empty lists, `evenNums` and `oddNums`.
2.  Iterate through the input array `nums` with an index `i`.
3.  If `i` is even, add `nums[i]` to the `evenNums` list.
4.  If `i` is odd, add `nums[i]` to the `oddNums` list.
5.  After populating the lists, sort `evenNums` in ascending order. In Java, `Collections.sort()` can be used.
6.  Sort `oddNums` in descending order. In Java, `Collections.sort(oddNums, Collections.reverseOrder())` can be used.
7.  Create two pointers, `evenPtr = 0` and `oddPtr = 0`, to track our position in the sorted lists.
8.  Iterate through the original `nums` array again from `i = 0` to `nums.length - 1`.
9.  If `i` is even, set `nums[i] = evenNums.get(evenPtr++)`.
10. If `i` is odd, set `nums[i] = oddNums.get(oddPtr++)`.
11. After the loop, `nums` will contain the rearranged elements.
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] sortEvenOdd(int[] nums) {
        List<Integer> evenNums = new ArrayList<>();
        List<Integer> oddNums = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                evenNums.add(nums[i]);
            } else {
                oddNums.add(nums[i]);
            }
        }

        // Sort even-indexed values in non-decreasing order
        Collections.sort(evenNums);

        // Sort odd-indexed values in non-increasing order
        Collections.sort(oddNums, Collections.reverseOrder());

        int evenPtr = 0;
        int oddPtr = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                nums[i] = evenNums.get(evenPtr++);
            } else {
                nums[i] = oddNums.get(oddPtr++);
            }
        }

        return nums;
    }
}
```
### Algorithm
*   Create two lists, `evenNums` and `oddNums`.
*   Iterate through `nums`. If the index is even, add the element to `evenNums`; otherwise, add it to `oddNums`.
*   Sort `evenNums` in non-decreasing (ascending) order.
*   Sort `oddNums` in non-increasing (descending) order.
*   Iterate through `nums` again. Fill even indices with elements from the sorted `evenNums` and odd indices with elements from the sorted `oddNums`.
*   Return the modified `nums` array.

## Using Counting Sort
This approach leverages the constraint that the values in `nums` are between 1 and 100. Instead of a general-purpose comparison sort, we can use a more efficient, linear-time sorting algorithm like Counting Sort. We use two separate frequency arrays (or count arrays), one for even-indexed values and one for odd-indexed values, to count the occurrences of each number. Then, we reconstruct the original array by iterating through the frequency arrays in the required order.
**Time:** O(N + K), where N is the length of `nums` and K is the range of possible values (100 in this case). Populating the count arrays takes O(N). Reconstructing the array involves iterating through the count arrays (O(K)) and placing N elements in total. Since K is a constant, the complexity is effectively linear, O(N). · **Space:** O(K), where K is the range of values (100). We use two frequency arrays of size K+1. Since K is a constant, the space complexity is O(1).
**Pros:** Highly efficient with linear time complexity, which is better than the O(N log N) of comparison-based sorting.; Constant space complexity, as it does not depend on the size of the input array `N`.
**Cons:** This approach is only efficient because the range of values in the input array is small and known. It would be impractical if the numbers could be very large.
### Explanation
Since the range of values is small and fixed (1 to 100), we can count the frequency of each number for even and odd indices separately.
1.  Initialize two integer arrays, `evenCounts` and `oddCounts`, of size 101, filled with zeros. These will store the frequencies of numbers from 1 to 100.
2.  Iterate through the input array `nums` with an index `i`.
3.  If `i` is even, increment the count for `nums[i]` in the `evenCounts` array: `evenCounts[nums[i]]++`.
4.  If `i` is odd, increment the count for `nums[i]` in the `oddCounts` array: `oddCounts[nums[i]]++`.
5.  Now, we overwrite the original `nums` array with the sorted values.
6.  To fill the even indices (non-decreasing), we iterate through the `evenCounts` array from 1 to 100. For each number `j`, we place it into the next available even slot in `nums` as many times as its count in `evenCounts[j]`.
7.  To fill the odd indices (non-increasing), we iterate through the `oddCounts` array from 100 down to 1. For each number `j`, we place it into the next available odd slot in `nums` as many times as its count in `oddCounts[j]`.
```java
class Solution {
    public int[] sortEvenOdd(int[] nums) {
        int[] evenCounts = new int[101];
        int[] oddCounts = new int[101];

        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                evenCounts[nums[i]]++;
            } else {
                oddCounts[nums[i]]++;
            }
        }

        int evenIndex = 0;
        // Place sorted even-indexed values
        for (int i = 1; i <= 100; i++) {
            while (evenCounts[i] > 0) {
                nums[evenIndex] = i;
                evenIndex += 2;
                evenCounts[i]--;
            }
        }

        int oddIndex = 1;
        // Place sorted odd-indexed values
        for (int i = 100; i >= 1; i--) {
            while (oddCounts[i] > 0) {
                nums[oddIndex] = i;
                oddIndex += 2;
                oddCounts[i]--;
            }
        }

        return nums;
    }
}
```
### Algorithm
*   Create two frequency arrays, `evenCounts` and `oddCounts`, of size 101 (for values 1-100).
*   Iterate through `nums`. Populate `evenCounts` with frequencies of numbers at even indices and `oddCounts` with frequencies of numbers at odd indices.
*   Initialize a pointer `evenIndex = 0`.
*   Iterate from `i = 1` to `100`. For each `i`, while `evenCounts[i] > 0`, place `i` at `nums[evenIndex]`, increment `evenIndex` by 2, and decrement `evenCounts[i]`.
*   Initialize a pointer `oddIndex = 1`.
*   Iterate from `i = 100` down to `1`. For each `i`, while `oddCounts[i] > 0`, place `i` at `nums[oddIndex]`, increment `oddIndex` by 2, and decrement `oddCounts[i]`.
*   Return the modified `nums` array.

# Solutions
### Java

```java
class Solution { public int [] sortEvenOdd ( int [] nums ) { int n = nums . length ; int [] a = new int [( n + 1 ) >> 1 ]; int [] b = new int [ n >> 1 ]; for ( int i = 0 , j = 0 ; j < n >> 1 ; i += 2 , ++ j ) { a [ j ] = nums [ i ]; b [ j ] = nums [ i + 1 ]; } if ( n % 2 == 1 ) { a [ a . length - 1 ] = nums [ n - 1 ]; } Arrays . sort ( a ); Arrays . sort ( b ); int [] ans = new int [ n ]; for ( int i = 0 , j = 0 ; j < a . length ; i += 2 , ++ j ) { ans [ i ] = a [ j ]; } for ( int i = 1 , j = b . length - 1 ; j >= 0 ; i += 2 , -- j ) { ans [ i ] = b [ j ]; } return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < int > sortEvenOdd ( vector < int >& nums ) { int n = nums . size (); vector < int > a ; vector < int > b ; for ( int i = 0 ; i < n ; ++ i ) { if ( i % 2 == 0 ) a . push_back ( nums [ i ]); else b . push_back ( nums [ i ]); } sort ( a . begin (), a . end ()); sort ( b . begin (), b . end (), greater < int > ()); vector < int > ans ( n ); for ( int i = 0 , j = 0 ; j < a . size (); i += 2 , ++ j ) ans [ i ] = a [ j ]; for ( int i = 1 , j = 0 ; j < b . size (); i += 2 , ++ j ) ans [ i ] = b [ j ]; return ans ; } };
```

### Python

```python
class Solution : def sortEvenOdd ( self , nums : List [ int ]) -> List [ int ]: a = sorted ( nums [:: 2 ]) b = sorted ( nums [ 1 :: 2 ], reverse = True ) nums [:: 2 ] = a nums [ 1 :: 2 ] = b return nums
```