280. Wiggle Sort

Problem Description

The problem requires us to reorder an array nums so that adjacent elements follow a specific pattern: the element at an even index is not greater than the next element, and the element at an odd index is not less than the previous element. In other words, the elements should alternate between being less than or equal to and being greater than or equal to their neighboring elements, creating a "wiggle" pattern. This needs to be done in a way that modifies the array in-place, meaning without using an additional array to output the result. The pattern can be described as nums[0] <= nums[1] >= nums[2] <= nums[3]... for the entire array. It is guaranteed that there is at least one way to rearrange the array to satisfy the condition.

Intuition

The provided solution approach is straightforward and works by iterating through the array and making local swaps to enforce the wiggle pattern. It utilizes a greedy algorithm that checks at each step if the current element violates the wiggle condition. If it does, the algorithm swaps the current element with the previous one. The condition for odd and even indices is different:

For odd indices (1, 3, 5, ...), if the current element is less than the previous one, a swap is needed to make sure the current (odd-indexed) element is greater or equal.
For even indices (2, 4, 6, ...), if the current element is greater than the previous one, a swap is needed to make sure the current (even-indexed) element is less or equal.

By swapping only when the condition is violated, we ensure that the swapped elements will also satisfy the wiggle condition with their new neighbors. This happens because we are only ever swapping adjacent elements that were already checked in previous iterations. Since we are iterating from the second element to the end of the array, each element is considered in its turn, and we avoid the extra memory usage that would come from creating a second array to hold the rearranged elements.

Learn more about Greedy and Sorting patterns.

Solution Approach

The solution uses a simple algorithm that is already described in the intuition. As for the implementation, it involves iterating through the array starting from the second element. During each iteration, the current element is compared with its predecessor, and a conditional swap is used to rectify the ordering if a wiggle violation is detected.

To implement this, the solution uses a single for loop that starts from index 1, since index 0 has no preceding element and thus cannot violate the wiggle property.

Within the loop, the solution checks two conditions, each corresponding to whether the current index i is even or odd:

For odd indices (when i % 2 == 1), if the current element nums[i] is less than the previous element nums[i - 1], they are swapped. This ensures that at odd indices, the value at that index is always greater than or equal to its predecessor.
For even indices (when i % 2 == 0), if the current element nums[i] is greater than the previous element nums[i - 1], they are swapped. This ensures that at even indices, the value at that index is always less than or equal to its predecessor.

The use of the modulo operation i % 2 helps to differentiate between even and odd indices. The swap operation itself is a standard technique and is implemented in Python by simply using tuple unpacking: nums[i], nums[i - 1] = nums[i - 1], nums[i]. This is equivalent to the algorithm having a temporary variable to hold one of the values during the swap but is more concise and idiomatic in Python.

No additional data structures are used, and the algorithm modifies the input list nums in place, resulting in a space complexity of O(1), since only a constant amount of extra space is used.

The time complexity of the algorithm is O(n), where n is the number of elements in the array. It's linear because the algorithm goes through the array only once, doing a constant amount of work for each element.

In summary, this algorithm efficiently enforces the wiggle condition using local swaps during a single pass through the array, requiring no extra memory apart from a few constant variables.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's apply the solution approach to a small array nums = [6, 4, 7, 5, 2]. Our goal is to modify nums in place to meet the alternating pattern of nums[0] <= nums[1] >= nums[2] <= nums[3] and so on. Following the approach, we start at the second element (index 1) and move through the array considering each element.

Iteration 1:

Index 1 (value 4) is odd.
Check if nums[1] < nums[0] (is 4 < 6? Yes).
No swap needed since the condition for odd indices is already fulfilled.

After Iteration 1: nums = [6, 4, 7, 5, 2]

Iteration 2:

Index 2 (value 7) is even.
Check if nums[2] > nums[1] (is 7 > 4? Yes).
Swap since this violates the condition for even indices.
After swapping, nums becomes [6, 7, 4, 5, 2].

After Iteration 2: nums = [6, 7, 4, 5, 2]

Iteration 3:

Index 3 (value 5) is odd.
Check if nums[3] < nums[2] (is 5 < 4? No).
Swap since this violates the condition for odd indices.
After swapping, nums becomes [6, 7, 5, 4, 2].

After Iteration 3: nums = [6, 7, 5, 4, 2]

Iteration 4:

Index 4 (value 2) is even.
Check if nums[4] > nums[3] (is 2 > 4? No).
No swap needed since the condition for even indices is already fulfilled.

Final result: nums = [6, 7, 5, 4, 2]

The example above demonstrates how the algorithm proceeds through the array, swapping elements as needed to create the "wiggle" pattern. By the final iteration, we have an array where each even index has a value not greater than its next element, and each odd index has a value not less than its previous element.

Solution Implementation

1from typing import List  # Import List from typing for type annotations
2
3class Solution:
4    def wiggleSort(self, nums: List[int]) -> None:
5        """
6        This method sorts the input array 'nums' such that nums[0] <= nums[1] >= nums[2] <= nums[3]...
7        The sort is done in-place to provide a 'wiggle' pattern.
8      
9        :param nums: List[int] - The list of numbers to be wiggled.
10        :return: None - The input list is modified in-place.
11        """
12      
13        # Loop through each element of the array starting from the second element.
14        for index in range(1, len(nums)):
15            # Check if the current index is odd.
16            is_odd_index = index % 2 == 1
17
18            # Wiggle condition for odd indices: if current element is less than the previous one.
19            # Wiggle condition for even indices: if current element is greater than the previous one.
20            if (is_odd_index and nums[index] < nums[index - 1]) or (not is_odd_index and nums[index] > nums[index - 1]):
21                # Swap the elements to maintain the wiggle condition.
22                nums[index], nums[index - 1] = nums[index - 1], nums[index]
23        # Since the method modifies the input list in-place, there is no return statement required.
24

1class Solution {
2    // Function to wiggle sort an array where nums[0] < nums[1] > nums[2] < nums[3]...
3    public void wiggleSort(int[] nums) {
4        // Loop through the array starting from index 1
5        for (int i = 1; i < nums.length; ++i) {
6            // Check if the current index is odd and the element is not greater than the previous element
7            // or the current index is even and the element is not smaller than the previous element
8            if ((i % 2 == 1 && nums[i] < nums[i - 1]) || (i % 2 == 0 && nums[i] > nums[i - 1])) {
9                // If either condition is true, swap the current and previous elements
10                swap(nums, i, i - 1);
11            }
12        }
13    }
14
15    // Helper function to swap two elements in the array
16    private void swap(int[] nums, int i, int j) {
17        int temp = nums[i]; // Store the value at index i
18        nums[i] = nums[j]; // Set the value at index i to the value at index j
19        nums[j] = temp; // Set the value at index j to the stored value of index i
20    }
21}
22

1class Solution {
2public:
3    // Function to wiggle sort an array where nums[0] < nums[1] > nums[2] < nums[3]...
4    void wiggleSort(vector<int>& nums) {
5        // Loop through the array starting from index 1
6        for (int i = 1; i < nums.size(); ++i) {
7            // If 'i' is odd and the current element is less than the previous one,
8            // or 'i' is even and the current element is greater than the previous one
9            if ((i % 2 == 1 && nums[i] < nums[i - 1]) || (i % 2 == 0 && nums[i] > nums[i - 1])) {
10                // Swap the current element with the previous one
11                swap(nums, i, i - 1);
12            }
13        }
14    }
15
16private:
17    // Helper function to swap two elements in the array
18    void swap(vector<int>& nums, int i, int j) {
19        int temp = nums[i]; // Store the value at index i in a temporary variable
20        nums[i] = nums[j]; // Assign the value at index j to index i
21        nums[j] = temp;    // Assign the stored value in temporary variable to index j
22    }
23};
24

1// Function to wiggle sort an array where nums[0] < nums[1] > nums[2] < nums[3]...
2function wiggleSort(nums: number[]): void {
3    // Loop through the array starting from index 1
4    for (let i = 1; i < nums.length; i++) {
5        // Check if the current index is odd and the current element is not greater than the previous element
6        // or the current index is even and the current element is not less than the previous element
7        if ((i % 2 === 1 && nums[i] < nums[i - 1]) || (i % 2 === 0 && nums[i] > nums[i - 1])) {
8            // If the element doesn't satisfy the wiggle condition, swap with the previous element
9            swap(nums, i, i - 1);
10        }
11    }
12}
13
14// Helper function to swap two elements in the nums array
15function swap(nums: number[], i: number, j: number): void {
16    const temp = nums[i]; // Store the value at index i
17    nums[i] = nums[j]; // Set the value at index i to the value at index j
18    nums[j] = temp; // Set the value at index j to the stored value of index i
19}
20

Time and Space Complexity

The given Python code performs a wiggle sort on an array nums by swapping adjacent elements when they do not follow the "wiggle" property (nums[i-1] < nums[i] for odd i and nums[i-1] > nums[i] for even i). Each pair of adjacent elements is considered exactly once.

Time Complexity:

The time complexity of the code is O(n), where n is the length of nums. This is because the algorithm iterates through the array once, and each iteration involves constant-time operations (simple comparisons and element swaps).

Space Complexity:

The space complexity of the code is O(1). This algorithm modifies the nums array in place and does not require any additional space that scales with the size of the input array. The only extra space used is for the loop counter and temporary variables for swapping, which are constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of these pictures shows the visit order of a depth-first search?

I don’t know