DEV Community: Archdemon

Roman Numerals in Go: The Self‑Correcting One‑Pass Trick

Archdemon — Wed, 17 Dec 2025 15:05:16 +0000

Today we’ll look at a classic interview problem: converting a Roman numeral to an integer.

To be honest, this is not something most of us use in real life. In 10+ years of programming, I haven’t needed it once. But it does show up in interviews, and more importantly, it’s a great problem for learning how to reason about algorithms instead of memorising tricks.

Let’s take it step by step.

Understanding the Problem

You’re given a string made up of Roman numeral characters:

I, V, X, L, C, D, M

Each character has a fixed numeric value:

I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000

Your task is simple:

Convert the Roman numeral string into its integer value.

The problem guarantees that:

the input is always valid
you don’t need to worry about malformed Roman numerals

That lets us focus entirely on the logic.

A Straightforward (Brute‑Force) Approach

The most natural way to solve this is to lean directly on the Roman numeral rules.

Some pairs are special:

IV = 4
IX = 9
XL = 40
XC = 90
CD = 400
CM = 900

Everything else is just addition.

So a brute‑force approach looks like this:

Walk through the string from left to right
If the current character and the next character form a subtractive pair, add that value and skip both
Otherwise, add the value of the current character and move on

This works. It’s clear. And for this problem, it’s completely acceptable.

But there’s a small cost:

you have to explicitly encode all subtractive pairs
you need lookahead (i + 1), which adds branching and edge checks

At this point, it’s reasonable to pause and ask:

Can we do this in a single pass, without treating some cases as special?

That question leads to a more interesting solution.

The Core Idea

Here’s the idea we’ll build everything on:

Always add. Correct only when proven wrong.

Roman numerals follow two simple rules:

Values normally add
If a smaller value appears before a larger one, the smaller value should be subtracted

Examples:

VI = 5 + 1 = 6
IV = 5 − 1 = 4
XL = 50 − 10 = 40

Instead of handling these cases up front, we’ll assume everything adds — and fix things only when we realise that assumption was wrong.

Pause for a Moment

Before looking at code, stop here and think about this question:

If I always add values, how would I undo a mistake when I later discover that a value should have been subtracted?

Keep that question in mind. The answer is the key to the whole solution.

The Invariant (This Is Everything)

The algorithm relies on one simple invariant:

At the start of each iteration, the running total already includes the previous symbol exactly once.

Everything that follows is just a consequence of that statement.

Why the Correction Works

Let’s walk through a concrete example: "XL".

Step 1: `'X'`

Value = 10
There is no previous symbol yet
We add 10

Running total:

Nothing to fix.

Step 2: `'L'`

Value = 50
The previous value was 10
According to Roman rules, that 10 should have been subtracted

But here’s the important part:

We already added 10 in the previous step.

To correct this, we need to:

remove the earlier +10
apply -10 instead

That’s a net change of:

-2 * previous_value

So the update becomes:

current_value - 2 * previous_value

Which gives:

50 - 2*10 = 30

Add that to the running total:

10 + 30 = 40

Correct.

Why We Subtract the Previous Value

This part is subtle and important.

We are not correcting the total.
We are correcting the contribution of the previous symbol.

previous is just the numeric value of the symbol we saw last
the running total already includes it once

That’s why this line works even on the first iteration:

current - 2*previous

When previous is 0, there’s nothing to correct.

The Code (Go)

Once the idea is clear, the code becomes very straightforward.

func romanToInt(s string) int {
    num, prev := 0, 0

    for _, r := range s {
        curr := val(r)

        if curr <= prev {
            num += curr
        } else {
            num += curr - 2*prev
        }

        prev = curr
    }

    return num
}

func val(r rune) int {
    switch r {
    case 'I': return 1
    case 'V': return 5
    case 'X': return 10
    case 'L': return 50
    case 'C': return 100
    case 'D': return 500
    case 'M': return 1000
    }
    return 0
}

Why This Is a Good Interview Solution

Single pass
O(1) extra space
No lookahead
No special cases

More importantly, it demonstrates that you can:

maintain a clear invariant
make simple assumptions
correct them cleanly when new information appears

One‑Sentence Mental Model

“I always add the current value. If I later realise the previous value should have been subtracted, I undo it by subtracting it twice.”

If that sentence makes sense, the solution will always make sense.

Final Thoughts

This problem isn’t really about Roman numerals.

It’s about writing algorithms that:

start with a simple assumption
stay linear and readable
correct themselves when needed

Once you see it that way, the 2 * previous no longer feels clever, it feels inevitable.

Final Thought

My goal here was to help you actually understand why this algorithm works and not just walk away with something to memorize.

Once that idea clicks, implementing it in your favorite language becomes a fun little exercise.

If this helped you see the problem differently, feel free to share it with someone who might enjoy the same “aha” moment. And if you have questions, feedback, or a different mental model altogether, drop a comment. Those conversations are half the fun.

Happy coding 👋

Majority Element: Easy Problem, Sneaky Insight

Archdemon — Sun, 14 Dec 2025 14:35:29 +0000

The Majority Element problem on LeetCode looks like one of those questions you expect to solve in two minutes and immediately forget about.

Input: an array of numbers
Output: the number that appears more than n/2 times
(n is the size of the array)

That’s it. No tricks hiding in the corner.

LeetCode even tells you upfront:
👉 “The majority element always exists.”

So your brain does the obvious thing:

“Cool. I’ll just count.”

99% of the time, that’s exactly the right instinct.

The Obvious Solution (And Why It’s Perfectly Fine)

You loop through the array, count how many times each number appears, and return the one whose count is greater than n/2.

Example:

Input:  [1, 1, 2, 2, 2, 3, 3]
Counts: {1: 2, 2: 3, 3: 2}

2 appears more than half the time. Done.

Go Implementation

func majorityElement(nums []int) int {
    counts, n := make(map[int]int), len(nums)

    for _, num := range nums {
        counts[num]++
    }

    for k, v := range counts {
        if v > n/2 {
            return k
        }
    }

    return -1 // unreachable due to problem guarantee
}

Complexity

Time: O(N)
Space: O(N)

This solution is clean, readable, and correct.

In real life, you’d probably stop here, ship it, and move on.

The Follow-Up That Changes the Mood

Then LeetCode adds one extra line:

Could you solve it in linear time and O(1) space?

Translation:

“Same problem. No hashmap.”

This is where the problem quietly stops being trivial and starts testing how you think.

⏸️ Pause Here

Before reading further, I’d genuinely recommend pausing for a moment and thinking about this yourself:

What does “more than half” actually guarantee?
What information do you really need to keep around?
If counting everything was forbidden, what would you track instead?

If you already know the solution, wonderful read along for a fun mental model.
If you don’t, that’s completely fine. It wasn’t obvious to me the first time either.

When you’re ready, keep going.

A Mental Model Instead of Math

Let’s stop thinking in terms of arrays and counters for a second.

Instead, imagine this.

Teams, Players, and Rounds

Think of each number as a team.
Each occurrence of that number is a player on that team.

There are multiple teams
One team has more than half of all players
The game plays out in rounds

Rules of the Game

In each round, one player steps forward
If two different teams step forward, both players are eliminated
Eliminated players never come back
A team can only keep playing if it still has unused players

Here’s the key part:

The outcome of a round doesn’t matter.
What matters is who still has players left.

What Inevitably Happens

Smaller teams run out of players pretty quickly.
Once they’re empty, they’re done.

The majority team:

Loses players too
Gets beaten
Cancels others out

But because it started with more players than all the other teams combined, it can never be eliminated completely.

By the end:

Either it’s the only team left
Or it’s the only team that can still send a player

That team is the majority element.

No tricks.
No luck.
Just inevitability.

Turning That Into Code

Now let’s map that mental model back to code.

candidate → the team currently sending players
count → how many more players that team has relative to others

As you walk through the array:

If count == 0 → pick the current number as the new team
Same number again → that team sends another player (count++)
Different number → two players clash and are gone (count--)

You’re not tracking wins.
You’re tracking who can still play.

Go Implementation (O(1) Space)

func majorityElement(nums []int) int {
    candidate, count := 0, 0

    for _, num := range nums {
        if count == 0 {
            candidate = num
        }

        if num == candidate {
            count++
        } else {
            count--
        }
    }

    return candidate
}

Complexity

Time: O(N)
Space: O(1)

Because the problem guarantees a majority element, no second pass is needed.

Trivia

This algorithm was introduced by Robert S. Boyer and J. Strother Moore, and is known as the Boyer–Moore Voting Algorithm.

You can think of it as a different way of running an election:

Instead of counting every vote up front,
candidates face off round by round,
and you only keep track of who still has supporters left.

By the end, the candidate who survives isn’t just popular —
they’re mathematically guaranteed to be the majority.

Less bookkeeping.
Same result.
Much more clever.

Side-by-Side Comparison

Approach	Time	Space	Obvious?	Interview Value
HashMap counting	O(N)	O(N)	Yes	Medium
Boyer–Moore voting	O(N)	O(1)	No	High

The hashmap solution is practical.
The Boyer–Moore solution is conceptual.

Interviewers like the second one not because it’s “better”,
but because it shows you can reason from constraints and guarantees.

Appendix: When Would You Actually Use This?

By now, you might be wondering:

“This is clever… but when would I ever use this instead of a hashmap?”

That’s a fair question.

The Boyer–Moore Voting Algorithm is not a general-purpose replacement for counting. It shines only when a strong guarantee exists.

You usually reach for it when all three of these are true:

You’re dealing with large or streaming data
A majority element is guaranteed
You want predictable, minimal memory usage

Streaming or One-Pass Data

If data comes in as a stream (logs, events, messages), you may not want to store everything just to count it.

Boyer–Moore lets you:

process elements one at a time
keep constant memory
stop at any point with a meaningful candidate

Large Inputs and Performance-Sensitive Code

Hashmaps aren’t just “memory”.

They involve:

allocations
resizing
hashing
cache misses
garbage collection

Boyer–Moore avoids all of that. It’s fast, cache-friendly, and predictable.

Memory-Constrained Environments

In embedded systems or edge devices, even small data structures matter.

An O(1) space algorithm:

uses fixed memory
behaves consistently
fails less spectacularly

That simplicity is a feature.

When Not to Use This Algorithm

Just as important:

Don’t use Boyer–Moore if:

a majority element is not guaranteed
you need exact frequencies
you need top-K elements
you care about distribution, not dominance

In those cases, a hashmap or sorting is the right tool.

A Simple Rule of Thumb

Use Boyer–Moore when dominance matters
Use a hashmap when distribution matters

Both are good tools. They just solve different problems.

Final Thought

My goal here was to help you actually understand why this algorithm works and not just walk away with something to memorize.

Once that idea clicks, implementing it in your favorite language becomes a fun little exercise.

Happy coding 👋

DEV Community: Archdemon

Roman Numerals in Go: The Self‑Correcting One‑Pass Trick

Understanding the Problem

A Straightforward (Brute‑Force) Approach

The Core Idea

Pause for a Moment

The Invariant (This Is Everything)

Why the Correction Works

Step 1: 'X'

Step 2: 'L'

Why We Subtract the Previous Value

The Code (Go)

Why This Is a Good Interview Solution

One‑Sentence Mental Model

Final Thoughts

Final Thought

Majority Element: Easy Problem, Sneaky Insight

The Obvious Solution (And Why It’s Perfectly Fine)

Go Implementation

Complexity

The Follow-Up That Changes the Mood

⏸️ Pause Here

A Mental Model Instead of Math

Teams, Players, and Rounds

Rules of the Game

What Inevitably Happens

Turning That Into Code

Go Implementation (O(1) Space)

Complexity

Trivia

Side-by-Side Comparison

Appendix: When Would You Actually Use This?

Streaming or One-Pass Data

Large Inputs and Performance-Sensitive Code

Memory-Constrained Environments

When Not to Use This Algorithm

A Simple Rule of Thumb

Final Thought

Step 1: `'X'`

Step 2: `'L'`