Sort Even and Odd Indices Independently

Difficulty: Easy | Acceptance: 63.30% | Paid: No Topics: Array, Sorting

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.
2. Sort the values at even indices of nums in non-decreasing order.

Return the array formed after rearranging nums’s values.

• Examples
• Constraints
• Separate and Sort
• In-place Modification
• Priority Queue Approach

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

Separate and Sort

Intuition Extract elements at even and odd indices into separate arrays, sort them independently, then merge back into the result array.

Steps

• Create two separate arrays for even and odd indexed elements
• Sort even-indexed elements in ascending order
• Sort odd-indexed elements in descending order
• Merge the sorted arrays back into their original positions

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:
        even = [nums[i] for i in range(0, len(nums), 2)]
        odd = [nums[i] for i in range(1, len(nums), 2)]
        
        even.sort()
        odd.sort(reverse=True)
        
        result = []
        e_idx, o_idx = 0, 0
        for i in range(len(nums)):
            if i % 2 == 0:
                result.append(even[e_idx])
                e_idx += 1
            else:
                result.append(odd[o_idx])
                o_idx += 1
        
        return result

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Uses extra space for separate arrays but is straightforward and readable.

In-place Modification

Intuition Modify the input array directly by extracting, sorting, and placing elements back at their correct positions without creating a new result array.

Steps

• Extract even and odd indexed elements into separate lists
• Sort even list ascending and odd list descending
• Place sorted elements back into the original array at their respective positions

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:
        even = sorted([nums[i] for i in range(0, len(nums), 2)])
        odd = sorted([nums[i] for i in range(1, len(nums), 2)], reverse=True)
        
        for i in range(0, len(nums), 2):
            nums[i] = even[i // 2]
        
        for i in range(1, len(nums), 2):
            nums[i] = odd[i // 2]
        
        return nums

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Modifies input array in-place but still uses O(n) auxiliary space for sorting.

Priority Queue Approach

Intuition Use a min-heap for even indices and a max-heap for odd indices to efficiently retrieve elements in the required sorted order during reconstruction.

Steps

• Push all even-indexed elements into a min-heap
• Push all odd-indexed elements into a max-heap
• Pop elements from heaps alternately to build the result array

import heapq

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:
        min_heap = []
        max_heap = []
        
        for i in range(len(nums)):
            if i % 2 == 0:
                heapq.heappush(min_heap, nums[i])
            else:
                heapq.heappush(max_heap, -nums[i])
        
        result = []
        for i in range(len(nums)):
            if i % 2 == 0:
                result.append(heapq.heappop(min_heap))
            else:
                result.append(-heapq.heappop(max_heap))
        
        return result

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Useful when elements need to be processed in sorted order dynamically, but has higher constant factors than simple sorting.