2164. Sort Even and Odd Indices Independently

Description

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

Solutions

Solution 1: Sorting

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 \(\textit{nums}\).

Python3JavaC++GoTypeScript

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 nums

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.rbegin(), b.rend());
        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;
    }
};

func sortEvenOdd(nums []int) []int {
    n := len(nums)
    var a []int
    var b []int
    for i, v := range nums {
        if i%2 == 0 {
            a = append(a, v)
        } else {
            b = append(b, v)
        }
    }
    ans := make([]int, n)
    sort.Ints(a)
    sort.Slice(b, func(i, j int) bool {
        return b[i] > b[j]
    })
    for i, j := 0, 0; j < len(a); i, j = i+2, j+1 {
        ans[i] = a[j]
    }
    for i, j := 1, 0; j < len(b); i, j = i+2, j+1 {
        ans[i] = b[j]
    }
    return ans
}

function sortEvenOdd(nums: number[]): number[] {
    const n = nums.length;
    const a: number[] = [];
    const b: number[] = [];
    for (let i = 0; i < n; ++i) {
        if (i % 2 === 0) {
            a.push(nums[i]);
        } else {
            b.push(nums[i]);
        }
    }
    a.sort((x, y) => x - y);
    b.sort((x, y) => y - x);
    const ans: number[] = [];
    for (let i = 0, j = 0; j < a.length; i += 2, ++j) {
        ans[i] = a[j];
    }
    for (let i = 1, j = 0; j < b.length; i += 2, ++j) {
        ans[i] = b[j];
    }
    return ans;
}

Comments