Wiggle Sort II - Practice Coding Problems

Wiggle Sort II - Problem

Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]...

The wiggle pattern means elements at even indices should be smaller than their next element, and elements at odd indices should be larger than their next element.

You may assume the input array always has a valid answer.

Input & Output

Example 1 — Basic Wiggle Pattern

$ Input: nums = [1,5,1,1,6,4]

› Output: [1,6,1,5,1,4]

💡 Note: One possible wiggle sort: 1 < 6 > 1 < 5 > 1 < 4. Each even index is smaller than the next odd index, and each odd index is larger than the next even index.

Example 2 — Small Array

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

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

💡 Note: After sorting [1,1,2,2,3,3], we arrange as wiggle: 2 < 3 > 1 < 3 > 1 < 2. Smaller elements at even positions, larger at odd positions.

Example 3 — Minimum Size

$ Input: nums = [1,2]

› Output: [1,2]

💡 Note: For two elements, we need nums[0] < nums[1], so [1,2] already satisfies the wiggle condition.

Constraints

1 ≤ nums.length ≤ 5 × 10⁴
0 ≤ nums[i] ≤ 5000
It is guaranteed that there will be an answer for the given input.

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original unsorted array [1,5,1,1,6,4]

Wiggle Requirement

Need pattern: small < large > small < large...

Output Result

Wiggle sorted: [1,6,1,5,1,4]

Key Takeaway

🎯 Key Insight: Use virtual indexing to map wiggle positions to sorted order without extra space

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is to arrange elements in a wiggle pattern where nums[0] < nums[1] > nums[2] < nums[3]... The optimal approach uses virtual indexing with quickselect to achieve O(n) time and O(1) space by directly placing elements without extra sorting. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Virtual Indexing with Quickselect	O(n)	O(1)	Use quickselect to find median, then virtual indexing for O(1) space placement
Sort and Rearrange	O(n log n)	O(n)	Sort array, then rearrange by placing elements alternately

Virtual Indexing with Quickselect — Algorithm Steps

Find median using quickselect
Use virtual indexing to map wiggle positions
Place elements directly using the mapping

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Median

Use quickselect to find the median element

Virtual Mapping

Map wiggle indices to virtual sorted positions

In-place Partition

Partition around median using virtual indices

Code -

solution.c — C

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

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

int virtualIndex(int i, int n) {
    return (1 + 2 * i) % (n | 1);
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void solution(int* nums, int numsSize) {
    // Use nth_element equivalent - partial sort to find median
    int* temp = malloc(numsSize * sizeof(int));
    memcpy(temp, nums, numsSize * sizeof(int));
    qsort(temp, numsSize, sizeof(int), compare);
    int median = temp[numsSize / 2];
    free(temp);
    
    // Three-way partition using virtual indexing
    int i = 0, j = 0, k = numsSize - 1;
    while (j <= k) {
        int vi = virtualIndex(i, numsSize);
        int vj = virtualIndex(j, numsSize);
        int vk = virtualIndex(k, numsSize);
        
        if (nums[vj] > median) {
            swap(&nums[vi], &nums[vj]);
            i++;
            j++;
        } else if (nums[vj] < median) {
            swap(&nums[vj], &nums[vk]);
            k--;
        } else {
            j++;
        }
    }
}

int main() {
    srand(time(NULL));
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[100], numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    solution(nums, numsSize);
    
    printf("[");
    for (int i = 0; i < numsSize; i++) {
        printf("%d", nums[i]);
        if (i < numsSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Quickselect takes O(n) average time, virtual indexing placement is O(n)

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables for indexing, modifies array in-place

✓ Linear Space

87.0K Views

Medium Frequency

~25 min Avg. Time

1.5K 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

Virtual Indexing with Quickselect — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler