Sort Even and Odd Indices Independently

EASY

Description

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

Checkout 2 different approaches to solve Sort Even and Odd Indices Independently. Click on different approaches to view the approach and algorithm in detail.

Separate, Sort, and Merge

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.

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

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Sort Even and Odd Indices Independently. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Sort Even and Odd Indices Independently

Algorithms:

Sorting

Data Structures:

Array

Companies:

Zoho |