algoadvance

Leetcode 2164. Sort Even and Odd Indices Independently

Problem Statement

The problem is to sort the elements at even indices and odd indices of an array independently. Given an integer array nums, you need to perform the following operations:

  1. Sort the elements at even indices (0-based) in increasing order.
  2. Sort the elements at odd indices (0-based) in decreasing order.

Return the array after performing the above operations.

Clarifying Questions

  1. What is the range of the array size?
    • The array size can range from 1 to 1000.
  2. What is the range of integer values within the array?
    • The integer values can range from -1000 to 1000.
  3. What should be done if the array has only one element?
    • No sorting is needed; return the array as is.
  4. Are there any constraints on the elements apart from the given ranges?
    • No other specific constraints were mentioned.

Strategy

  1. Separate the elements at even and odd indices into two lists.
  2. Sort the list of even indices in ascending order.
  3. Sort the list of odd indices in descending order.
  4. Merge these two sorted lists back into the original array positions.

Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SortEvenOddIndices {

    public int[] sortEvenOdd(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums; // Edge case for null or single-element arrays
        }

        List<Integer> evenIndices = new ArrayList<>();
        List<Integer> oddIndices = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                evenIndices.add(nums[i]);
            } else {
                oddIndices.add(nums[i]);
            }
        }

        Collections.sort(evenIndices);
        Collections.sort(oddIndices, Collections.reverseOrder());

        int evenIndex = 0;
        int oddIndex = 0;

        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                nums[i] = evenIndices.get(evenIndex++);
            } else {
                nums[i] = oddIndices.get(oddIndex++);
            }
        }

        return nums;
    }

    // Example usage
    public static void main(String[] args) {
        SortEvenOddIndices solution = new SortEvenOddIndices();
        int[] nums = {4, 1, 2, 3};
        int[] sortedNums = solution.sortEvenOdd(nums);
        for (int num : sortedNums) {
            System.out.print(num + " ");
        }
    }
}

Time Complexity

Therefore, the overall time complexity is (O(n \log n)).

Space Complexity

The space complexity is (O(n)) for storing the even and odd indexed elements separately.

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