Go Coding with Asparagos: Can We Find the King in O(1) Space?

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 Fruit Sabotage 🍍.

Fruits united. Vegetables confused. Long live the King?

Problem

The election day has come to the Veggie Kingdom. All vegetables and fruits are casting their votes for the next King — each one voting for a single candidate.

Just before the election, a secret plan was revealed: all fruits secretly agreed to vote for the same fruit!

Honestly, we get it - fruits are clearly tired of the long-running vegetable monarchy. More and more vegetables are being added to smoothies, carrot cakes are gaining popularity... that would drive anyone bananas.

We don’t know which fruit they’ve chosen as their future King, but we do know this: they hold the majority. The total number of votes is N, and the number of fruit votes is greater than ⌊N / 2⌋.

Can we figure out who will be the next fruit King in the Veggie Kingdom?

A small note: there's a bit of a crisis in the Kingdom - all the budget was spent on saving potatoes from bugs, so we’re only allowed to use constant memory.

Input 🥦

A slice of integers - each integer represents a vote for some candidate.

Although we are vegetables and fruits, this is a serious election: all votes are anonymous - and there is at least one vote (mine).

Output 🥕

An integer - the value that occurs more than ⌊N / 2⌋ times, where N is the length of the input slice.
It’s guaranteed that such a value exists.

Examples 🥒:

• Example 1

  Input: [1, 2, 2]

  Output: 2

• Example 2

  Input: [3, 2, 3, 4, 3, 4, 3, 3]

  Output: 3

• Example 3

  Input: [10]

  Output: 10

Solution 💡

1. We only need two variables:

   • king: the current candidate. In the end, this will hold the majority value.

   • count: the current "confidence" in our king — how many votes they’ve received (after subtracting opposing votes).

2. We iterate through the input slice votes. At each step:

   • If count == 0, we set the current vote as the new potential king and increment count.

   • If vote == king, we increment count.

   • Otherwise (i.e., vote != king), we decrement count.

   This way, each vote against the current king cancels out one vote for them.
   

func findFruitKing(votes []int) int {
    var king int
    count := 0
    for _, vote := range votes {
        if count == 0 {
            king = vote
            count++
            continue
        }
        if king == vote {
            count++
        } else {
            count--
        }
    }
    return king
}

Why does it work?

This is the Boyer–Moore majority vote algorithm.

At the end of the loop, we have a candidate stored in the variable king, and a count - the number of votes that were definitely cast for this candidate.

Let’s imagine we remove those count votes from the full set. The remaining votes can be grouped into pairs: for every vote that increased count, there was a vote that decreased it. Each such pair consists of votes for different candidates.

Now, suppose the final candidate in king is not the majority. That would mean all votes for the real majority candidate are somewhere among those pairs. But that’s impossible — since each pair contains different votes, the majority candidate couldn’t fit entirely within them. There aren’t enough pairs to hold more than ⌊N / 2⌋ votes. So the final king must be the true majority.

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