Scale Engineer

Sort Even and Odd Indices Independently

Easy
#1971Time: 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.1 company
Algorithms
Sorting
Data structures
Array
Companies
Zoho

Prompt

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.
    • For example, if 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.
  2. Sort the values at even indices of nums in 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 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 <= 100
  • 1 <= 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, evenNums and oddNums.
  • Iterate through nums. If the index is even, add the element to evenNums; otherwise, add it to oddNums.
  • Sort evenNums in non-decreasing (ascending) order.
  • Sort oddNums in non-increasing (descending) order.
  • Iterate through nums again. Fill even indices with elements from the sorted evenNums and odd indices with elements from the sorted oddNums.
  • Return the modified nums array.

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.

  1. Initialize two empty lists, evenNums and oddNums.
  2. Iterate through the input array nums with an index i.
  3. If i is even, add nums[i] to the evenNums list.
  4. If i is odd, add nums[i] to the oddNums list.
  5. After populating the lists, sort evenNums in ascending order. In Java, Collections.sort() can be used.
  6. Sort oddNums in descending order. In Java, Collections.sort(oddNums, Collections.reverseOrder()) can be used.
  7. Create two pointers, evenPtr = 0 and oddPtr = 0, to track our position in the sorted lists.
  8. Iterate through the original nums array again from i = 0 to nums.length - 1.
  9. If i is even, set nums[i] = evenNums.get(evenPtr++).
  10. If i is odd, set nums[i] = oddNums.get(oddPtr++).
  11. After the loop, nums will 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.

Solutions

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 ; } }

Video 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.

← Previous

Previous problem

Next →

Next problem