Go Coding with Asparagos: The Smartest Peanut in the Neighborhood

#go #programming #algorithms #humor

Peanuts feed their ego 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 The Smartest Peanut in the Neighborhood 🥜.

Problem

Remember how the walnuts once tried to find out who was the smartest? Now it's the peanuts' turn, though their approach is a bit different.

Peanuts don't care about being the smartest among all nuts. They just want to feel smarter than their nearby neighbors.

You’re given the cleverness levels of peanuts planted in a row. For each group of k consecutive peanuts, determine which peanut is the smartest.

Is it a hard nut to crack?

Input 🌰

A slice of integers — each integer represents the cleverness level of a peanut in the row.
k — an integer that represents the size of a group (a sliding window).

Output 🌱

A slice of integers — each representing the maximum cleverness level within a sliding window of size k.

Examples 🥒:

Example 1

Input: [1, 6, 3, 4, 1, 2, 6], k = 3

Output: [6, 6, 4, 4, 6]

The first group is [1, 6, 3], its maximum is 6.
The second group is [6, 3, 4], its maximum is 6.
The third group is [3, 4, 1], its maximum is 4.
The fourth group is [4, 1, 2], its maximum is 4.
The last group is [1, 2, 6], its maximum is 6.
Example 2

Input: [1, 2, 3, 2, 1], k = 2

Output: [2, 3, 3, 2]

The first group is [1, 2], its maximum is 2.
The second group is [2, 3], its maximum is 3.
The third group is [3, 2], its maximum is 3.
The last group is [2, 1], its maximum is 2.

Solution 💡

We use a double-ended queue (deque) to keep track of the indices of peanuts that might be the smartest in the current sliding window. This queue helps us efficiently add and remove candidates from both ends.
We iterate through the peanuts slice. For each peanutLevel at index i:

a. We remove all peanuts from the right side of the queue that are less clever than or equal to the current one. They're no longer valid candidates because the current peanut is smarter and more recent.

b. We add the current index i to the right of the queue.

c. If the leftmost index in the queue is outside the current window (i.e., its index is less than or equal to i - k), we remove it, it's no longer part of the group we're analyzing.

d. If the window has reached size k (i.e., i + 1 >= k), we save the cleverness of the peanut at the left side of the queue as the result because it's the smartest one in the current window.
Each peanut is added to the queue once and removed at most once, so the total time complexity is O(len(peanuts)).

func findSmartestPeanut(peanuts []int, k int) []int {
    res := make([]int, 0, len(peanuts)-k+1)
    deque := make([]int, 0, len(peanuts))
    for i, peanutLevel := range peanuts {
        for len(deque) > 0 && peanuts[deque[len(deque)-1]] <= peanutLevel {
            deque = deque[:len(deque)-1]
        }

        deque = append(deque, i)

        if len(deque) > 1 && deque[0] <= i-k {
            deque = deque[1:]
        }
        if i+1 >= k {
            res = append(res, peanuts[deque[0]])
        }
    }
    return res
}