We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sort Even and Odd Indices Independently

Number: 2283

Difficulty: Easy

Paid? No

Companies: Zoho, Bloomberg

Problem Description

Given a 0-indexed integer array nums, rearrange its elements so that:

  • The values at odd indices are sorted in non-increasing (descending) order.
  • The values at even indices are sorted in non-decreasing (ascending) order. Return the resultant array after rearranging.

Key Insights

  • Separate the elements of nums into two groups based on index parity (even and odd).
  • Sort the even-index values in ascending order.
  • Sort the odd-index values in descending order.
  • Merge the two sorted groups back into the result array using their original indices.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting both subarrays, where n is the number of elements.
Space Complexity: O(n) for storing the separated even and odd indexed elements.

Solution

We first traverse the nums array and store elements at even and odd indices into separate lists. We then sort the even-index list in ascending order and the odd-index list in descending order. Finally, we iterate through the original array indices and replace each element with the next sorted value from the corresponding list. This approach allows us to independently sort the subarrays before combining them into the final result.

Code Solutions

# Python Solution
def sort_even_odd_indices(nums):
    # Extract even-index elements and odd-index elements
    even_nums = [nums[i] for i in range(len(nums)) if i % 2 == 0]
    odd_nums = [nums[i] for i in range(len(nums)) if i % 2 != 0]
    
    # Sort even-index values in non-decreasing (ascending) order
    even_nums.sort()
    # Sort odd-index values in non-increasing (descending) order
    odd_nums.sort(reverse=True)
    
    # Prepare indices for even and odd lists
    even_index, odd_index = 0, 0
    
    # Reconstruct the sorted array by picking from even or odd lists
    for i in range(len(nums)):
        if i % 2 == 0:
            nums[i] = even_nums[even_index]
            even_index += 1
        else:
            nums[i] = odd_nums[odd_index]
            odd_index += 1
            
    return nums

# Example usage:
print(sort_even_odd_indices([4,1,2,3]))  # Expected output: [2,3,4,1]
← Back to All Questions