Skip to content

10.11. Peaks and Valleys

Description

In an array of integers, a "peak" is an element which is greater than or equal to the adjacent integers and a "valley" is an element which is less than or equal to the adjacent inte­gers. For example, in the array {5, 8, 6, 2, 3, 4, 6}, {8, 6} are peaks and {5, 2} are valleys. Given an array of integers, sort the array into an alternating sequence of peaks and valleys.

Example:


Input: [5, 3, 1, 2, 3]

Output: [5, 1, 3, 2, 3]

Note:

  • nums.length <= 10000

Solutions

Solution 1: Sorting

We first sort the array, and then traverse the array and swap the elements at even indices with their next element.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the array.

1
2
3
4
5
class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        nums.sort()
        for i in range(0, len(nums), 2):
            nums[i : i + 2] = nums[i : i + 2][::-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 1; i += 2) {
            int t = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = t;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n - 1; i += 2) {
            swap(nums[i], nums[i + 1]);
        }
    }
};

1
2
3
4
5
6
func wiggleSort(nums []int) {
    sort.Ints(nums)
    for i := 0; i < len(nums)-1; i += 2 {
        nums[i], nums[i+1] = nums[i+1], nums[i]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
/**
 Do not return anything, modify nums in-place instead.
 */
function wiggleSort(nums: number[]): void {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    for (let i = 0; i < n - 1; i += 2) {
        [nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    func wiggleSort(_ nums: inout [Int]) {
        nums.sort()

        let n = nums.count

        for i in stride(from: 0, to: n - 1, by: 2) {
            let temp = nums[i]
            nums[i] = nums[i + 1]
            nums[i + 1] = temp
        }
    }
}

Comments