Problem Description

You are given a 0-indexed integer array nums. Your task is to rearrange the array by applying two sorting rules based on the index positions:

1. Sort elements at odd indices (1, 3, 5, ...) in non-increasing order (from largest to smallest)

   • For example, if nums = [4, 1, 2, 3], the elements at odd indices are at positions 1 and 3, which are values 1 and 3. After sorting these in non-increasing order, they become 3 and 1, resulting in [4, 3, 2, 1].

2. Sort elements at even indices (0, 2, 4, ...) in non-decreasing order (from smallest to largest)

   • For example, if nums = [4, 1, 2, 3], the elements at even indices are at positions 0 and 2, which are values 4 and 2. After sorting these in non-decreasing order, they become 2 and 4, resulting in [2, 1, 4, 3].

The solution approach extracts elements at odd and even positions separately using Python slicing. nums[::2] gets all elements at even indices, while nums[1::2] gets all elements at odd indices. After sorting each group according to their respective rules, the sorted values are placed back into their original positions in the array using the same slicing technique.

The time complexity is O(n log n) due to the sorting operations, where n is the length of the input array. The space complexity is O(n) for storing the extracted odd and even indexed elements.

Intuition

The key insight is recognizing that elements at odd indices and even indices need to be sorted independently of each other. Since these two groups don't interact during sorting, we can handle them separately.

Think of the array as two interlaced subsequences - one containing all elements at even positions and another containing all elements at odd positions. Instead of trying to sort the entire array with complex comparison logic that checks indices, we can:

1. Separate the problem into two simpler subproblems
2. Sort each group according to its own rule
3. Merge them back into their original positions

This approach naturally leads us to use Python's slicing feature. The notation nums[::2] extracts every second element starting from index 0 (even indices), while nums[1::2] extracts every second element starting from index 1 (odd indices).

Why does this work? Because sorting preserves the relative order within each group. When we extract elements at positions [0, 2, 4, ...], sort them, and place them back at the same positions [0, 2, 4, ...], we maintain the alternating pattern. The same logic applies to odd positions.

The beauty of this solution is that it transforms a seemingly complex rearrangement problem into two standard sorting operations. By decomposing the array based on index parity, we avoid the need for custom sorting comparators or complex index manipulation during the sorting process.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a straightforward four-step process using Python's list slicing capabilities:

Step 1: Extract elements at even indices

a = sorted(nums[::2])

Using slice notation nums[::2], we extract all elements at even positions (0, 2, 4, ...). The ::2 means "start from the beginning, go to the end, with a step of 2". These elements are then sorted in ascending order using Python's built-in sorted() function, which returns a new sorted list.

Step 2: Extract elements at odd indices

b = sorted(nums[1::2], reverse=True)

Similarly, nums[1::2] extracts all elements at odd positions (1, 3, 5, ...). The 1::2 means "start from index 1, go to the end, with a step of 2". We sort these elements in descending order by setting reverse=True in the sorted() function.

Step 3: Place sorted elements back

nums[::2] = a
nums[1::2] = b

Python's slice assignment allows us to replace elements at specific positions. nums[::2] = a replaces all elements at even indices with the sorted values from list a. Similarly, nums[1::2] = b replaces all elements at odd indices with the sorted values from list b.

Step 4: Return the modified array

return nums

The original array nums has been modified in-place with the rearranged values.

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

• Even indices (0, 2): values are [4, 2], sorted becomes [2, 4]
• Odd indices (1, 3): values are [1, 3], sorted in reverse becomes [3, 1]
• Merging back: position 0 gets 2, position 1 gets 3, position 2 gets 4, position 3 gets 1
• Final result: [2, 3, 4, 1]

The elegance of this solution lies in Python's slice notation, which handles the index management automatically, making the code both concise and readable.

Example Walkthrough

Let's walk through the solution with nums = [5, 8, 3, 6, 2, 9]:

Initial array visualization by index:

Index:  0  1  2  3  4  5
Value:  5  8  3  6  2  9
Type:   E  O  E  O  E  O  (E=Even index, O=Odd index)

Step 1: Extract and sort even-indexed elements

• Extract nums[::2] → gets indices 0, 2, 4 → values [5, 3, 2]
• Sort in non-decreasing order → [2, 3, 5]

Step 2: Extract and sort odd-indexed elements

• Extract nums[1::2] → gets indices 1, 3, 5 → values [8, 6, 9]
• Sort in non-increasing order (reverse=True) → [9, 8, 6]

Step 3: Place sorted elements back into original positions

• Even indices (0, 2, 4) get [2, 3, 5]:
  • Index 0 ← 2
  • Index 2 ← 3
  • Index 4 ← 5
• Odd indices (1, 3, 5) get [9, 8, 6]:
  • Index 1 ← 9
  • Index 3 ← 8
  • Index 5 ← 6

Final result:

Index:  0  1  2  3  4  5
Value:  2  9  3  8  5  6

The array transforms from [5, 8, 3, 6, 2, 9] to [2, 9, 3, 8, 5, 6], where even indices [2, 3, 5] are sorted ascending and odd indices [9, 8, 6] are sorted descending.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

The code performs the following operations:

• nums[::2] extracts elements at even indices, which takes O(n/2) = O(n) time
• sorted(nums[::2]) sorts approximately n/2 elements, which takes O((n/2) log(n/2)) = O(n log n) time
• nums[1::2] extracts elements at odd indices, which takes O(n/2) = O(n) time
• sorted(nums[1::2], reverse=True) sorts approximately n/2 elements, which takes O((n/2) log(n/2)) = O(n log n) time
• Assignment operations nums[::2] = a and nums[1::2] = b each take O(n/2) = O(n) time

The dominant operations are the two sorting steps, giving an overall time complexity of O(n log n).

Space Complexity: O(n)

The code creates:

• List a containing approximately n/2 elements from even indices
• List b containing approximately n/2 elements from odd indices

Together, these two lists store all n elements, resulting in a space complexity of O(n).

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

Common Pitfalls

1. Misunderstanding Index vs. Position

A frequent mistake is confusing the index-based sorting requirement with value-based sorting. The problem asks to sort elements at even/odd indices, not elements that are even/odd numbers.

Incorrect approach:

# Wrong: This sorts based on whether the VALUE is even or odd
evens = sorted([x for x in nums if x % 2 == 0])
odds = sorted([x for x in nums if x % 2 == 1], reverse=True)

Correct approach:

# Right: This sorts based on the INDEX position
even_indices = sorted(nums[::2])  # Elements at positions 0, 2, 4...
odd_indices = sorted(nums[1::2], reverse=True)  # Elements at positions 1, 3, 5...

2. Attempting Manual Index Reconstruction

Some developers try to manually merge the sorted arrays back together, which is error-prone and unnecessarily complex.

Inefficient approach:

result = []
for i in range(len(nums)):
    if i % 2 == 0:
        result.append(even_sorted[i // 2])
    else:
        result.append(odd_sorted[i // 2])
return result

Better approach: Use slice assignment to directly place elements back:

nums[::2] = even_sorted
nums[1::2] = odd_sorted
return nums

3. Creating Unnecessary Copies

When the problem allows in-place modification, creating a new array wastes space.

Space-inefficient:

result = [0] * len(nums)
# ... populate result array
return result

Space-efficient:

# Modify nums directly using slice assignment
nums[::2] = sorted(nums[::2])
nums[1::2] = sorted(nums[1::2], reverse=True)
return nums

4. Forgetting Edge Cases

Not handling arrays with only one element or empty arrays properly.

Solution: The slice notation naturally handles these cases:

• For nums = []: Both nums[::2] and nums[1::2] return empty lists
• For nums = [5]: nums[::2] returns [5], nums[1::2] returns []
• The code works correctly without special case handling

5. Incorrect Slice Notation

Using wrong slice syntax can lead to unexpected results.

Common mistakes:

nums[0::2]  # This is actually correct for even indices (same as nums[::2])
nums[2::2]  # Wrong: This starts from index 2, missing index 0
nums[1:2]   # Wrong: This only gets one element at index 1

Correct notation:

nums[::2]   # All even indices: 0, 2, 4, ...
nums[1::2]  # All odd indices: 1, 3, 5, ...