Wave Pattern Rearrangement

Given an array of integers nums, rearrange the elements in-place so that they form an alternating high-low wave pattern. Specifically, the reordered array must satisfy the following strict inequalities at every adjacent position:

nums[0] < nums[1] > nums[2] < nums[3] > nums[4] < nums[5] ...

In other words:

• Elements at odd indices (1, 3, 5, ...) must be strictly greater than their immediate neighbors on both sides.
• Elements at even indices (0, 2, 4, ...) must be strictly less than their immediate neighbors.

This creates a distinctive wave-like pattern where values alternately rise and fall, resembling peaks and valleys when visualized graphically.

Key Requirements:

• The rearrangement must be performed in-place, modifying the original array directly.
• You are guaranteed that a valid wave arrangement always exists for the given input.
• Multiple valid answers may exist; any arrangement satisfying the wave pattern condition is acceptable.

Visualization:

Original: [1, 5, 1, 1, 6, 4]

Valid Wave Pattern:
       6       5
      / \     / \
     1   1   1   4
       peaks at odd indices (1, 3, 5)
       valleys at even indices (0, 2, 4)

This problem challenges you to think about element placement strategies, median-finding algorithms, and space-efficient transformations.

nums = [1, 5, 1, 1, 6, 4]

[1, 6, 1, 5, 1, 4]

nums = [1, 3, 2, 2, 3, 1]

[2, 3, 1, 3, 1, 2]

nums = [1, 2, 3, 4, 5]

[3, 5, 2, 4, 1]