Sort Even and Odd Indices Independently - Practice Coding Problems

Sort Even and Odd Indices Independently - Problem

Array Sorting Easy

You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules:

1. Sort the values at odd indices of nums in non-increasing order.

For example, if nums = [4,1,2,3] before this step, it becomes [4,3,2,1] after. The values at odd indices 1 and 3 are sorted in non-increasing order.

2. Sort the values at even indices of nums in non-decreasing order.

For example, if nums = [4,1,2,3] before this step, it becomes [2,1,4,3] after. The values at even indices 0 and 2 are sorted in non-decreasing order.

Return the array formed after rearranging the values of nums.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,1,2,3]

› Output: [2,3,4,1]

💡 Note: Even indices (0,2): [4,2] → sorted ascending: [2,4]. Odd indices (1,3): [1,3] → sorted descending: [3,1]. Result: [2,3,4,1]

Example 2 — Single Element Groups

$ Input: nums = [2,1]

› Output: [2,1]

💡 Note: Even indices (0): [2] → stays [2]. Odd indices (1): [1] → stays [1]. Result: [2,1]

Example 3 — Larger Array

$ Input: nums = [4,1,2,3,1,2,3,1]

› Output: [1,3,2,3,3,1,4,1]

💡 Note: Even indices (0,2,4,6): [4,2,1,3] → sorted ascending: [1,2,3,4]. Odd indices (1,3,5,7): [1,3,2,1] → sorted descending: [3,3,1,1]. Result: [1,3,2,3,3,1,4,1]

Constraints

1 ≤ nums.length ≤ 100
-100 ≤ nums[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original array with mixed values at even and odd indices

Separate by Index

Group values by even indices (ascending) and odd indices (descending)

Final Result

Reassembled array with sorted values at their respective index types

Key Takeaway

🎯 Key Insight: Separate elements by index parity, sort each group with different orders, then reassemble

Asked in

M Microsoft 15 G Google 12

The key insight is to separate elements by index parity (even/odd), sort each group independently (even ascending, odd descending), then reassemble. Best approach uses separate arrays for extraction and sorting. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Separate Arrays	O(n log n)	O(n)	Extract elements by index parity, sort separately, then merge back
In-Place Sorting	O(n log n)	O(n)	Sort elements in-place by creating temporary arrays for indices

Brute Force - Separate Arrays — Algorithm Steps

Extract all even-indexed elements into one array
Extract all odd-indexed elements into another array
Sort even array in ascending order
Sort odd array in descending order
Place sorted elements back at their original index positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Separate

Extract even and odd indexed elements

Sort

Sort even ascending, odd descending

Merge

Place sorted elements back at original positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare_asc(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int compare_desc(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);
}

int* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* evenElements = (int*)malloc((numsSize + 1) / 2 * sizeof(int));
    int* oddElements = (int*)malloc(numsSize / 2 * sizeof(int));
    int evenCount = 0, oddCount = 0;
    
    // Separate elements by index parity
    for (int i = 0; i < numsSize; i++) {
        if (i % 2 == 0) {
            evenElements[evenCount++] = nums[i];
        } else {
            oddElements[oddCount++] = nums[i];
        }
    }
    
    // Sort even elements in ascending order, odd in descending order
    qsort(evenElements, evenCount, sizeof(int), compare_asc);
    qsort(oddElements, oddCount, sizeof(int), compare_desc);
    
    // Merge back into result array
    int* result = (int*)malloc(numsSize * sizeof(int));
    int evenIdx = 0, oddIdx = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (i % 2 == 0) {
            result[i] = evenElements[evenIdx++];
        } else {
            result[i] = oddElements[oddIdx++];
        }
    }
    
    free(evenElements);
    free(oddElements);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array
    int nums[1000];
    int numsSize = 0;
    char *ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        while (*ptr && *ptr != ']') {
            if (*ptr == ',' || *ptr == ' ') {
                ptr++;
                continue;
            }
            nums[numsSize++] = atoi(ptr);
            while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        }
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting even and odd elements takes O(n/2 log n/2) each, which simplifies to O(n log n)

⚡ Linearithmic

Space Complexity

O(n)

Two additional arrays to store even and odd indexed elements

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~15 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Separate Arrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler