1

For this challenge, you will determine if numbers in an array can be sorted in a particular way. Have the function WaveSorting(arr) take the array of positive integers (can contain duplicate) stored in arr and return the string true if the numbers can be arranged in a wave pattern: a1 > a2 < a3 > a4 < a5 > ..., otherwise, return the string false. For example, if arr is: [0, 1, 2, 4, 1, 4], then a possible wave ordering of the numbers is: [2, 0, 4, 1, 4, 1]. So for this input your program should return the string true. The input array will always contain at least 2 elements.

How to solve this problem? How to prove the correctness?

Jason Law
  • 965
  • 1
  • 9
  • 21
  • how about to check if there's (**any**) half (+ 1 or -1 depend on the arrangement of the statement and number of the items) it of the items that are smaller than the other half? isn't it the meaning of that "wave pattern" statements? could you refute (disprove) my statement? – JackRaBeat Dec 22 '22 at 08:12

1 Answers1

2

The ceiling(n/2) highest numbers can go at the even positions, and the remaining floor(n/2) lowest numbers can go at the odd positions.

This makes a wave sort unless the median element is duplicated in both groups and appears next to itself. As long as all occurrences of the median element can be spaced apart, then a wave sort is possible.

To space occurrences of the median apart, you need to assign at most one to each pair of adjacent items, like [M,?,M,?,M,?,?,M,?,M], and you can do that if the median element occurs at most N/2 times, or if it occurs ceil(N/2) times and all the other elements are smaller.

Whenever a wave sort is impossible, the median element is the majority element -- it occurs more than N/2 times. That provides a simple O(n) algorithm:

  1. Find the majority element. If there isn't one, return "true". See Find the majority element in array
  2. If N is even, return "false"
  3. Count occurrences of the majority element. If it's > ceil(n/2), return "false".
  4. Search for an element larger than the majority element. If there is one, return "false". Otherwise return "true".
Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87