{x}
blog image

Sort Even and Odd Indices Independently

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

2164. Sort Even and Odd Indices Independently

Problem Description

Given a 0-indexed integer array nums, rearrange its values according to these rules:

  1. Sort the values at odd indices in non-increasing order.
  2. Sort the values at even indices in non-decreasing order.

Return the rearranged array.

Solution: Sorting

This problem can be efficiently solved using sorting. We separate the elements at even and odd indices into two separate arrays. Then, we sort the even-indexed array in ascending order and the odd-indexed array in descending order. Finally, we merge these sorted arrays back into the original array structure.

Algorithm

  1. Separate Even and Odd: Create two lists (or arrays): one to store elements at even indices and another for odd indices.
  2. Sort: Sort the even-indexed list in ascending order and the odd-indexed list in descending order.
  3. Merge: Interleave the sorted even and odd lists back into the original array, maintaining the even/odd index pattern.

Time and Space Complexity

  • Time Complexity: O(n log n), dominated by the sorting operations. The other operations (separating, merging) take O(n) time.
  • Space Complexity: O(n) in the worst case, as we create two new arrays to store even and odd indices separately. In some implementations (like Python's list slicing), this space complexity might be slightly lower as it can be optimized to operate in-place more effectively.

Code Implementation (Multiple Languages)

Python

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:
        even = sorted(nums[::2])  # Even indices (step 2)
        odd = sorted(nums[1::2], reverse=True)  # Odd indices (step 2)
        result = []
        for i in range(len(even)):
            result.extend([even[i], odd[i]]) #Merge (step 3)
 
        if len(nums) % 2 != 0:  # Handle odd length arrays.
            result.append(even[-1])
        return result

Java

import java.util.Arrays;
 
class Solution {
    public int[] sortEvenOdd(int[] nums) {
        int n = nums.length;
        int[] even = new int[(n + 1) / 2];
        int[] odd = new int[n / 2];
        int evenIndex = 0;
        int oddIndex = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                even[evenIndex++] = nums[i];
            } else {
                odd[oddIndex++] = nums[i];
            }
        }
        Arrays.sort(even);
        Arrays.sort(odd);
        int[] result = new int[n];
        int evenPtr = 0;
        int oddPtr = odd.length -1;
        for(int i=0; i<n; i++){
            if(i%2 == 0){
                result[i] = even[evenPtr++];
            } else{
                result[i] = odd[oddPtr--];
            }
        }
        return result;
    }
}

C++

#include <vector>
#include <algorithm>
 
class Solution {
public:
    std::vector<int> sortEvenOdd(std::vector<int>& nums) {
        int n = nums.size();
        std::vector<int> even;
        std::vector<int> odd;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                even.push_back(nums[i]);
            } else {
                odd.push_back(nums[i]);
            }
        }
        std::sort(even.begin(), even.end());
        std::sort(odd.begin(), odd.end(), std::greater<int>()); //Descending order
        std::vector<int> result;
        int evenPtr = 0;
        int oddPtr = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                result.push_back(even[evenPtr++]);
            } else {
                result.push_back(odd[oddPtr++]);
            }
        }
        return result;
    }
};

JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortEvenOdd = function(nums) {
    let even = nums.filter((num, i) => i % 2 === 0).sort((a, b) => a - b);
    let odd = nums.filter((num, i) => i % 2 !== 0).sort((a, b) => b - a);
    let result = [];
    let evenIndex = 0;
    let oddIndex = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i % 2 === 0) {
            result.push(even[evenIndex++]);
        } else {
            result.push(odd[oddIndex++]);
        }
    }
    return result;
};

These code examples all follow the same algorithmic structure, differing only in syntax and library usage specific to each programming language. Remember to include necessary header files or import statements for sorting functions in C++, Java, and other languages as needed.