Data Structures & Algorithms In Go/

...

/

Solution Review: Array Waveform

Solution Review: Array Waveform

Let’s take a detailed look at two solutions to the challenge set in the previous lesson.

We'll cover the following...

First solution

Compare the value of every even index with the values of its previous and next odd indices. Swap the pair if the value at the odd index is not less than the value at the even index. The solution idea is presented in the following illustration.

Solution code

Press + to interact
Go (1.6.2)
package main
import "fmt"
func swap(data []int, x int, y int) {
	data[x], data[y] = data[y], data[x]
}
func WaveArray(arr []int) {
    size := len(arr)
    /* Odd elements are lesser than even elements. */
    for i := 1; i < size; i += 2 {
        if (i-1) >= 0 && arr[i] > arr[i-1] { //swap with left neighbour
            swap(arr, i, i-1)
        }
        if (i+1) < size && arr[i] > arr[i+1] { //swap with right neighbour
            swap(arr, i, i+1)
        }
    }
}
/* Testing code */
func main() {
    arr := []int{8, 1, 2, 3, 4, 5} 
    WaveArray(arr)
    fmt.Println(arr)
}

Time complexity

The time complexity of the solution is O ...