Sort Even and Odd Indices Independently

Easy
372.

Sort Even and Odd Indices Independently

Sort Even and Odd Indices Independently is an easy coding problem on arrays and sorting, asked in Amazon and Microsoft interviews.

You are given a 0-indexed integer array nums. Rearrange it so that:

  1. the values at odd indices are sorted in non-increasing order;
  2. the values at even indices are sorted in non-decreasing order.

Return the resulting array.

Example 1

Input
nums = [4,1,2,3]
Output
[2,3,4,1]
Explanation
Even indices hold 2 and 4 ascending; odd indices hold 3 and 1 descending.

Example 2

Input
nums = [2,1]
Output
[2,1]

Example 3

Input
nums = [5,5,5,5]
Output
[5,5,5,5]

Constraints

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortEvenOdd = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sort Even and Odd Indices Independently — Problem & Solution

Sort Even and Odd Indices Independently solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Sort Even and Odd Indices Independently is an easy coding problem on arrays and sorting, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a 0-indexed integer array nums. Rearrange it so that:

  1. the values at odd indices are sorted in non-increasing order;
  2. the values at even indices are sorted in non-decreasing order.

Return the resulting array.

Example 1

Input: nums = [4,1,2,3]
Output: [2,3,4,1]
Explanation: Even indices hold 2 and 4 ascending; odd indices hold 3 and 1 descending.

Example 2

Input: nums = [2,1]
Output: [2,1]

Example 3

Input: nums = [5,5,5,5]
Output: [5,5,5,5]

Constraints

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= 1000

Hints for Sort Even and Odd Indices Independently

  1. Hint 1

    Split the array by index parity into two lists.

  2. Hint 2

    Sort the even-index list ascending and the odd-index list descending.

  3. Hint 3

    Then write them back into their original index slots in order.

How to solve Sort Even and Odd Indices Independently

Split by index parity, sort evens ascending and odds descending, then write them back into their slots.

Approach

  1. evens = sorted(nums[0::2]), odds = sorted(nums[1::2], reverse=True).
  2. Rebuild: index i takes evens[i/2] when even, odds[i/2] when odd.

Why it works

The two index classes are independent, so sorting each separately and reinterleaving satisfies both conditions.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Values are bounded by 100, so counting sort per class is linear if needed.

Reference solution

Python

def sortEvenOdd(nums):
    evens = sorted(nums[0::2])
    odds = sorted(nums[1::2], reverse=True)
    out = []
    for i in range(len(nums)):
        out.append(evens[i // 2] if i % 2 == 0 else odds[i // 2])
    return out

Java

public static int[] sortEvenOdd(int[] nums) {
    int evenCount = (nums.length + 1) / 2;
    int oddCount = nums.length / 2;
    int[] evens = new int[evenCount];
    int[] odds = new int[oddCount];
    int e = 0, o = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i % 2 == 0) evens[e++] = nums[i];
        else odds[o++] = nums[i];
    }
    Arrays.sort(evens);
    Arrays.sort(odds);
    int[] out = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        out[i] = i % 2 == 0 ? evens[i / 2] : odds[oddCount - 1 - (i - 1) / 2];
    }
    return out;
}

C++

vector<int> sortEvenOdd(vector<int>& nums) {
    vector<int> evens, odds;
    for (int i = 0; i < (int) nums.size(); i++) {
        if (i % 2 == 0) evens.push_back(nums[i]);
        else odds.push_back(nums[i]);
    }
    sort(evens.begin(), evens.end());
    sort(odds.begin(), odds.end(), greater<int>());
    vector<int> out;
    for (int i = 0; i < (int) nums.size(); i++) {
        out.push_back(i % 2 == 0 ? evens[i / 2] : odds[(i - 1) / 2]);
    }
    return out;
}

JavaScript

var sortEvenOdd = function(nums) {
    const evens = [], odds = [];
    for (let i = 0; i < nums.length; i++) {
        if (i % 2 === 0) evens.push(nums[i]);
        else odds.push(nums[i]);
    }
    evens.sort(function(a, b) { return a - b; });
    odds.sort(function(a, b) { return b - a; });
    const out = [];
    for (let i = 0; i < nums.length; i++) {
        out.push(i % 2 === 0 ? evens[i / 2] : odds[(i - 1) / 2]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms