Sort Even and Odd Indices Independently - Video Solutions

Problem Overview: Given an integer array nums, reorder it so elements at even indices (0,2,4...) appear in ascending order while elements at odd indices (1,3,5...) appear in descending order. The relative ordering only applies within their own index groups.

Approach 1: Separate and Sort (Two Arrays) (Time: O(n log n), Space: O(n))

Iterate through the array once and split the values into two lists: one for even indices and one for odd indices. Sort the even-index list in ascending order and the odd-index list in descending order using a standard sort operation. Then rebuild the original array by iterating through indices and pulling the next value from the appropriate list. This approach is straightforward and easy to reason about. The key insight is that even and odd indices are completely independent groups, so sorting them separately produces the required final arrangement.

The algorithm performs a single pass to collect values, two sorting operations, and another pass to write results back. Sorting dominates the runtime at O(n log n). Extra storage for the two temporary arrays requires O(n) space. This approach is commonly used when solving problems involving independent index partitions in array manipulation combined with sorting.

Approach 2: In-place Rearrangement (Time: O(n log n), Space: O(1) extra)

Instead of storing two additional arrays, treat even and odd positions as two logical subsequences inside the same array. Extract the values logically by iterating with step size two, sort the even-indexed values ascending and the odd-indexed values descending, then write them back to their respective indices using pointers that jump by two. In languages like Python or JavaScript this can be implemented with slicing or temporary views while still rewriting the original array directly.

The runtime remains O(n log n) because sorting still dominates the work. However, extra auxiliary memory is minimized since values are rearranged back into the same array structure. This version is useful when interviewers ask for minimal additional memory while still leveraging efficient built‑in sorting routines.

Recommended for interviews: The separate-and-sort method is the clearest explanation during interviews. You show understanding by recognizing that even and odd indices form two independent sequences. Once that observation is stated, sorting each sequence individually becomes obvious. The in-place version demonstrates awareness of memory optimization but follows the same core idea.