Go Coding with Asparagos: Sunflowers and the Speaking Challenge

This content originally appeared on DEV Community and was authored by Asparagos

Sunflowers on a mission: better English in linear time?

Hi! I’m Asparagos — an asparagus who codes in Go. Here you’ll find everyday problems that a typical veggie might struggle with — and my Go solutions to them. Today we are solving the problem of Sunflower Speaking Club .

Problem

Sunflowers are planning to expand their influence across the world. Olives are gaining popularity, they can’t fall behind. To achieve this, they need to learn English.

Each sunflower already speaks it to some extent, but wants to find a partner to practice with. The sunflowers are planted in a row. Each has their own level of English and wants to find the nearest sunflower to the right who speaks better than they do.

Why to the right? The sun is rising in the east, so it’s the perfect moment to combine business with pleasure.

Input

A slice of integers — each integer represents the English level of a sunflower in the row.

Output

A slice of integers — each integer represents the distance to the nearest sunflower to the right with a higher English level. If there’s no such sunflower, return 0.

Examples :

• Example 1

  Input: [1, 5, 7, 3, 4]

  Output: [1, 1, 0, 1, 0]

• Example 2

  Input: [10, 9, 8, 7]

  Output: [0, 0, 0, 0]

• Example 3

  Input: [25, 13, 30]

  Output: [2, 1, 0]

Solution

1. We use a stack to keep track of potential candidates for being the nearest better-speaking partner to the right.

2. We iterate through the englishLevel slice from right to left. For each sunflower:

   a. We remove all sunflowers from the stack that have an English level less than or equal to the current one. These sunflowers can’t be good partners anymore, because the current sunflower is better and will be a better candidate for any future comparisons.

   b. If the stack is not empty, then the sunflower on top of the stack is the nearest one to the right with a higher level. So we store the distance between them.

   c. We then push the current sunflower onto the stack, as it might be a suitable partner for some sunflower to its left.

3. Each sunflower is pushed to the stack only once and removed at most once, so the overall time complexity is O(len(englishLevel)).
   

func findSpeakingPartner(englishLevel []int) []int {
    result := make([]int, len(englishLevel))
    stack := make([]int, 0, len(englishLevel))
    for ind := len(englishLevel) - 1; ind >= 0; ind-- {
        curLevel := englishLevel[ind]
        for len(stack) > 0 {
            stackInd := stack[len(stack)-1]
            if englishLevel[stackInd] > curLevel {
                break
            }
            stack = stack[:len(stack)-1]
        }
        if len(stack) != 0 {
            result[ind] = stack[len(stack)-1] - ind
        }
        stack = append(stack, ind)
    }
    return result
}

Feel free to check out the full code with tests on GitHub, and don’t hesitate to leave a if you find it helpful!

This content originally appeared on DEV Community and was authored by Asparagos