You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules:
nums in non-increasing order.
nums = [4,1,2,3] before this step, it becomes [4,3,2,1] after. The values at odd indices 1 and 3 are sorted in non-increasing order.nums in non-decreasing order.
nums = [4,1,2,3] before this step, it becomes [2,1,4,3] after. The values at even indices 0 and 2 are sorted in non-decreasing order.Return the array formed after rearranging the values of nums.
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 <= 1001 <= nums[i] <= 100Problem 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.
This approach involves splitting the array into two separate arrays: one containing elements at even indices and the other containing elements at odd indices. Once split, we can sort the even index array in non-decreasing order and the odd index array in non-increasing order. Finally, we merge the sorted arrays back into the original structure by placing them back at their respective indices.
The C solution involves using separate arrays for even and odd indices. We populate these arrays with respective elements from the input array. Then, we sort these arrays using the qsort function, specifying different comparators for ascending and descending order. Finally, we merge these sorted arrays back into the original input array in their original positions.
Time Complexity: O(n log n), primarily due to sorting operations.
Space Complexity: O(n), additional space for separate even and odd arrays.
This approach is an alternative but less optimal than the first one, aimed at modifying the input array in place. Instead of using additional arrays to hold the even and odd indexed elements separately, this solution involves selective swapping and rearranging within the given array. It involves logically partitioning and then sorting respective indices without additional splits, which can be cumbersome and error-prone.
The in-place Python solution relies on bubble-sort-like nested loops to achieve sorting. For both even and odd indexed elements, we iterate over every pair of indices in respective sequences, performing swaps where necessary to maintain order properties read directly within the input array.
Python
JavaScript
Time Complexity: O(n^2) because of the nested loops.
Space Complexity: O(1), because operations are performed in place without extra space usage.
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.
The time complexity is O(n log n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Separate and Sort (Two Arrays) | Time Complexity: O(n log n), primarily due to sorting operations. |
| In-place Rearrangement | Time Complexity: O(n^2) because of the nested loops. |
| Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Separate and Sort (Two Arrays) | O(n log n) | O(n) | Best for clarity and interviews; simplest implementation |
| In-place Rearrangement | O(n log n) | O(1) extra | When minimizing extra memory while keeping the same logic |
2164. Sort Even and Odd Indices Independently || LeetCode 2164 || Weekly LeetCode 279 • Bro Coders • 2,169 views views
Watch 9 more video solutions →Practice Sort Even and Odd Indices Independently with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor