Sort Even and Odd Indices Independently
EasyPrompt
You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules:
- Sort the values at odd indices of
numsin non-increasing order.- For example, if
nums = [4,1,2,3]before this step, it becomes[4,3,2,1]after. The values at odd indices1and3are sorted in non-increasing order.
- For example, if
- Sort the values at even indices of
numsin non-decreasing order.- For example, if
nums = [4,1,2,3]before this step, it becomes[2,1,4,3]after. The values at even indices0and2are sorted in non-decreasing order.
- For example, if
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] <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach follows the problem description directly. We first separate the numbers at even and odd indices into two different lists. Then, we sort these lists according to the specified rules (non-decreasing for even-indexed values, non-increasing for odd-indexed values). Finally, we merge the sorted values back into the original array at their respective even and odd positions.
Algorithm
- Create two lists,
evenNumsandoddNums. - Iterate through
nums. If the index is even, add the element toevenNums; otherwise, add it tooddNums. - Sort
evenNumsin non-decreasing (ascending) order. - Sort
oddNumsin non-increasing (descending) order. - Iterate through
numsagain. Fill even indices with elements from the sortedevenNumsand odd indices with elements from the sortedoddNums. - Return the modified
numsarray.
Walkthrough
The core idea is to isolate the two subproblems (sorting even-indexed elements and sorting odd-indexed elements) and solve them independently before combining the results.
- Initialize two empty lists,
evenNumsandoddNums. - Iterate through the input array
numswith an indexi. - If
iis even, addnums[i]to theevenNumslist. - If
iis odd, addnums[i]to theoddNumslist. - After populating the lists, sort
evenNumsin ascending order. In Java,Collections.sort()can be used. - Sort
oddNumsin descending order. In Java,Collections.sort(oddNums, Collections.reverseOrder())can be used. - Create two pointers,
evenPtr = 0andoddPtr = 0, to track our position in the sorted lists. - Iterate through the original
numsarray again fromi = 0tonums.length - 1. - If
iis even, setnums[i] = evenNums.get(evenPtr++). - If
iis odd, setnums[i] = oddNums.get(oddPtr++). - After the loop,
numswill contain the rearranged elements.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int[] sortEvenOdd(int[] nums) { List<Integer> evenNums = new ArrayList<>(); List<Integer> oddNums = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { if (i % 2 == 0) { evenNums.add(nums[i]); } else { oddNums.add(nums[i]); } } // Sort even-indexed values in non-decreasing order Collections.sort(evenNums); // Sort odd-indexed values in non-increasing order Collections.sort(oddNums, Collections.reverseOrder()); int evenPtr = 0; int oddPtr = 0; for (int i = 0; i < nums.length; i++) { if (i % 2 == 0) { nums[i] = evenNums.get(evenPtr++); } else { nums[i] = oddNums.get(oddPtr++); } } return nums; }}Complexity
Time
O(N log N), where N is the number of elements in `nums`. The dominant operations are sorting the `evenNums` and `oddNums` lists, each of which has approximately N/2 elements. Sorting takes O((N/2)log(N/2)), which simplifies to O(N log N). The initial separation and final merging steps both take O(N) time.
Space
O(N), where N is the number of elements in `nums`. We use two auxiliary lists, `evenNums` and `oddNums`, whose combined size is equal to N.
Trade-offs
Pros
Simple and intuitive to understand and implement.
Works for any range of numbers, not just the constrained
1 <= nums[i] <= 100.
Cons
Not the most efficient in terms of time complexity due to the comparison-based sort.
Requires extra space proportional to the input size.
This approach leverages the constraint that the values in nums are between 1 and 100. Instead of a general-purpose comparison sort, we can use a more efficient, linear-time sorting algorithm like Counting Sort. We use two separate frequency arrays (or count arrays), one for even-indexed values and one for odd-indexed values, to count the occurrences of each number. Then, we reconstruct the original array by iterating through the frequency arrays in the required order.
Algorithm
- Create two frequency arrays,
evenCountsandoddCounts, of size 101 (for values 1-100). - Iterate through
nums. PopulateevenCountswith frequencies of numbers at even indices andoddCountswith frequencies of numbers at odd indices. - Initialize a pointer
evenIndex = 0. - Iterate from
i = 1to100. For eachi, whileevenCounts[i] > 0, placeiatnums[evenIndex], incrementevenIndexby 2, and decrementevenCounts[i]. - Initialize a pointer
oddIndex = 1. - Iterate from
i = 100down to1. For eachi, whileoddCounts[i] > 0, placeiatnums[oddIndex], incrementoddIndexby 2, and decrementoddCounts[i]. - Return the modified
numsarray.
Walkthrough
Since the range of values is small and fixed (1 to 100), we can count the frequency of each number for even and odd indices separately.
- Initialize two integer arrays,
evenCountsandoddCounts, of size 101, filled with zeros. These will store the frequencies of numbers from 1 to 100. - Iterate through the input array
numswith an indexi. - If
iis even, increment the count fornums[i]in theevenCountsarray:evenCounts[nums[i]]++. - If
iis odd, increment the count fornums[i]in theoddCountsarray:oddCounts[nums[i]]++. - Now, we overwrite the original
numsarray with the sorted values. - To fill the even indices (non-decreasing), we iterate through the
evenCountsarray from 1 to 100. For each numberj, we place it into the next available even slot innumsas many times as its count inevenCounts[j]. - To fill the odd indices (non-increasing), we iterate through the
oddCountsarray from 100 down to 1. For each numberj, we place it into the next available odd slot innumsas many times as its count inoddCounts[j].
class Solution { public int[] sortEvenOdd(int[] nums) { int[] evenCounts = new int[101]; int[] oddCounts = new int[101]; for (int i = 0; i < nums.length; i++) { if (i % 2 == 0) { evenCounts[nums[i]]++; } else { oddCounts[nums[i]]++; } } int evenIndex = 0; // Place sorted even-indexed values for (int i = 1; i <= 100; i++) { while (evenCounts[i] > 0) { nums[evenIndex] = i; evenIndex += 2; evenCounts[i]--; } } int oddIndex = 1; // Place sorted odd-indexed values for (int i = 100; i >= 1; i--) { while (oddCounts[i] > 0) { nums[oddIndex] = i; oddIndex += 2; oddCounts[i]--; } } return nums; }}Complexity
Time
O(N + K), where N is the length of `nums` and K is the range of possible values (100 in this case). Populating the count arrays takes O(N). Reconstructing the array involves iterating through the count arrays (O(K)) and placing N elements in total. Since K is a constant, the complexity is effectively linear, O(N).
Space
O(K), where K is the range of values (100). We use two frequency arrays of size K+1. Since K is a constant, the space complexity is O(1).
Trade-offs
Pros
Highly efficient with linear time complexity, which is better than the O(N log N) of comparison-based sorting.
Constant space complexity, as it does not depend on the size of the input array
N.
Cons
This approach is only efficient because the range of values in the input array is small and known. It would be impractical if the numbers could be very large.
Solutions
Solution
class Solution { public int [] sortEvenOdd ( int [] nums ) { int n = nums . length ; int [] a = new int [( n + 1 ) >> 1 ]; int [] b = new int [ n >> 1 ]; for ( int i = 0 , j = 0 ; j < n >> 1 ; i += 2 , ++ j ) { a [ j ] = nums [ i ]; b [ j ] = nums [ i + 1 ]; } if ( n % 2 == 1 ) { a [ a . length - 1 ] = nums [ n - 1 ]; } Arrays . sort ( a ); Arrays . sort ( b ); int [] ans = new int [ n ]; for ( int i = 0 , j = 0 ; j < a . length ; i += 2 , ++ j ) { ans [ i ] = a [ j ]; } for ( int i = 1 , j = b . length - 1 ; j >= 0 ; i += 2 , -- j ) { ans [ i ] = b [ j ]; } return ans ; } }class Solution { public: vector < int > sortEvenOdd ( vector < int >& nums ) { int n = nums . size (); vector < int > a ; vector < int > b ; for ( int i = 0 ; i < n ; ++ i ) { if ( i % 2 == 0 ) a . push_back ( nums [ i ]); else b . push_back ( nums [ i ]); } sort ( a . begin (), a . end ()); sort ( b . begin (), b . end (), greater < int > ()); vector < int > ans ( n ); for ( int i = 0 , j = 0 ; j < a . size (); i += 2 , ++ j ) ans [ i ] = a [ j ]; for ( int i = 1 , j = 0 ; j < b . size (); i += 2 , ++ j ) ans [ i ] = b [ j ]; return ans ; } };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 numsVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.