algoadvance

Leetcode 2164. Sort Even and Odd Indices Independently

Problem Statement

You are given a 0-indexed integer array nums. Reorder the array so that:

• Odd indices (1, 3, 5, ...) are sorted in descending order.
• Even indices (0, 2, 4, ...) are sorted in ascending order.

Return the reordered array.

Clarifying Questions

1. Q: Do we need to maintain the original indices after sorting?
   • A: Yes, indices remain the same. Only elements at odd and even indices are sorted independently.
2. Q: Can the array contain negative numbers?
   • A: Yes, the array can contain negative numbers.
3. Q: What is the maximum size of the array we can expect?
   • A: The problem constraints should mention this, but typically, you can expect the size to be up to 10^5.

Strategy

1. Extract Odd and Even Indexed Elements:
   • Traverse the array and separate the elements at odd and even indices.
2. Sort the Extracted Elements:
   • Sort the even-indexed elements in ascending order.
   • Sort the odd-indexed elements in descending order.
3. Reconstruct the Original Array:
   • Place the sorted elements back into their original positions.

Code

#include <vector>
#include <algorithm>

std::vector<int> sortEvenOdd(std::vector<int>& nums) {
    std::vector<int> evenElements;
    std::vector<int> oddElements;
    
    // Extract even-indexed and odd-indexed elements
    for (int i = 0; i < nums.size(); ++i) {
        if (i % 2 == 0) {
            evenElements.push_back(nums[i]);
        } else {
            oddElements.push_back(nums[i]);
        }
    }
    
    // Sort the even-indexed elements in ascending order
    std::sort(evenElements.begin(), evenElements.end());
    
    // Sort the odd-indexed elements in descending order
    std::sort(oddElements.begin(), oddElements.end(), std::greater<int>());
    
    // Place the sorted elements back in the array
    int evenIndex = 0, oddIndex = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (i % 2 == 0) {
            nums[i] = evenElements[evenIndex++];
        } else {
            nums[i] = oddElements[oddIndex++];
        }
    }
    
    return nums;
}

Time Complexity

• Extraction: O(n), where n is the size of the array.
• Sorting: O((n/2)log(n/2)) for even indices + O((n/2)log(n/2)) for odd indices.
  • This simplifies to O(n log n) because sorting dominates the time complexity.
• Reconstruction: O(n).

Overall, the time complexity is O(n log n) due to the sorting steps. The space complexity is O(n) for storing the odd and even indexed elements separately.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?