Skip to content

2164. Sort Even and Odd Indices Independently 👍

Approach 1: Counting Sort

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  vector<int> sortEvenOdd(vector<int>& nums) {
    const int n = nums.size();
    vector<int> ans(n);
    vector<int> evenCount(101);
    vector<int> oddCount(101);

    for (int i = 0; i < n; ++i)
      if (i & 1)
        ++oddCount[nums[i]];
      else
        ++evenCount[nums[i]];

    int ansIndex = 0;
    for (int i = 1; i < 101; ++i)
      while (evenCount[i]--) {
        ans[ansIndex] = i;
        ansIndex += 2;
      }

    ansIndex = 1;
    for (int i = 100; i > 0; --i)
      while (oddCount[i]--) {
        ans[ansIndex] = i;
        ansIndex += 2;
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int[] sortEvenOdd(int[] nums) {
    final int n = nums.length;
    int[] ans = new int[n];
    int[] evenCount = new int[101];
    int[] oddCount = new int[101];

    for (int i = 0; i < n; ++i)
      if ((i & 1) == 1)
        ++oddCount[nums[i]];
      else
        ++evenCount[nums[i]];

    int ansIndex = 0;
    for (int i = 1; i < 101; ++i)
      while (evenCount[i]-- > 0) {
        ans[ansIndex] = i;
        ansIndex += 2;
      }

    ansIndex = 1;
    for (int i = 100; i > 0; --i)
      while (oddCount[i]-- > 0) {
        ans[ansIndex] = i;
        ansIndex += 2;
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def sortEvenOdd(self, nums: List[int]) -> List[int]:
    ans = [0] * len(nums)
    evenCount = collections.Counter(nums[::2])
    oddCount = collections.Counter(nums[1::2])

    ansIndex = 0
    for i in range(1, 101):
      while evenCount[i] > 0:
        ans[ansIndex] = i
        ansIndex += 2
        evenCount[i] -= 1

    ansIndex = 1
    for i in range(100, 0, -1):
      while oddCount[i] > 0:
        ans[ansIndex] = i
        ansIndex += 2
        oddCount[i] -= 1

    return ans

Approach 2: Slicing

  • Time: $O(n\log n)$
  • Space: $O(n)$
1
2
3
4
5
class Solution:
  def sortEvenOdd(self, nums: List[int]) -> List[int]:
    nums[::2] = sorted(nums[::2])
    nums[1::2] = sorted(nums[1::2])[::-1]
    return nums