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:

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.

Examples

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

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

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

Code

C++

#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;
    }
};

Go

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
}

Java

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;
    }
}

Kotlin

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

Python

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

Rust

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

TypeScript

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