Forem: Asparagos

Go Coding with Asparagos: Fair Play in Watermelon Football

Asparagos — Wed, 15 Oct 2025 10:01:20 +0000

Who becomes the referee in the Great Watermelon Football Final?

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 Watermelon Football 🍉.

Problem

Welcome to The Great Watermelon Football Final! The watermelons are ready, and the stakes are high. There’s just one task left: we must split the players into two teams.

The watermelons are standing in a row, each with a rating. We must remove exactly one watermelon (don’t worry, this one becomes the referee). The remaining watermelons are split into two teams by index in the remaining row:

Team Even: players at even indices

Team Odd: players at odd indices

The total rating of both teams must be equal.

How many choices of the referee (how many indices to remove) make the teams' total ratings equal?

Input 🍈

rating []int - the ratings of the watermelons, len(rating) > 2.

Output 🥭

An integer representing the number of ways to choose one watermelon to remove (the referee) so that the remaining players can be split by index into two teams with equal total rating.

Examples 🥝:

Example 1

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

Output: 2

We can remove the 2nd watermelon (rating 3), remaining players are [1, 2, 1, 2, 2].
Team Even: 1 + 1 + 2 = 4, Team Odd: 2 + 2 = 4.

We can remove the 4th watermelon (rating 1), remaining players are [1, 3, 2, 2, 2].
Team Even: 1 + 2 + 2 = 5, Team Odd: 3 + 2 = 5.
Example 2

Input: rating = [5, 7, 3, 8, 1]

Output: 1

We can remove the 4th watermelon (rating 8), remaining players are [5, 7, 3, 1].
Team Even: 5 + 3 = 8, Team Odd: 7 + 1 = 8.
Example 3

Input: rating = [1, 2, 3, 4]

Output: 0

There are no ways to remove one watermelon and obtain equal team totals.

Solution 💡

First, we calculate the total sums at even and odd indices: evenSum and oddSum.
We iterate through the watermelons' ratings and consider removing the current one at index ind. To check whether this removal builds equal teams, we use even/odd prefix sums before ind and compare the new even/odd sums after the removal (remember: all indices to the right shift left by 1, so their parity changes):

a. After removing index ind, all elements to the right that were at even indices become odd. Their total is evenSum - prefixEvenSum. Adding the odd prefix on the left, we get newOddSum = prefixOddSum + (evenSum - prefixEvenSum). If the current index is even, we must subtract its value r from newOddSum (because it was counted on the even side before removal). Then update prefixEvenSum += r.

b. Symmetrically, elements to the right that were at odd indices become even, their sum is oddSum - prefixOddSum. Adding the even prefix on the left, we get newEvenSum = prefixEvenSum + (oddSum - prefixOddSum). If the current index is odd, subtract r from newEvenSum, then update prefixOddSum += r.

c. If newOddSum == newEvenSum, increment count.

func countWaysToMakeTeams(rating []int) int {
    oddSum := 0
    evenSum := 0
    for ind, r := range rating {
        if ind%2 == 0 {
            evenSum += r
        } else {
            oddSum += r
        }
    }
    var prefixOddSum, prefixEvenSum, count int
    for ind, r := range rating {
        newOddSum := prefixOddSum + (evenSum - prefixEvenSum)
        newEvenSum := prefixEvenSum + (oddSum - prefixOddSum)
        if ind%2 == 0 {
            newOddSum -= r
            prefixEvenSum += r
        } else {
            newEvenSum -= r
            prefixOddSum += r
        }
        if newOddSum == newEvenSum {
            count++
        }
    }
    return count
}

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

Go Coding with Asparagos: Lemon Squeezy, Dynamic Easy

Asparagos — Fri, 10 Oct 2025 07:47:11 +0000

When life gives you lemons, make a quiz team!

Problem

Summer is over, lemonade is out of fashion, but the lemons refuse to waste time. They've formed a team called "Lemon Squeezy" and are aiming to win the annual pub quiz.

Now they must decide who joins the team. Each lemon has two attributes: IQ and age. They want a team with the maximum total IQ. But lemons have fragile citrus egos: no lemon will play in a team with a younger lemon who has a higher IQ.

Can they quickly figure out who should be in the team? And what will the total IQ of "Lemon Squeezy" be?

Input 🍊

iqs []int - IQ of each lemon.
ages []int - age of each lemon.

Output 🍐

An integer — the maximum total IQ of a team with no conflicts. A conflict exists if a younger lemon has a higher IQ than the older lemon. Lemons of the same age never conflict, regardless of IQ.

Examples 🍈:

Example 1

Input: iqs = [1, 2, 3], ages = [10, 15, 20]

Output: 6

All lemons can be in the same team.
Example 2

Input: iqs = [4, 9, 20], ages = [20, 10, 15]

Output: 29

The team consists of the second and third lemons. The first lemon can’t be included because its IQ = 4 is lower than the IQ of the second lemon, who is younger.
Example 2

Input: iqs = [17, 24, 50], ages = [46, 37, 5]

Output: 50

The team consists of a single lemon — the last one. Any other combination would include a younger lemon with a higher IQ than an older lemon, causing a conflict.

Solution 💡

First, we sort all lemons by age. If two lemons have the same age, we sort them by IQ. We also create a slice teamIQs, where teamIQs[i] is the maximum total IQ of the team that contains the lemon at index i.
We iterate through the sorted lemons. For each lemon, we first set teamIQs[i] to the current lemon's IQ: at least the team consisting of just the i-th lemon is valid.
For each lemon, we iterate through all previous lemons and try to find a previous team to which the current lemon can be added without conflicts.

In the team at index prevInd, the lemon with the maximum IQ is the lemon at prevInd (otherwise that lemon could not have been added, because it would be older with a smaller IQ, given our sorting).

Therefore, if the current lemon's IQ is greater than or equal to the prevInd lemon's IQ, we can add the current lemon to teamIQs[prevInd] without conflicts. Among all such possible teams, we take the one with the maximum total IQ.
As we go, we update maxTeamIQ — the maximum total IQ over all conflict-free teams.

type Lemon struct {
    iq  int
    age int
}

func findBestTeamIQ(iqs []int, ages []int) int {
    lemons := make([]Lemon, len(iqs))
    for i, iq := range iqs {
        lemons[i] = Lemon{iq: iq, age: ages[i]}
    }
    slices.SortFunc(lemons, func(a, b Lemon) int {
        if a.age == b.age {
            return cmp.Compare(a.iq, b.iq)
        }
        return cmp.Compare(a.age, b.age)
    })

    teamIQs := make([]int, len(lemons))
    maxTeamIQ := 0
    for i, lemon := range lemons {
        teamIQs[i] = lemon.iq
        for prevInd := 0; prevInd < i; prevInd++ {
            if lemons[prevInd].iq > lemon.iq {
                continue
            }
            newIQ := teamIQs[prevInd] + lemon.iq
            if newIQ > teamIQs[i] {
                teamIQs[i] = newIQ
            }
        }
        if teamIQs[i] > maxTeamIQ {
            maxTeamIQ = teamIQs[i]
        }
    }
    return maxTeamIQ
}

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

Go Coding with Asparagos: Mushroom Soup for everyone!

Asparagos — Wed, 01 Oct 2025 09:02:43 +0000

Everyone deserves creamy mushroom soup!

Problem

Autumn is a great time for soup, so the Veggie Kingdom is gathering mushrooms for a creamy mushroom soup. But there’s one problem: lactose intolerance. What's the solution? Cook two pots: one with dairy cream and one with coconut cream.

The amount of soup should be the same in both pots, so we need to split the mushrooms evenly by weight. Each mushroom has its own weight, so we can’t just divide them by count.

How can we quickly check whether it’s possible to partition the mushrooms into two groups with equal total weight?

Input 🥔

mushrooms []int - weights of the mushrooms (each element is the weight of one mushroom).

Output 🧅

Return true if it’s possible to partition the mushrooms evenly by weight (into two groups with equal total weight), otherwise return false.

Examples 🧄:

Example 1

Input: mushrooms = [1,5,11,5]

Output: true

The first pot contains mushrooms with weights 1, 5, 5, and the second pot contains a single mushroom with weight 11.
Example 2

Input: mushrooms = [1, 3, 10]

Output: false

It’s impossible to split the mushrooms into two groups with equal total weight.

Solution 💡

First, we calculate the total weight of all mushrooms. If totalWeight is odd, it's impossible to partition mushrooms evenly. Otherwise, the target weight for one pot is totalWeight / 2 (call it potWeight).
We use dynamic programming to solve the problem. Let's create a boolean slice dpSumWeight, where dpSumWeight[i] is true if some subset of mushrooms sums to i. We need potWeight+1 elements, because the maximum sum we care about is potWeight and we also add one element for zero weight.
We iterate through all the mushrooms. For each mushroom we scan dpSumWeight backwards. If dpSumWeight[i] is true and i+mushroomWeight < len(dpSumWeight), then set dpSumWeight[i+mushroomWeight] = true, because the sum i+mushroomWeight is now reachable. We go backwards so we don’t reuse the same mushroom twice during the same iteration.
If at any point dpSumWeight[potWeight] becomes true, we return true. Otherwise, return false.

func canPartition(mushrooms []int) bool {
    totalWeight := 0
    for _, mushroomWeight := range mushrooms {
        totalWeight += mushroomWeight
    }
    if totalWeight%2 == 1 {
        return false
    }
    potWeight := totalWeight / 2

    dpSumWeight := make([]bool, potWeight+1)
    dpSumWeight[0] = true
    for _, mushroomWeight := range mushrooms {
        for i := len(dpSumWeight) - 1; i >= 0; i-- {
            if dpSumWeight[i] && i+mushroomWeight < len(dpSumWeight) {
                dpSumWeight[i+mushroomWeight] = true
            }
        }
        if dpSumWeight[potWeight] {
            return true
        }
    }
    return false
}

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

Go Coding with Asparagos: Saving Apples from Pies

Asparagos — Wed, 24 Sep 2025 08:13:34 +0000

Can a single train save apples from the pie threat?

Problem

The season of Apple Pies has begun. All the apples are leaving their homes in search of a safer place. Nobody wants to end up in a pie anymore — it’s just not trendy. A smoothie is better, or at least a strudel.

There is a train going in one direction with a limited number of seats. Apples travel in groups: each group wants to board the train at point X and leave at point Y.

Can the train take every apple without exceeding its seats?

Input 🍐

trips []Trip - information about group trips. Each Trip has a start point from, an end point to, and the group size num.

capacity int - the number of seats on the train.

Output 🍊

true if the train can carry all apples without exceeding capacity at any point; false otherwise.

Examples 🍋:

Example 1

Input: trips = {{from: 2, to: 7, num: 1}, {from: 0, to: 2, num: 3}, {from: 1, to: 3, num: 2}}, capacity = 5

Output: true

At point 0, the train takes 3 apples.

Then, at point 1, it takes 2 more apples, so now all 5 seats are occupied.

At point 2, 3 apples leave the train. At the same time, 1 apple boards the train. Now there are 3 apples on board.

At point 3, 2 apples leave the train. Only 1 apple remains, which will leave at point 7.

The apples on board never exceeded the train’s capacity.
Example 2

Input: trips = {{from: 0, to: 2, num: 3}, {from: 1, to: 3, num: 2}}, capacity = 4

Output: false

At point 0, the train takes 3 apples.

At point 1, it should take 2 more apples. That would require 5 seats, but the capacity is 4, so the train can't take them.

Solution 💡

First, we build a list of events: each trip creates a pick-up event at from and a drop-off event at to. We sort events by location in ascending order. When two events have the same location, put drop-offs before pick-ups. In this case, the freed seats can be reused immediately. Each event contains: location, num (group size), and isFrom (whether it is a pick-up or drop-off).
We iterate through the events and update the current number of apples on the train num. If it's a drop-off, we subtract the size of the group from num. Otherwise, we add the group size to num.
If at any point a pick-up would exceed capacity, return false.
Otherwise, return true.

type Trip struct {
    from int
    to   int
    num  int
}

type Event struct {
    location int
    num      int
    isFrom   bool
}

func canSaveAllApples(trips []Trip, capacity int) bool {
    events := make([]Event, 0, 2*len(trips))
    for _, trip := range trips {
        events = append(events, Event{trip.from, trip.num, true}, Event{trip.to, trip.num, false})
    }
    slices.SortFunc(events, func(a, b Event) int {
        if a.location != b.location {
            return cmp.Compare(a.location, b.location)
        }
        if a.isFrom == b.isFrom {
            return 0
        }
        if !a.isFrom {
            return -1
        }
        return 1
    })
    num := 0
    for _, event := range events {
        if !event.isFrom {
            num -= event.num
            continue
        }
        if capacity-num < event.num {
            return false
        }
        num += event.num
    }
    return true
}

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

Go Coding with Asparagos: Coconuts Never Roll Alone

Asparagos — Thu, 04 Sep 2025 14:09:15 +0000

What happens when coconuts start racing?

Problem

Coconuts are having a race! Just for fun. After all, there's no real need to hurry when you're a coconut.

Each coconut starts from a certain position and has its own speed. They're all rolling in the same direction toward a common finish line.

Whenever one coconut catches up with another, they merge into a coconut bouquet and continue rolling together at the speed of the slowest coconut in the group.

How many bouquets will reach the finish line?

Input 🥭

position []int - the starting positions of the coconuts.

speed []int - the speeds of the coconuts.

target int - the finish line; all coconuts are rolling toward this point.

Output 🍍

An integer representing the number of coconut bouquets that reach the target.

Examples 🍌:

Example 1

Input: position = [1, 3, 18], speed = [5, 1, 3], target = 20

Output: 2

The first coconut (from position 1, speed 5) catches up to the second one (position 3, speed 1) before reaching the target.

They form a bouquet and move together at speed 1.

The third coconut (position 18, speed 3) reaches the target before the bouquet catches up.

So, there are 2 bouquets at the finish.
Example 2

Input: position = [2, 0, 4], speed = [3, 7, 1], target = 10

Output: 1

The coconut starting from 0 (speed 7) quickly catches up to the one at 2 (speed 3).

Together they move at speed 3 and catch up to the coconut at 4 (speed 1) before reaching the target.

All three coconuts finish as a single bouquet.

Solution 💡

First, we sort the coconuts by their starting positions.
Then, we iterate through the coconuts from right to left. We keep track of the current bouquet using two variables:

bouquetPos — the position of the last bouquet,
bouquetSpeed — the speed of the last bouquet.
For each coconut, we check whether it can reach the current bouquet (canReach()). A coconut can merge with the bouquet if it catches up to it before the bouquet itself reaches the finish.
If the coconut can't reach the bouquet, then no other coconut behind it will be able to reach that bouquet either. Why? Because to get there, they would first need to catch up to the current coconut, and then move at its speed. So, if the current coconut can’t make it, nobody else can.

In this case, we increase the count of bouquets res. The current coconut now becomes the new bouquet, so we update bouquetPos and bouquetSpeed.
In the end, we return res + 1, because the very last bouquet wasn’t counted during the loop.

func canReach(leftPos, rightPos, leftSpeed, rightSpeed, target int) bool {
    if leftPos == rightPos {
        return true
    }
    if leftSpeed <= rightSpeed {
        return false
    }
    approachSpeed := leftSpeed - rightSpeed
    approachDist := rightPos - leftPos
    rightDist := target - rightPos
    return approachDist*rightSpeed <= approachSpeed*rightDist
}

type Coconut struct {
    pos   int
    speed int
}

func countCoconutBouquets(target int, position []int, speed []int) int {
    if len(position) == 0 {
        return 0
    }
    coconuts := make([]Coconut, 0, len(position))
    for i, pos := range position {
        coconuts = append(coconuts, Coconut{pos: pos, speed: speed[i]})
    }
    slices.SortFunc(coconuts, func(a, b Coconut) int { return a.pos - b.pos })

    lastInd := len(coconuts) - 1
    bouquetPos := coconuts[lastInd].pos
    bouquetSpeed := coconuts[lastInd].speed
    res := 0
    for i := len(coconuts) - 2; i >= 0; i-- {
        curPos := coconuts[i].pos
        curSpeed := coconuts[i].speed
        if canReach(curPos, bouquetPos, curSpeed, bouquetSpeed, target) {
            continue
        }
        res++
        bouquetPos = curPos
        bouquetSpeed = curSpeed
    }
    return res + 1
}

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

Go Coding with Asparagos: The Smartest Peanut in the Neighborhood

Asparagos — Tue, 26 Aug 2025 06:44:48 +0000

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
}

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

Go Coding with Asparagos: Sunflowers and the Speaking Challenge

Asparagos — Tue, 19 Aug 2025 08:10:54 +0000

Sunflowers on a mission: better English in linear time?

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 💡

We use a stack to keep track of potential candidates for being the nearest better-speaking partner to the right.
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.
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!

Go Coding with Asparagos: Will Graph Cycles Spoil the Salsa Festival?

Asparagos — Thu, 14 Aug 2025 14:27:40 +0000

Salsa Festival! All vegetables are invited! Can cycles ruin the fun?

Problem

There’s a salsa festival in the Veggie Kingdom this weekend. All vegetables are invited, free of charge!

But veggies are picky: each one will only come if certain friends arrive first.
For example, bell pepper will only show up after his brother, chili pepper. A potato will only come if both pumpkin and corn are already there (this trio became best friends after the lecture "Introduction to the Carbohydrate Diet").

Nobody can untangle these complicated relationships. Did you know that apple is trying to sue pineapple for using its name?

So, can we figure out whether all the veggies will come to the salsa festival?

Input 🥒

vegNum int - the total number of vegetables in the kingdom.

requirements [][]int - each element requirements[i] = [a, b] means that vegetable a will come to the festival only if vegetable b comes first.

Output 🍅

true if it’s possible for all vegetables to attend the festival,

false if some requirements create a deadlock (i.e. a cycle).

Examples 🌶️:

Example 1

Input: vegNum = 2, requirements = [[1, 0]]

Output: true

Vegetable 0 can come without any conditions. Vegetable 1 depends on 0, and since 0 can come, 1 can come too.
Example 2

Input: vegNum = 2, requirements = [[1, 0], [0, 1]]

Output: false

Vegetable 1 depends on 0, and 0 depends on 1. This creates a cycle, neither can come first, so no one comes.

Solution 💡

We start by building a graph of vegetables. Each vertex represents a vegetable. An edge a -> b means that b will only come if a comes first. Now the problem reduces to detecting a cycle in this graph, which we can do using Depth-First Search (DFS).
The dfs function is a recursive function with the following arguments:

graph [][]int - the adjacency list of the vegetable graph

vertex int – the current node we are traversing

pathVertices map[int]bool - tracks nodes on the current DFS path (used to detect a cycle)

visited map[int]bool - tracks all previously visited nodes (used to avoid duplicate traversal)

It returns true if a cycle is found, and false otherwise.
Cycle detection logic:

If the vertex is already in pathVertices, that means we've visited it in the current path — a cycle is found, so we return true.

If it's already in visited but not in the current path, we've checked it before and know it doesn’t lead to a cycle — return false.
Otherwise, we:

Mark the current node as visited (both in visited and pathVertices).

Recursively apply DFS to its children.

After processing all descendants, remove the current node from pathVertices (as we’re backtracking).

If no cycles are found during any DFS traversal, return true. Otherwise, return false.

func canAllVeggiesCome(vegNum int, requirements [][]int) bool {
    vegGraph := make([][]int, vegNum)
    for _, req := range requirements {
        toVeg := req[0]
        fromVeg := req[1]
        vegGraph[fromVeg] = append(vegGraph[fromVeg], toVeg)
    }

    visited := make(map[int]bool)
    for veg := 0; veg < vegNum; veg++ {
        if visited[veg] {
            continue
        }
        pathVertices := make(map[int]bool)
        if dfs(vegGraph, veg, pathVertices, visited) {
            return false
        }
    }
    return true
}

func dfs(graph [][]int, vertex int, pathVertices map[int]bool, visited map[int]bool) bool {
    if pathVertices[vertex] {
        return true
    }
    if visited[vertex] {
        return false
    }
    pathVertices[vertex] = true
    visited[vertex] = true
    for _, childV := range graph[vertex] {
        if dfs(graph, childV, pathVertices, visited) {
            return true
        }
    }
    pathVertices[vertex] = false
    return false
}

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

Go Coding with Asparagos: How Much Gazpacho Can We Make with Dynamic Programming?

Asparagos — Tue, 29 Jul 2025 07:49:31 +0000

One chef. One heatwave. Can Dynamic Programming save the gazpacho?

Problem

Everyone is suffering from the summer heat. One chef decides to surprise everyone by making the biggest gazpacho ever.

He needs as many tomatoes as possible. There are several tomato beds in the garden, but he can't gather them all. He wants to keep it a secret - nobody should notice anything suspicious for as long as possible.

So he comes up with a strategy: he’ll collect all the tomatoes from some beds and leave the others untouched — but he won’t leave two adjacent beds empty. Otherwise, someone might suspect something (especially the lemons - they’re always sticking their nose where it doesn’t belong).

Time is running out, the sun is burning, and we all want that delicious cold soup as soon as possible. How can the chef gather the maximum number of tomatoes? And how many tomatoes can he collect in total?

Input 🥒

A slice of integers representing tomato beds — each integer is the number of tomatoes in that bed.

Output 🫑

An integer — the maximum number of tomatoes the chef can collect without leaving two adjacent beds empty.

Examples 🧅:

Example 1

Input: [6, 3, 5, 10]
Output: 16

If we take tomatoes from the first bed, we have two options:
- Take tomatoes from the third bed: 6 + 5 = 11
- Take tomatoes from the last bed: 6 + 10 = 16
If we take tomatoes from the second bed, we can only take tomatoes from the last bed: 3 + 10 = 13

The best option gives us 16 tomatoes.
Example 2

Input: [3, 7, 2]
Output: 7

If we take tomatoes from the first bed, we can also take tomatoes from the last bed: 3 + 2 = 5

If we take tomatoes from the second bed, we can’t take any others, so we get 7 tomatoes.

The best option gives us 7 tomatoes.

Solution 💡

We iterate through the input slice. At each step, we calculate two values:

takeSum: the maximum number of tomatoes we can collect if we take tomatoes from the current bed.

notTakeSum: the maximum number of tomatoes we can collect if we skip the current bed.
Initially, both takeSum and notTakeSum are set to 0.
At each step:

If we take tomatoes from the current bed (num), we should have skipped the previous one. So the new takeSum becomes notTakeSum + num.

If we skip the current bed, it doesn’t matter whether we took or skipped the previous one - we just take the maximum of the previous takeSum and notTakeSum.
After processing all beds, the result is the maximum of takeSum and notTakeSum.

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func collectTomatoes(beds []int) int {
    takeSum := 0
    notTakeSum := 0
    for _, num := range beds {
        takeSum, notTakeSum = notTakeSum+num, max(notTakeSum, takeSum)
    }
    return max(takeSum, notTakeSum)
}

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

Go Coding with Asparagos: Detecting Potato Cycles in O(1) Space

Asparagos — Mon, 14 Jul 2025 09:00:54 +0000

Potato vs Bugs. Can FIFO save the harvest?

Problem

Yet another challenging day in the Veggie Kingdom. To save the harvest, all potatoes must be treated for bugs. That’s why they’re lining up at the Fight for Insect-Free Organics (FIFO) office.

But potatoes aren’t the sharpest veggies — they might mess things up and accidentally form a cycle in the queue. We need to check whether their queue contains a cycle.

The Kingdom is going through hard times, so we must solve this using only constant memory.

Input 🥦

A head of a linked list of potatoes. Each potato has a Name and a pointer to the next one:

type PotatoNode struct {
    Name string
    Next *PotatoNode
}

Output 🥕

Return true if the list contains a cycle, or false otherwise.

Examples 🥒:

Example 1

Input:

Potato Jack -> Potato George -> Potato Arthur -> nil

Output: false

Example 2

Input:

Potato Jack -> Potato George -> Potato Arthur
                      ↑                ↓
                      ← ← ← ← ← ← ← ← ←

Output: true

Solution 💡

We use two pointers:
slowNode moves one node at a time.
fastNode moves two nodes at a time.
As we iterate through the list:

If fastNode reaches the end (nil), there’s no cycle.

If slowNode and fastNode meet at the same node, it means there's a cycle.

func hasPotatoCycle(head *PotatoNode) bool {
    if head == nil {
        return false
    }
    slowNode := head
    fastNode := head
    for fastNode != nil && fastNode.Next != nil {
        slowNode = slowNode.Next
        fastNode = fastNode.Next.Next
        if slowNode == fastNode {
            return true
        }
    }
    return false
}

This is a classic example of Floyd's cycle-finding algorithm, also known as the Tortoise and Hare algorithm.

Naturally, no tortoises or hares were allowed to participate in our event - otherwise, our veggies would've been in serious danger.

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

Go Coding with Asparagos: Are Strawberries in Danger?

Asparagos — Mon, 07 Jul 2025 14:38:26 +0000

One boy. One obsession. Can the city’s strawberries survive?

Problem

There’s one boy who is crazy about strawberries (and honestly, who isn’t?). One day, he decided to eat all the strawberries in the city.

There is a bunch of stores arranged in a circle where strawberries can be bought. The boy wants to visit all of them in a clockwise direction and buy every strawberry he can. For each store, we know:

how many strawberries can be bought there,
how many strawberries he needs to eat to have enough energy to move from that store to the next one.

We don't know where the boy will start his route, but he must finish it at the same store where he started.

Can the boy visit all the stores if he has unlimited money and can eat all the strawberries he collects along the way?

It's guaranteed that if completing the route is possible, there is exactly one valid starting point. In that case, we should find this starting point — and stop his evil strawberry plan!

Input 🍒

storeStock []int — each storeStock[i] represents the number of strawberries available in the ith store.

wayCost []int — each wayCost[i] represents the number of strawberries the boy needs to eat to travel from store i to store i+1.

Output 🍇

An integer — the index of the store where the boy should start his route to complete his plan. Return -1 if no such starting point exists.

Examples 🫐:

Example 1

Input: storeStock = [1, 2, 3, 4, 5], wayCost = [3, 4, 5, 1, 2]
Output: 3

He starts at store 3 and eats 4 strawberries. His energy reserve is 4 strawberries.

He travels to store 4, spends 1 strawberry of energy, and eats 5 strawberries. His energy reserve is 4 - 1 + 5 = 8 strawberries.

He travels to store 0, spends 2 strawberries, and eats 1 strawberry. His energy reserve is 8 - 2 + 1 = 7.

He travels to store 1, spends 3 strawberries, eats 2 strawberries. His energy reserve is 7 - 3 + 2 = 6.

He travels to store 2, spends 4 strawberries, eats 3 strawberries. His energy reserve is 6 - 4 + 3 = 5.

He travels to store 3, spends 5 strawberries. Mission completed.
Example 2

Input: storeStock = [2, 3, 4], wayCost = [3, 4, 3]

Output: -1

If he starts at store 0 he eats 2 strawberries, but he needs 3 strawberries to get to the next store.

If he starts at store 1 he eats 3 strawberries, but he needs 4 strawberries to get to the next store.

If he starts at store 2 he eats 4 strawberries. Then, he travels to store 0, spends 3 strawberries and eats 2 strawberries. His energy reserve is 4 - 3 + 2 = 3 strawberries.

He travels to store 1, spends 3 strawberries and eats 3 strawberries. His energy reserve is 3 - 3 + 3 = 3 strawberries. But he needs 4 strawberries to finish the circle and travel to the store 2. So it's impossible.

Solution 💡

We need three variables:
• minEnergyReserve - the minimum energy reserve reached during the loop (before eating strawberries).
• minEnergyReserveInd - the index of the store where that minimum occurred.
• energyReserve - the current energy reserve at any given step.
We iterate through the stores. At each step:

• We add the difference between strawberries gained storeStock[ind] and energy spent wayCost[ind] to energyReserve.

• If the current energyReserve is less than minEnergyReserve, we update both minEnergyReserve and minEnergyReserveInd.
After completing the loop, we check if energyReserve is negative.
If energyReserve < 0, it means the total amount of strawberries is less than the total energy required to complete the full circle. In that case, it’s impossible to complete the route — no matter where you start.
Otherwise, we can start at the store where the minimum energy reserve occurred — minEnergyReserveInd. Let’s see why this works.

• If minEnergyReserve == 0, it means our energy reserve was never negative during the entire loop, and the minimum occurred right at the beginning. So minEnergyReserveInd == 0, and starting from index 0 is safe — we can complete the full route without running out of energy.

• If minEnergyReserve < 0, and we now start from minEnergyReserveInd, our energy reserve is reset to 0 instead of some negative value. From this point on, we follow the same path as before, but with an energy reserve that is always higher by -minEnergyReserve. Since no point in the previous run was lower than minEnergyReserve, now we will never hit a negative energy level, and we can successfully complete the route.

func canEatAllStrawberries(storeStock []int, wayCost []int) int {
    minEnergyReserve := 0
    minEnergyReserveInd := 0
    energyReserve := 0
    for ind := 0; ind < len(storeStock); ind++ {
        if energyReserve < minEnergyReserve {
            minEnergyReserve = energyReserve
            minEnergyReserveInd = ind
        }
        energyReserve += storeStock[ind] - wayCost[ind]
    }
    if energyReserve < 0 {
        return -1
    }
    return minEnergyReserveInd
}

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

Go Coding with Asparagos: Walnuts Take the IQ Test

Asparagos — Wed, 25 Jun 2025 09:15:59 +0000

Are walnuts the smartest?

Problem

Walnuts believe they are the smartest among all the plants (though not everyone agrees - especially spinach). Each walnut also believes that they are the smartest among all walnuts. Now, they want to convince everyone of their genius.

All walnuts have taken an IQ test. We have the IQ results for each of them. Now, they want to know if they are smarter than the average IQ of all the other walnuts - excluding themselves.

But that's not all. After gaining power, the fruits passed a new law: No negativity! Everyone should be happy and support the new King! So, subtraction is now banned in the kingdom. We must solve the problem without using the - operator.

Input 🥦

A slice of integers — each integer represents the result of one walnut's IQ test. There are at least two elements in the slice.

Output 🥕

A slice of integers — each integer represents the average IQ score of all the walnuts except the one at that index. The average should be calculated as the sum of the other results divided by their count, rounded down.

Examples 🥒:

Example 1

Input: [14, 75, 24, 86]

Output: [61, 41, 58, 37]

For index 0: average of [75, 24, 86] = (75 + 24 + 86) / 3 = 61.66... → 61
For index 1: average of [14, 24, 86] = 41.33... → 41
For index 2: average of [14, 75, 86] = 58.33... → 58
For index 3: average of [14, 75, 24] = 37.66... → 37
Example 2

Input: [15, 23, 48]

Output: [35, 31, 19]

For index 0: average of [23, 48] = (23 + 48) / 2 = 35.5 → 35
For index 1: average of [15, 48] = 31.5 → 31
For index 2: average of [15, 23] = 19
Example 3

Input: [15, 23]

Output: [23, 15]

Each index simply returns the other value.

Solution 💡

We create a result slice result. First, we calculate the prefix sum for each index and store it in result.
To calculate the average IQ of all nuts except the one at index ind, we need to sum all the elements to the left and right of that index.

We already have the prefix sum (i.e. the sum of all elements to the left) in result[ind - 1].

While iterating through the slice in reverse order, we calculate suffixSum, which holds the sum of all elements to the right of the current index.

The average is then calculated as (result[ind - 1] + suffixSum) / divNumber.

There's no subtraction in this algorithm, as required by the kingdom’s "No Negativity" law.

func checkWalnutGenius(iqs []int) []int {
    result := make([]int, len(iqs))
    result[0] = iqs[0]
    for ind := 1; ind < len(iqs); ind++ {
        result[ind] = result[ind-1] + iqs[ind]
    }

    suffixSum := 0
    divNumber := len(iqs) - 1
    for ind := len(iqs) - 1; ind > 0; ind-- {
        result[ind] = (result[ind-1] + suffixSum) / divNumber
        suffixSum += iqs[ind]
    }
    result[0] = suffixSum / divNumber
    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!