LeetCode 2164 - Sort Even and Odd Indices Independently

The problem asks us to take an integer array nums and sort its elements based on their indices in two separate ways: the elements at even indices should be sorted in non-decreasing order, and the elements at odd indices should be sorted in non-increasing order.

leetcodeeasyarraysorting

LeetCode Problem 2164

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

Problem Understanding

The problem asks us to take an integer array nums and sort its elements based on their indices in two separate ways: the elements at even indices should be sorted in non-decreasing order, and the elements at odd indices should be sorted in non-increasing order. The array is 0-indexed, so index 0 is considered even, index 1 is odd, index 2 is even, and so on.

The input nums represents a list of integers that need rearrangement according to the index-based sorting rules. The output is the array after performing the two separate sorts while keeping the elements at their respective index parity positions.

The constraints are small: the array length is at most 100, and each element ranges between 1 and 100. This ensures that even simple sorting-based solutions are efficient.

Important edge cases include arrays of length 1 or 2, arrays where all odd or all even indices contain the same value, and arrays already sorted according to one or both rules. The problem guarantees that the array is non-empty and contains only positive integers.

Approaches

Brute Force

A naive approach is to iterate over the array, separate the even-indexed elements and odd-indexed elements into two separate arrays, sort each array according to the required order, and then merge them back into their original positions.

This approach works because sorting the two groups independently guarantees that the final array meets the required conditions. For small arrays, this is perfectly acceptable.

Optimal Insight

Given the constraints (nums.length <= 100), the brute force solution is effectively optimal because sorting two small arrays of size roughly n/2 is fast. No further optimization is necessary beyond using the built-in sorting functions.

Approach Time Complexity Space Complexity Notes
Brute Force / Optimal O(n log n) O(n) Separate even and odd indices, sort, then merge back. Optimal for n <= 100

Algorithm Walkthrough

  1. Initialize two empty lists: one for even-indexed elements (even_nums) and one for odd-indexed elements (odd_nums).
  2. Iterate over the original array nums. If the index i is even, append nums[i] to even_nums; otherwise, append it to odd_nums.
  3. Sort even_nums in non-decreasing order. This ensures that even-indexed positions will be sorted ascending.
  4. Sort odd_nums in non-increasing order. This ensures that odd-indexed positions will be sorted descending.
  5. Initialize a new array or reuse the original array nums.
  6. Iterate over nums again, and for each index i, place elements from even_nums if i is even, and from odd_nums if i is odd, maintaining the sorted order.
  7. Return the modified array.

Why it works: Sorting each parity group independently ensures that the relative order within even and odd indices follows the specified sorting rules. By mapping the sorted values back to their original parity positions, we maintain the index constraints.

Python Solution

from typing import List

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:
        even_nums = [nums[i] for i in range(0, len(nums), 2)]
        odd_nums = [nums[i] for i in range(1, len(nums), 2)]
        
        even_nums.sort()
        odd_nums.sort(reverse=True)
        
        result = []
        even_idx, odd_idx = 0, 0
        for i in range(len(nums)):
            if i % 2 == 0:
                result.append(even_nums[even_idx])
                even_idx += 1
            else:
                result.append(odd_nums[odd_idx])
                odd_idx += 1
        
        return result

Implementation Explanation: We first extract even and odd indexed elements, sort them as required, and then merge them back by maintaining two separate pointers for even and odd arrays. This ensures each element goes to the correct index while following the sorting rules.

Go Solution

import "sort"

func sortEvenOdd(nums []int) []int {
    evenNums := []int{}
    oddNums := []int{}
    
    for i, val := range nums {
        if i%2 == 0 {
            evenNums = append(evenNums, val)
        } else {
            oddNums = append(oddNums, val)
        }
    }
    
    sort.Ints(evenNums)
    sort.Sort(sort.Reverse(sort.IntSlice(oddNums)))
    
    result := make([]int, len(nums))
    evenIdx, oddIdx := 0, 0
    
    for i := range nums {
        if i%2 == 0 {
            result[i] = evenNums[evenIdx]
            evenIdx++
        } else {
            result[i] = oddNums[oddIdx]
            oddIdx++
        }
    }
    
    return result
}

Go-Specific Notes: We use sort.Ints for ascending sort and sort.Sort(sort.Reverse(...)) for descending sort. Slices in Go make it easy to dynamically build even and odd arrays, and we allocate a fixed-size result slice to avoid multiple appends.

Worked Examples

Example 1: nums = [4,1,2,3]

  1. Extract even indices: [4,2] → sort ascending → [2,4]
  2. Extract odd indices: [1,3] → sort descending → [3,1]
  3. Merge back by index:
  • index 0 → 2
  • index 1 → 3
  • index 2 → 4
  • index 3 → 1

Result: [2,3,4,1]

Example 2: nums = [2,1]

  1. Extract even indices: [2] → [2]
  2. Extract odd indices: [1] → [1]
  3. Merge back → [2,1]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting two arrays of size n/2 takes O(n log n)
Space O(n) We create separate arrays for even and odd elements

The overall complexity is efficient for n <= 100, and the solution comfortably fits within typical constraints for LeetCode easy problems.

Test Cases

# Provided examples
assert Solution().sortEvenOdd([4,1,2,3]) == [2,3,4,1]  # mixed even/odd indices
assert Solution().sortEvenOdd([2,1]) == [2,1]          # single odd/even pair

# Edge cases
assert Solution().sortEvenOdd([1]) == [1]              # single element
assert Solution().sortEvenOdd([5,3,2,4,1]) == [1,4,2,3,5]  # odd length array
assert Solution().sortEvenOdd([1,1,1,1,1,1]) == [1,1,1,1,1,1]  # all same elements
assert Solution().sortEvenOdd([100,1,50,2,25,3]) == [25,3,50,2,100,1]  # larger numbers
Test Why
[4,1,2,3] Basic example with both even and odd indices requiring sorting
[2,1] Minimal case with one odd and one even index
[1] Single element edge case
[5,3,2,4,1] Odd-length array to ensure correct index mapping
[1,1,1,1,1,1] All elements identical, should return same array
[100,1,50,2,25,3] Larger values with alternating sort requirements

Edge Cases

Single Element: Arrays with only one element do not require sorting. The algorithm handles this by extracting one-element arrays and merging them back without changes.

All Elements Same: If all elements are equal, sorting still occurs but results in the same array. This tests that the implementation does not inadvertently reorder identical elements incorrectly.

Odd-Length Arrays: Arrays with an odd number of elements ensure that the last index may be even or odd. Our approach handles this by using index-based iteration with separate pointers, ensuring no index is skipped.

Already Sorted: If an array is already sorted according to the rules, the algorithm should still produce the same array. This validates that the sort operations and merging logic do not disrupt already sorted parity groups.