#2164

Easy

LeetCode Problem Workspace

Sort Even and Odd Indices Independently

Rearrange a 0-indexed array by sorting even and odd indices independently for predictable order and correctness.

Problem Statement

You are given a 0-indexed integer array nums. Rearrange the values such that all elements at even indices are sorted in non-decreasing order, and all elements at odd indices are sorted in non-increasing order. Maintain the original positions for each index type while applying these sorts.

Return the array formed after performing these index-based sorts. For example, given nums = [4,1,2,3], sorting odd indices gives [4,3,2,1], then sorting even indices results in [2,3,4,1]. Ensure your solution handles arrays of varying lengths correctly.

Examples

Example 1

Input: nums = [4,1,2,3]

Output: [2,3,4,1]

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]

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 Approach

Separate Even and Odd Indices

Iterate through the array and collect two separate lists: one for values at even indices and another for values at odd indices. This allows independent sorting without interfering with the other set.

Sort Each List Appropriately

Sort the even-index list in ascending order and the odd-index list in descending order. This respects the problem requirement and avoids failure from mixing index types.

Merge Back into Original Array

Iterate over the original array indices and place the sorted values back into their respective even or odd positions. This reconstruction step preserves the index pattern while achieving the desired order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to sorting two separate lists of up to n/2 elements each. Space complexity is O(n) for storing the even and odd lists before merging back into the array.

What Interviewers Usually Probe

Can you separate values by index type before sorting?
What happens if you mix odd and even index elements during sorting?
How does your approach maintain the pattern while sorting independently?

Common Pitfalls or Variants

Common pitfalls

Sorting the entire array without separating indices causes incorrect order.
Failing to handle single-element even or odd positions may produce errors.
Merging incorrectly by index can overwrite values and break the desired pattern.

Follow-up variants

Sorting odd indices in ascending order instead of descending.
Handling arrays with duplicate values at the same index type.
Sorting indices independently for multi-dimensional arrays or subarrays.

FAQ

What is the main strategy for Sort Even and Odd Indices Independently?

The core strategy is to separate values by even and odd indices, sort each list according to the problem rules, then merge them back into their original positions.

Can I sort the entire array at once for this problem?

No, sorting the entire array without separating indices will break the pattern and produce incorrect results.

How should I handle arrays with only one element at an index type?

Single-element even or odd indices do not need sorting, but you must still merge correctly to maintain the overall pattern.

What is the time complexity of sorting even and odd indices separately?

Sorting two separate lists of length n/2 each results in O(n log n) time complexity.

Does GhostInterview check the final merged array correctness?

Yes, it validates that the merged array preserves even and odd index patterns while maintaining the required sorted order.

terminal

Solution

Solution 1: Sorting

We can extract the elements at odd and even indices separately, then sort the array of odd indices in non-increasing order and the array of even indices in non-decreasing order. Finally, merge the two arrays back together.

1

2

3

4

5

6

7

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:
        a = sorted(nums[::2])
        b = sorted(nums[1::2], reverse=True)
        nums[::2] = a
        nums[1::2] = b
        return nums

Continue Practicing

#2171 removing minimum number of magic beans #2154 keep multiplying found values by two #2148 count elements with strictly smaller and greater elements