Sort Even and Odd Indices Independently

Problem

You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules:

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.
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.

Examples

Example 1

1
2
3
4
5
6
7
8


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

1
2
3
4
5


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

Solution

Method 1 - Separate, Sort, and Merge

Intuition: Extract elements at even and odd indices separately, sort them according to their requirements (even indices ascending, odd indices descending), then place them back in their respective positions.

Approach:

Separate elements at even indices and odd indices into different arrays
Sort even-indexed elements in ascending order (non-decreasing)
Sort odd-indexed elements in descending order (non-increasing)
Merge the sorted arrays back into the result, maintaining index parity

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> sortEvenOdd(vector<int>& nums) {
        vector<int> evenElements, oddElements;
        
        // Separate elements by index parity
        for (int i = 0; i < nums.size(); i++) {
            if (i % 2 == 0) {
                evenElements.push_back(nums[i]);
            } else {
                oddElements.push_back(nums[i]);
            }
        }
        
        // Sort even indices in ascending order
        sort(evenElements.begin(), evenElements.end());
        
        // Sort odd indices in descending order
        sort(oddElements.begin(), oddElements.end(), greater<int>());
        
        // Merge back into result
        vector<int> result(nums.size());
        int evenIdx = 0, oddIdx = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            if (i % 2 == 0) {
                result[i] = evenElements[evenIdx++];
            } else {
                result[i] = oddElements[oddIdx++];
            }
        }
        
        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


import "sort"

func sortEvenOdd(nums []int) []int {
    var evenElements, oddElements []int
    
    // Separate elements by index parity
    for i, num := range nums {
        if i%2 == 0 {
            evenElements = append(evenElements, num)
        } else {
            oddElements = append(oddElements, num)
        }
    }
    
    // Sort even indices in ascending order
    sort.Ints(evenElements)
    
    // Sort odd indices in descending order
    sort.Sort(sort.Reverse(sort.IntSlice(oddElements)))
    
    // Merge back into result
    result := make([]int, len(nums))
    evenIdx, oddIdx := 0, 0
    
    for i := range nums {
        if i%2 == 0 {
            result[i] = evenElements[evenIdx]
            evenIdx++
        } else {
            result[i] = oddElements[oddIdx]
            oddIdx++
        }
    }
    
    return result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


import java.util.*;

class Solution {
    public int[] sortEvenOdd(int[] nums) {
        List<Integer> evenElements = new ArrayList<>();
        List<Integer> oddElements = new ArrayList<>();
        
        // Separate elements by index parity
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                evenElements.add(nums[i]);
            } else {
                oddElements.add(nums[i]);
            }
        }
        
        // Sort even indices in ascending order
        Collections.sort(evenElements);
        
        // Sort odd indices in descending order
        Collections.sort(oddElements, Collections.reverseOrder());
        
        // Merge back into result
        int[] result = new int[nums.length];
        int evenIdx = 0, oddIdx = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                result[i] = evenElements.get(evenIdx++);
            } else {
                result[i] = oddElements.get(oddIdx++);
            }
        }
        
        return result;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution {
    fun sortEvenOdd(nums: IntArray): IntArray {
        val evenElements = mutableListOf<Int>()
        val oddElements = mutableListOf<Int>()
        
        // Separate elements by index parity
        for (i in nums.indices) {
            if (i % 2 == 0) {
                evenElements.add(nums[i])
            } else {
                oddElements.add(nums[i])
            }
        }
        
        // Sort even indices in ascending order
        evenElements.sort()
        
        // Sort odd indices in descending order
        oddElements.sortDescending()
        
        // Merge back into result
        val result = IntArray(nums.size)
        var evenIdx = 0
        var oddIdx = 0
        
        for (i in nums.indices) {
            if (i % 2 == 0) {
                result[i] = evenElements[evenIdx++]
            } else {
                result[i] = oddElements[oddIdx++]
            }
        }
        
        return result
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


def sortEvenOdd(nums: list[int]) -> list[int]:
    even_elements = []
    odd_elements = []
    
    # Separate elements by index parity
    for i, num in enumerate(nums):
        if i % 2 == 0:
            even_elements.append(num)
        else:
            odd_elements.append(num)
    
    # Sort even indices in ascending order
    even_elements.sort()
    
    # Sort odd indices in descending order
    odd_elements.sort(reverse=True)
    
    # Merge back into result
    result = [0] * len(nums)
    even_idx = odd_idx = 0
    
    for i in range(len(nums)):
        if i % 2 == 0:
            result[i] = even_elements[even_idx]
            even_idx += 1
        else:
            result[i] = odd_elements[odd_idx]
            odd_idx += 1
    
    return result

# Alternative one-liner approach
def sortEvenOdd2(nums: list[int]) -> list[int]:
    even_sorted = sorted([nums[i] for i in range(0, len(nums), 2)])
    odd_sorted = sorted([nums[i] for i in range(1, len(nums), 2)], reverse=True)
    
    result = []
    even_idx = odd_idx = 0
    
    for i in range(len(nums)):
        if i % 2 == 0:
            result.append(even_sorted[even_idx])
            even_idx += 1
        else:
            result.append(odd_sorted[odd_idx])
            odd_idx += 1
    
    return result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


impl Solution {
    pub fn sort_even_odd(nums: Vec<i32>) -> Vec<i32> {
        let mut even_elements = Vec::new();
        let mut odd_elements = Vec::new();
        
        // Separate elements by index parity
        for (i, &num) in nums.iter().enumerate() {
            if i % 2 == 0 {
                even_elements.push(num);
            } else {
                odd_elements.push(num);
            }
        }
        
        // Sort even indices in ascending order
        even_elements.sort();
        
        // Sort odd indices in descending order
        odd_elements.sort_by(|a, b| b.cmp(a));
        
        // Merge back into result
        let mut result = vec![0; nums.len()];
        let mut even_idx = 0;
        let mut odd_idx = 0;
        
        for i in 0..nums.len() {
            if i % 2 == 0 {
                result[i] = even_elements[even_idx];
                even_idx += 1;
            } else {
                result[i] = odd_elements[odd_idx];
                odd_idx += 1;
            }
        }
        
        result
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


function sortEvenOdd(nums: number[]): number[] {
    const evenElements: number[] = [];
    const oddElements: number[] = [];
    
    // Separate elements by index parity
    for (let i = 0; i < nums.length; i++) {
        if (i % 2 === 0) {
            evenElements.push(nums[i]);
        } else {
            oddElements.push(nums[i]);
        }
    }
    
    // Sort even indices in ascending order
    evenElements.sort((a, b) => a - b);
    
    // Sort odd indices in descending order
    oddElements.sort((a, b) => b - a);
    
    // Merge back into result
    const result: number[] = new Array(nums.length);
    let evenIdx = 0, oddIdx = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (i % 2 === 0) {
            result[i] = evenElements[evenIdx++];
        } else {
            result[i] = oddElements[oddIdx++];
        }
    }
    
    return result;
}

Complexity

⏰ Time complexity: O(n log n) where n is the length of the array (due to sorting operations)
🧺 Space complexity: O(n) for storing the separated even and odd elements

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 - Separate, Sort, and Merge#

Code#

Complexity#