Wiggle Sort

Medium

Google

2 views

Topics:

Arrays

Wiggle Sort

You are given an unsorted array of integers called nums. Your task is to reorder the elements of the array in-place such that it satisfies the following "wiggle" property:

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

In other words, the elements should alternate between being less than or equal to and greater than or equal to their adjacent elements.

Constraints:

You must modify the array in-place. Do not create a new array.
The array can contain duplicate elements.
The array can be of any size (including empty).
You can assume the input will always have a valid output.

Example 1:

Input: nums = [3, 5, 2, 1, 6, 4]
Output: One possible solution: [3, 5, 1, 6, 2, 4]
Explanation:  The output satisfies the wiggle property: 3 <= 5 >= 1 <= 6 >= 2 <= 4

Example 2:

Input: nums = [6, 6, 5, 6, 3, 8]
Output: One possible solution: [6, 6, 5, 6, 3, 8]
Explanation: The output satisfies the wiggle property: 6 <= 6 >= 5 <= 6 >= 3 <= 8

Example 3:

Input: nums = [1, 2, 3, 4, 5]
Output: One possible solution: [1, 2, 3, 4, 5]
Explanation: The output satisfies the wiggle property: 1 <= 2 >= 3 <= 4 >= 5

Your Task:

Write a function that takes an unsorted array nums as input and modifies it in-place to satisfy the wiggle property described above. Can you do it in O(n) time?

Wiggle Sort

Medium

Google

2 views

Topics:

Arrays

Wiggle Sort

You are given an unsorted array of integers called nums. Your task is to reorder the elements of the array in-place such that it satisfies the following "wiggle" property:

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

In other words, the elements should alternate between being less than or equal to and greater than or equal to their adjacent elements.

Constraints:

You must modify the array in-place. Do not create a new array.
The array can contain duplicate elements.
The array can be of any size (including empty).
You can assume the input will always have a valid output.

Example 1:

Input: nums = [3, 5, 2, 1, 6, 4]
Output: One possible solution: [3, 5, 1, 6, 2, 4]
Explanation:  The output satisfies the wiggle property: 3 <= 5 >= 1 <= 6 >= 2 <= 4

Example 2:

Input: nums = [6, 6, 5, 6, 3, 8]
Output: One possible solution: [6, 6, 5, 6, 3, 8]
Explanation: The output satisfies the wiggle property: 6 <= 6 >= 5 <= 6 >= 3 <= 8

Example 3:

Input: nums = [1, 2, 3, 4, 5]
Output: One possible solution: [1, 2, 3, 4, 5]
Explanation: The output satisfies the wiggle property: 1 <= 2 >= 3 <= 4 >= 5

Your Task:

Write a function that takes an unsorted array nums as input and modifies it in-place to satisfy the wiggle property described above. Can you do it in O(n) time?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array contain duplicate numbers?
Can the array contain negative numbers or zero?
What should I return if the input array is empty or null?
Is any specific wiggle pattern acceptable (e.g., nums[i] <= nums[i+1] >= nums[i+2] or nums[i] >= nums[i+1] <= nums[i+2])?
Is it acceptable to modify the input array in place, or should I return a new array?

Brute Force Solution

Approach

The brute force approach to wiggle sort is all about trying out every possible arrangement of the numbers we have. We check each arrangement to see if it follows the wiggle pattern. If it does, we've found a solution.

Here's how the algorithm would work step-by-step:

Start by listing all the possible ways you could arrange the numbers.
Take the first arrangement and check if the numbers alternate between being smaller and larger than their neighbors.
If the arrangement follows this 'wiggle' pattern, then we've found one possible solution.
If it doesn't, move on to the next possible arrangement.
Keep checking each arrangement until you find one that follows the 'wiggle' pattern.
If you go through all possible arrangements without finding one that works, then there might be no solution.

Code Implementation

import itertools

def wiggle_sort_brute_force(numbers):

    # Generate all possible permutations of the input list
    for permutation in itertools.permutations(numbers):
        
        # Convert the permutation tuple to a list for easier manipulation
        list_permutation = list(permutation)
        
        # Check if the current permutation satisfies the wiggle condition
        if is_wiggle_sort(list_permutation):
            return list_permutation

    return None

def is_wiggle_sort(numbers_list):
    # An empty or single element list is considered wiggle sorted
    if len(numbers_list) < 2:
        return True

    # Check for wiggle pattern violations
    for index in range(len(numbers_list) - 1):
        #Even indices should be less than the next element
        if index % 2 == 0:

            if numbers_list[index] >= numbers_list[index + 1]:
                return False
        #Odd indices should be greater than the next element
        else:
            if numbers_list[index] <= numbers_list[index + 1]:
                return False

    return True

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force approach involves generating all possible permutations of the input array of size n. Generating all permutations takes O(n!) time. For each permutation generated, we need to check if it satisfies the wiggle property. Checking the wiggle property requires iterating through the array once, taking O(n) time. Therefore, the overall time complexity is O(n! * n), as we generate n! permutations and for each one, we perform a check that takes n operations.

Space Complexity

O(N!) – The brute force approach generates all possible permutations of the input array. Generating all permutations requires storing the current permutation being built, and potentially storing all permutations found so far. The number of possible permutations for an array of size N is N!. Therefore, the space needed to store these permutations grows factorially with N. In the worst case, the algorithm might need to hold all possible arrangements in memory before finding a wiggle sort. Thus, the space complexity is O(N!).

Optimal Solution

Approach

The core idea behind Wiggle Sort is to arrange numbers so that they alternate between being smaller and larger than their neighbors. The optimal solution figures out the middle number and then cleverly places the smaller and larger numbers around it to satisfy the alternating pattern.

Here's how the algorithm would work step-by-step:

First, find the middle number in the entire group of numbers. Think of it as finding the median.
Imagine the numbers on a number line. Now, put all the numbers bigger than the middle number on the 'odd' spots, starting from the back.
Next, put all the numbers smaller than the middle number on the 'even' spots, also starting from the back.
Put the middle numbers in the remaining spots. They'll naturally fill in any gaps left after placing the smaller and larger numbers.
By placing the numbers in this specific order, you ensure that the numbers wiggle – smaller, larger, smaller, larger – all the way through the group.

Code Implementation

def wiggle_sort(numbers):
    array_length = len(numbers)
    median_value = sorted(numbers)[array_length // 2]

    less_than_pointer = 0
    greater_than_pointer = array_length - 1
    current_index = 0

    # Custom in-place 'virtual' indexing.
    def get_virtual_index(index):
        return (2 * index + 1) % (array_length | 1)

    while current_index <= greater_than_pointer:
        virtual_index = get_virtual_index(current_index)

        if numbers[virtual_index] > median_value:
            numbers[virtual_index], numbers[get_virtual_index(less_than_pointer)] = \
                numbers[get_virtual_index(less_than_pointer)], numbers[virtual_index]

            less_than_pointer += 1
            current_index += 1

        elif numbers[virtual_index] < median_value:

            numbers[virtual_index], numbers[get_virtual_index(greater_than_pointer)] = \
                numbers[get_virtual_index(greater_than_pointer)], numbers[virtual_index]

            greater_than_pointer -= 1

        else:
            # Move to the next index if the current value is equal to the median.
            current_index += 1

# Partition to arrange larger numbers to odd indices
# and smaller ones to even indices

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this wiggle sort algorithm is finding the median of the input array of size n. A typical efficient algorithm for finding the median involves sorting the array (or using a selection algorithm). Sorting algorithms generally have a time complexity of O(n log n). The subsequent placement steps, while involving iterations over the array, are linear, O(n). Therefore, the overall time complexity is determined by the median finding step, resulting in O(n log n).

Space Complexity

O(1) – The provided steps for Wiggle Sort primarily involve in-place rearrangements of the input array. While finding the middle number (median) might conceptually involve sorting which can require auxiliary space in some implementations, the plain English explanation does not explicitly mention creating any additional data structures like temporary arrays, hash maps, or recursion. Therefore, assuming an in-place median finding algorithm (or a selection algorithm with constant space) is used, the space complexity is dominated by a few index variables. These variables consume constant space regardless of the input size N, leading to O(1) auxiliary space.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException, depending on the requirements, after checking for null or zero length.
Input array with only one element	Return the input array as is, because an array with one element is already trivially wiggle-sorted.
Array with all identical elements	The solution must ensure alternating comparisons still lead to index swapping, potentially requiring a stable swap implementation to prevent infinite loops if not using median approach.
Array with already wiggle-sorted elements	The algorithm should still execute correctly and produce a wiggle-sorted array (which would be the same as the input).
Array with large positive or negative numbers (potential integer overflow during calculations)	Use long data types to perform any intermediate calculations, particularly when finding the median, or check if result exceeds max int.
Array with duplicate values concentrated at one end	Sorting-based or median-finding approaches should correctly distribute the duplicate values to achieve the wiggle sort pattern.
Very large array (performance considerations)	Select an algorithm with O(n log n) time complexity (e.g., sorting) or potentially O(n) with median selection, considering memory usage.
Array containing both positive and negative numbers with extreme values	The comparison logic must correctly handle mixed signs and potential for overflow during comparison if not handled by the median approach.