Wiggle Sort Ii

                                            
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        vector<int> sorted(nums);
        sort(sorted.begin(), sorted.end());
        
        int n = nums.size();
        int mid = (n + 1) / 2;
        
        int largeIdx = n - 1;
        int smallIdx = mid - 1;
        
        for (int i = 0; i < n; i++) {
            nums[i] = i % 2 == 0 ? sorted[smallIdx--] : sorted[largeIdx--];
        }
    }
};

                                            
class Solution {
    public void wiggleSort(int[] nums) {
        int[] sortedNums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sortedNums);
        
        int n = nums.length;
        int mid = (n + 1) / 2;
        int end = n;
        
        for (int i = 0; i < n; i++) {
            nums[i] = i % 2 == 0 ? sortedNums[--mid] : sortedNums[--end];
        }
    }
}

                                            
class Solution(object):
    def wiggleSort(self, nums):
        nums.sort()
        mid = (len(nums) + 1) // 2
        nums[::2], nums[1::2] = nums[:mid][::-1], nums[mid:][::-1]

                                            
public class Solution {
    public void WiggleSort(int[] nums) {
        Array.Sort(nums);
        int[] result = new int[nums.Length];
        int mid = nums.Length / 2;
        if (nums.Length % 2 != 0) mid++;

        int evenIndex = mid - 1;
        int oddIndex = nums.Length - 1;

        for (int i = 0; i < nums.Length; i++) {
            if (i % 2 == 0) {
                result[i] = nums[evenIndex];
                evenIndex--;
            } else {
                result[i] = nums[oddIndex];
                oddIndex--;
            }
        }

        Array.Copy(result, nums, nums.Length);
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify 
nums in-place instead.
 */
var wiggleSort = function(nums) {
    // Sort the nums array
    nums.sort((a, b) => a - b);
    
    const n = nums.length;
    const mid = Math.floor((n + 1) / 2);
    const copy = nums.slice();
    
    let left = mid - 1;
    let right = n - 1;
    
    for (let i = 0; i < n; i++) {
        if (i % 2 === 0) {
            nums[i] = copy[left];
            left--;
        } else {
            nums[i] = copy[right];
            right--;
        }
    }
};

                                            
/**
 Do not return anything, modify nums in-place 
instead.
 */
function wiggleSort(nums: number[]): void {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const mid = Math.floor((n + 1) / 2);
    const result = new Array(n).fill(0);
    
    let left = mid - 1;
    let right = n - 1;
    
    for (let i = 0; i < n; i++) {
        if (i % 2 === 0) {
            result[i] = nums[left];
            left--;
        } else {
            result[i] = nums[right];
            right--;
        }
    }
    
    for (let i = 0; i < n; i++) {
        nums[i] = result[i];
    }
};

                                            
class Solution {
    func wiggleSort(_ nums: inout [Int]) {
        let n = nums.count
        let sortedNums = nums.sorted()
        var low = 0
        var high = n - 1
        var mid = (n - 1) / 2
        
        var result = [Int](repeating: 0, count: n)
        
        for i in 0..<n {
            if i % 2 == 0 {
                nums[i] = sortedNums[mid]
                mid -= 1
            } else {
                nums[i] = sortedNums[high]
                high -= 1
            }
        }
    }
}

                                            
class Solution {
  void wiggleSort(List<int> nums) {
    List<int> sortedNums = List.from(nums)..sort();
    int n = nums.length;
    
    int mid = (n + 1) ~/ 2;
    List<int> small = sortedNums.sublist(0, mid);
    List<int> large = sortedNums.sublist(mid);
    
    int index = 0;
    for (int i = small.length - 1, j = large.length - 1; i >= 0 || j >= 0;) {
      if (i >= 0) {
        nums[index] = small[i];
        i--;
        index++;
      }
      if (j >= 0) {
        nums[index] = large[j];
        j--;
        index++;
      }
    }
  }
}

                                            
import "sort"

func wiggleSort(nums []int) {
    n := len(nums)
    sort.Ints(nums)
    mid := n / 2
    if n%2 == 1 {
        mid++
    }
    copyNums := make([]int, n)
    copy(copyNums, nums)

    index := 0
    for i := 0; i < mid; i++ {
        nums[index] = copyNums[mid-1-i]
        if index+1 < n {
            nums[index+1] = copyNums[n-1-i]
        }
        index += 2
    }
}

                                            
impl Solution {
    pub fn wiggle_sort(nums: &mut Vec<i32>) {
        let n = nums.len();
        
        let mut sorted_nums = nums.clone();
        sorted_nums.sort_unstable();
        
        let mut mid = (n - 1) / 2;
        
        let mut result = vec![0; n];
        
        for i in 0..n {
            result[i] = if i % 2 == 0 {
                mid -= 1;
                sorted_nums[mid + 1]
            } else {
                sorted_nums[n - 1 - (i / 2)]
            };
        }
        
        nums.clone_from_slice(&result);
    }
}

To solve this coding challenge, we need to reorder a given integer array such that the "wiggle" property is satisfied. This property specifies that the elements at even indices should be smaller than their adjacent neighbors, and elements at odd indices should be greater than their neighbors. More precisely, for an array

nums

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

We'll achieve this by splitting the sorted array into two nearly equal halves and then interleaving them while maintaining a reverse order in each half to satisfy the wiggle property.

Step-by-Step Explanation

Sort the Array : Start by sorting the input array. Sorting helps us to easily pick smaller and larger elements to construct the wiggle pattern.
Split the Array : Divide the sorted array into two parts - a left part (which contains the smaller half of the elements) and a right part (which contains the larger half).
Reverse Both Halves : Reverse both halves to ensure we place the largest available value at the required position for the wiggle property.
Interleave the Halves : Interleave elements from both parts in such a way that numbers from the larger half place at odd indices and from the smaller half at even indices.

The methodology is designed to ensure that we maintain the

nums[0] < nums[1] > nums[2]

pattern. Below is the detailed step-by-step pseudocode with explanations:

Pseudocode with Comments

Phase 1: Sort the Input Array

                                            
# Sort the input array to prepare for splitting
Sort(nums_array)

Phase 2: Split the Array

                                            
# Calculate the midpoint to split the array into two halves
mid_point = (Length(nums_array) + 1) // 2

# The left part (small half) is from the start to the middle, reversed
left_half = Reverse(nums_array[0 to mid_point])

# The right part (large half) is from the middle to the end, reversed
right_half = Reverse(nums_array[mid_point to end])

Phase 3: Interleave the Halves

                                            
# Initialize index pointers for interleaving
left_index = 0
right_index = 0

# Initialize an array for the result
result_array = []

# Iterate through the indexes combining both arrays
For each index i in range of Length(nums_array):
If i is even:  # Elements at even indexes come from the left half
result_array.append(left_half[left_index])
left_index += 1
Else:  # Elements at odd indexes come from the right half
result_array.append(right_half[right_index])
right_index += 1

Detailed Steps in Pseudocode

Sort the Input Array :

Begin by sorting the array to have elements in ascending order. This helps in easily sectioning the smallest and largest halves.
Sorting can be done using any efficient sorting algorithm, typically with complexity O(n log n).

Calculate the Midpoint :

Determine the midpoint of the array:
mid = (Length of nums + 1) // 2

. This divides the array into two parts, one part slightly larger or equal depending on whether the total length is odd or even.

Split and Reverse Both Halves :

Split the sorted array into two halves:
left_half

for the smaller values and
right_half

for the bigger values.
Reverse both halves to place the largest available value correctly while interleaving.

Interleave the Halves :

Use two pointers (
left_index

and
right_index

) to iterate through
left_half

and
right_half

.
For each index in the final output array, place elements in such a manner that elements from
left_half

go to even indices and elements from
right_half

go to odd indices.

Following this detailed methodology will ensure the wiggle sort property is satisfied.