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:
- the values at odd indices are sorted in non-increasing order;
- 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 <= 401 <= nums[i] <= 1000
Hints for Sort Even and Odd Indices Independently
Hint 1
Split the array by index parity into two lists.
Hint 2
Sort the even-index list ascending and the odd-index list descending.
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
evens = sorted(nums[0::2]),odds = sorted(nums[1::2], reverse=True).- Rebuild: index
itakesevens[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 outJava
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