2164. Sort Even and Odd Indices Independently

Problem Description

In this problem, we're given an array nums that we need to rearrange based on certain rules. Specifically, the indices of the array are divided into two groups – odd indices and even indices. Values at odd indices must be sorted in non-increasing order, meaning that each value should be less than or equal to the one before it. Conversely, the values at even indices must be sorted in non-decreasing order, meaning each value should be greater than or equal to the one before it. After applying these sorting rules, the modified array should be returned.

For example, let's say nums is [6, 3, 5, 2, 8, 1]. After sorting, the values at odd indices [3, 2, 1] should be sorted in non-increasing order, and the values at even indices [6, 5, 8] should be sorted in non-decreasing order. The rearranged array will be [5, 3, 6, 2, 8, 1].

Intuition

The solution leverages the fact that we can treat the odd and even indexed elements of the array separately. We can "slice" the original array into two - one containing the even-indexed elements and the other containing the odd-indexed elements. Once we separate the two, we can sort them individually according to the rules: non-decreasing order for even-indexed elements and non-increasing order for odd-indexed elements.

When we sort the even-indexed elements, we extract elements starting at index 0 and then every second element thereafter (using Python's slicing syntax [::2]). For the odd-indexed elements, we start at index 1 and again take every second element (using [1::2]). Once sorted, we can then interleave these two lists back into nums in the original order of odd and even indices to get our final rearranged array.

The implementation of this intuition is straightforward and involves the following steps:

Slice out and sort the even-indexed elements.
Slice out, sort (in reverse order), and reverse the odd-indexed elements, so they become non-increasing.
Merge the sorted even-indexed elements with the sorted odd-indexed ones by interleaving them back into the nums array.
Return the rearranged nums array.

By following this approach, we can arrive at the solution in an efficient and straightforward manner.

Learn more about Sorting patterns.

Solution Approach

The implementation of the solution uses a simple and efficient approach:

Slicing: To separate the even and odd indexed elements, Python's slicing feature is used. The slice nums[::2] takes every element starting from index 0, and continuing in steps of 2 (this gives us all even-indexed elements since Python is 0-indexed). Similarly, nums[1::2] gives us all odd-indexed elements starting at index 1.
Sorting: Python's built-in sorted() function is then used to sort these two subsets. For the even-indexed elements, the function call sorted(nums[::2]) returns a new list where the elements are in ascending (non-decreasing) order. For the odd-indexed elements, the call sorted(nums[1::2], reverse=True) returns them sorted in descending (non-increasing) order due to the reverse=True parameter. It is important to understand that sorting in reverse is the same as sorting normally and then reversing the list, which is exactly what we want for the non-increasing sorting condition.
Merging back into the original array: After sorting, these sorted subsets are interleaved back into nums. The even-indexed elements replace the original even-indexed elements (nums[::2] = a), and the odd-indexed elements replace the original odd-indexed elements (nums[1::2] = b). This step overwrites nums with the newly sorted values while maintaining the original structure of even and odd indices.
Returning the result: Finally, the nums list, now rearranged according to the specified rules, is returned.

The Python slicing feature is particularly useful in this solution because it allows us to easily extract and manipulate elements based on their indices. This approach is efficient since we're operating directly on the slices of the input list, and Python's built-in sorting function is optimized for performance.

Overall, the data structure used is the input list nums itself, which is modified in place to avoid using extra space. The only algorithms used are the slicing and sorting operations provided by Python. This is a great example of a problem that can be solved elegantly with the right choice of built-in functions and language features.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the following array nums:

nums = [4, 1, 2, 3, 6, 5]

We need to sort the even-indexed elements (indices 0, 2, 4; values 4, 2, 6) in non-decreasing order, and the odd-indexed elements (indices 1, 3, 5; values 1, 3, 5) in non-increasing order.

According to the solution approach:

Slicing the even-indexed elements: We extract the even-indexed elements (initially at indices 0, 2, 4), which gives us [4, 2, 6]. Then we sort this slice in non-decreasing order using sorted(nums[::2]).

After sorting, we get:
```
even_sorted = [2, 4, 6]
```
Slicing the odd-indexed elements: We do the same for the odd-indexed elements (initially at indices 1, 3, 5), resulting in [1, 3, 5]. We sort this slice in non-increasing order with sorted(nums[1::2], reverse=True).

After sorting and reversing for non-increasing order, we get:
```
odd_sorted = [5, 3, 1]
```

Merging back into the original array: We now interleave these sorted slices back into the array nums. The even-indexed elements get replaced with even_sorted:

nums[::2] = even_sorted   // nums becomes [2, _, 4, _, 6, _]

And the odd-indexed elements get replaced with odd_sorted:

nums[1::2] = odd_sorted   // nums becomes [2, 5, 4, 3, 6, 1]

Returning the result: The array nums is now properly rearranged:

nums = [2, 5, 4, 3, 6, 1]

The resulting array has the even-indexed elements sorted in non-decreasing order and the odd-indexed elements sorted in non-increasing order, which matches the problem's requirements. This represents our final solution, the rearranged nums array, which can now be returned.

Solution Implementation

1from typing import List
2
3class Solution:
4    def sortEvenOdd(self, nums: List[int]) -> List[int]:
5        # Sort the elements at even indices in non-decreasing order
6        even_index_sorted = sorted(nums[::2])  
7      
8        # Sort the elements at odd indices in non-increasing order (or decreasing order)
9        odd_index_sorted = sorted(nums[1::2], reverse=True)
10
11        # Updating the original list, place the sorted even indices back in their original places
12        nums[::2] = even_index_sorted
13      
14        # Update the original list, place the sorted odd indices back in their positions
15        nums[1::2] = odd_index_sorted
16      
17        return nums  # Return the newly sorted list according to the rules
18
19# The code above defines a method `sortEvenOdd` within a class `Solution`. 
20# The method takes a list `nums` as input and returns a new list in which 
21# the elements at even indices are sorted in non-decreasing order, and the 
22# elements at odd indices are sorted in non-increasing order.
23

1import java.util.Arrays;
2
3class Solution {
4  
5    // The sortEvenOdd method takes an array of integers and sorts the indices of the array such that
6    // all even indices are sorted in ascending order and all odd indices are sorted in descending order.
7    public int[] sortEvenOdd(int[] nums) {
8        int n = nums.length; // The length of the provided array.
9      
10        // Arrays to separately store elements at even and odd indices.
11        int[] evenIndexedElements = new int[(n + 1) >> 1];  // ">> 1" is equivalent to dividing by 2.
12        int[] oddIndexedElements = new int[n >> 1]; // These will be sorted separately.
13      
14        // Split the original array elements into two separate arrays.
15        for (int i = 0, j = 0; j < n / 2; i += 2, ++j) {
16            evenIndexedElements[j] = nums[i];
17            oddIndexedElements[j] = nums[i + 1];
18        }
19      
20        // If the number of elements is odd, the last element belongs to the even index array.
21        if (n % 2 == 1) {
22            evenIndexedElements[evenIndexedElements.length - 1] = nums[n - 1];
23        }
24      
25        // Sort the even and odd indexed elements independently.
26        Arrays.sort(evenIndexedElements); // Sorts in ascending order.
27        Arrays.sort(oddIndexedElements); // To be reversed later.
28
29        // Array to store the final sorted elements.
30        int[] sortedArray = new int[n];
31      
32        // Merge the even indexed elements back into the final array.
33        for (int i = 0, j = 0; j < evenIndexedElements.length; i += 2, ++j) {
34            sortedArray[i] = evenIndexedElements[j];
35        }
36      
37        // Merge and reverse the odd indexed elements into the final array.
38        for (int i = 1, j = oddIndexedElements.length - 1; j >= 0; i += 2, --j) {
39            sortedArray[i] = oddIndexedElements[j]; // Inserting in descending order.
40        }
41      
42        return sortedArray; // Return the final sorted array.
43    }
44}
45

1#include <vector>
2#include <algorithm>
3#include <functional>
4
5class Solution {
6public:
7    // Function to sort even and odd indexed elements in separate order
8    vector<int> sortEvenOdd(vector<int>& nums) {
9        // Retrieve the size of the input vector
10        int size = nums.size();
11      
12        // Vectors to hold even and odd indexed elements
13        vector<int> evenIndexedElements;
14        vector<int> oddIndexedElements;
15      
16        // Iterate over the input vector and distribute elements to even or odd vectors
17        for (int i = 0; i < size; ++i) {
18            if (i % 2 == 0) {
19                // Even indexed elements (0-indexed)
20                evenIndexedElements.push_back(nums[i]);
21            } else {
22                // Odd indexed elements (0-indexed)
23                oddIndexedElements.push_back(nums[i]);
24            }
25        }
26      
27        // Sort even indexed elements in ascending order
28        sort(evenIndexedElements.begin(), evenIndexedElements.end());
29        // Sort odd indexed elements in descending order
30        sort(oddIndexedElements.begin(), oddIndexedElements.end(), greater<int>());
31      
32        // Vector to store the final sorted numbers
33        vector<int> sortedNums(size);
34      
35        // Merge even indexed elements back into `sortedNums`
36        for (int i = 0, j = 0; j < evenIndexedElements.size(); i += 2, ++j) {
37            sortedNums[i] = evenIndexedElements[j];
38        }
39      
40        // Merge odd indexed elements back into `sortedNums`
41        for (int i = 1, j = 0; j < oddIndexedElements.size(); i += 2, ++j) {
42            sortedNums[i] = oddIndexedElements[j];
43        }
44      
45        // Return the final sorted vector
46        return sortedNums;
47    }
48};
49

1function sortEvenOdd(nums: number[]): number[] {
2    // Retrieve the size of the input array
3    const size: number = nums.length;
4  
5    // Arrays to hold even and odd indexed elements
6    let evenIndexedElements: number[] = [];
7    let oddIndexedElements: number[] = [];
8  
9    // Iterate over the input array and distribute elements to even or odd arrays
10    for (let i = 0; i < size; i++) {
11        if (i % 2 === 0) {
12            // Even indexed elements (0-indexed)
13            evenIndexedElements.push(nums[i]);
14        } else {
15            // Odd indexed elements (0-indexed)
16            oddIndexedElements.push(nums[i]);
17        }
18    }
19  
20    // Sort even indexed elements in ascending order
21    evenIndexedElements.sort((a, b) => a - b);
22    // Sort odd indexed elements in descending order
23    oddIndexedElements.sort((a, b) => b - a);
24  
25    // Array to store the final sorted numbers
26    let sortedNums: number[] = new Array(size);
27  
28    // Merge even indexed elements back into `sortedNums`
29    for (let i = 0, j = 0; j < evenIndexedElements.length; i += 2, j++) {
30        sortedNums[i] = evenIndexedElements[j];
31    }
32  
33    // Merge odd indexed elements back into `sortedNums`
34    for (let i = 1, j = 0; j < oddIndexedElements.length; i += 2, j++) {
35        sortedNums[i] = oddIndexedElements[j];
36    }
37  
38    // Return the final sorted array
39    return sortedNums;
40}
41

Time and Space Complexity

The given Python code takes an input list nums and sorts the even-indexed elements in ascending order and the odd-indexed elements in descending order.

Time Complexity

The main operations that determine the time complexity are the two sorted function calls and the slicing operations.

nums[::2] and nums[1::2] are slicing operations that take O(n) time, where n is the length of the list nums. These operations are done twice each, once to create a and b, and once to update nums.
sorted(nums[::2]) sorts the even-indexed elements, which is roughly n/2 elements, leading to a time complexity of O(n/2 * log(n/2)). This simplifies to O(n * log(n)) in terms of big-O notation.
sorted(nums[1::2], reverse=True) sorts the odd-indexed elements, which is also roughly n/2 elements, with the same complexity of O(n * log(n)).

Hence, the overall time complexity of the code snippet is O(n * log(n)), as the sorting operations dominate the time complexity.

Space Complexity

The space complexity considerations include the additional space required for storing the sorted sublists a and b.

a and b each store about n/2 elements, so together they require O(n) space.

However, the sorted function creates a new list, and hence the space complexity for both a and b is O(n) combined since each list gets up to n/2 elements, thus making the space complexity O(n).

The final assignment operations where nums[::2] = a and nums[1::2] = b do not use additional space as they are happening in-place in the original list nums.

Therefore, the overall space complexity of the function is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointers

Two pointers moving in opposite direction

Sliding window

Prefix sum

I don’t know