Wiggle sort ii

Array Divide and Conquer Greedy Sorting Quickselect

37.0% acceptance

Jan 12, 2026

3242

981

Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3].... You may assume the input array always has a valid answer.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn wiggle_sort(nums: &mut Vec<i32>) {
    let mut sorted = nums.clone();
    sorted.sort();
    
    let n = nums.len();
    let mid = (n + 1) / 2;
    
    let mut left = mid - 1;
    let mut right = n - 1;
    
    for i in 0..n {
      if i % 2 == 0 {
        nums[i] = sorted[left];
        if left > 0 {
          left -= 1;
        }
      } else {
        nums[i] = sorted[right];
        if right > mid {
          right -= 1;
        }
      }
    }
  }
}