Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Array Waveform

Explore two approaches to solve the array waveform problem using Go: one compares and swaps neighbors based on value, the other sorts and swaps pairs. Understand the implementation details and time complexity of both solutions.

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

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 ...