Breaking LeetCode: Roman to Integer

I had two solutions to Roman to Integer that are, line for line, the same algorithm. One “beats 98%” on runtime. The other beats about 40%. Same big-O, same loop, same idea, and a wildly different bar on the little green results screen. So I did the obvious thing and went to find out what that timer is actually measuring, because as far as I can tell it isn’t the algorithm.

First, the problem, because the whole trick lives in one rule. Roman numerals map symbols to values (I=1, V=5, X=10, L=50, C=100, D=500, M=1000), and you mostly just write them big-to-small and add them up. LVIII is 50+5+1+1+1 = 58. The one wrinkle is the six subtractive pairs, where a smaller symbol sits in front of a bigger one: IV=4, IX=9, XL=40, XC=90, CD=400, CM=900. Every solution to this problem is just some way of paying attention to those six cases. That's it.

The literal solution: enumerate the six special cases.

The most honest first attempt is to translate the rulebook directly. There are six magic two-letter combos, so look for them explicitly.

var romanToInt = function(s) {
    const single = {I:1, V:5, X:10, L:50, C:100, D:500, M:1000};
    const pairs  = {IV:4, IX:9, XL:40, XC:90, CD:400, CM:900};

    let total = 0;
    let i = 0;
    while (i < s.length) {
        const two = s.substring(i, i + 2);   // peek at the next two chars
        if (pairs[two] !== undefined) {       // is it one of the six combos?
            total += pairs[two];              // yes -> take the pair value
            i += 2;                           // ...and consume both chars
        } else {
            total += single[s[i]];            // no  -> take the single value
            i += 1;                           // ...and consume one char
        }
    }
    return total;
};

Line by line it reads like the rules sound. Two lookup tables: one for symbols, one for the subtractive pairs. Walk left to right, at each step grab the next two characters and ask “is this a special pair?” If yes, add the pair’s value and jump ahead by two; if no, add the single symbol and step by one. The manual i += 2 / i += 1 is the part doing the real work: it's how you avoid double-counting a character you already spent inside a pair. It's verbose and it carries a second table around, but you can trust it on sight, which counts for something.

The elegant solution: stop enumerating, notice the pattern.

Here’s the move. You don’t need the six pairs at all. Look at what they have in common: every subtractive case is just a smaller symbol standing to the left of a larger one. So the entire rule collapses into a single comparison: if a symbol is smaller than its right-hand neighbor, subtract it; otherwise add it.

var romanToInt = function (s) {
    const d = { 'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000 };
    let res = 0;
    for (let i = 0; i < s.length; i++) {
        if (d[s[i + 1]] > d[s[i]]) {   // neighbor bigger -> we're the small half of a pair
            res -= d[s[i]];
        } else {
            res += d[s[i]];
        }
    }
    return res;
};

The body is four lines and one table. The clever bit is the boundary: on the last character s[i + 1] is undefined, so d[undefined] is undefined, and undefined > anything is false, which drops you into the else and adds. The end of the string handles itself for free, with no special case and no off-by-one. I find that quietly satisfying.

Trace MCMXCIV and watch the sign flip happen on exactly the subtractive symbols:

M(1000) : next C(100)  not bigger -> +1000   (running 1000)
C(100)  : next M(1000) bigger     ->  -100   (running  900)
M(1000) : next X(10)   not bigger -> +1000   (running 1900)
X(10)   : next C(100)  bigger     ->   -10   (running 1890)
C(100)  : next I(1)    not bigger ->  +100   (running 1990)
I(1)    : next V(5)    bigger     ->    -1   (running 1989)
V(5)    : no next char            ->    +5   (running 1994)

1. The C before M and the I before V go negative all on their own. The pattern generates the six special cases instead of memorizing them.

Now: how does the second one “beat the system”?

This is where I have to be a spoilsport, because the honest answer is that it mostly doesn’t, and figuring out why is the actually-interesting part. Both solutions are O(n) time, O(1) space. You cannot beat O(n) here: you have to look at every character at least once, so there is no algorithmic gap to exploit. The two solutions are in the same complexity class, so whatever the leaderboard is rewarding, it is not the complexity.

There is exactly one real difference between them, and it’s a constant factor, not a class. The literal version calls s.substring(i, i + 2) on every iteration, which allocates a fresh little string each time around the loop, n tiny throwaway objects for the garbage collector to deal with later. The elegant version never allocates anything inside the loop; it indexes straight into the original string with s[i] and s[i + 1] and does arithmetic. So if you squint, the second one does strictly less work per character, and that's a defensible reason for it to measure a hair faster. (This is the same category of thing that genuinely tanks a runtime: an accidental console.log is real I/O the harness counts, and a needless s.split('') allocates a whole array up front. I/O and allocation are the things that actually move the timer; arithmetic this small does not.)

But “a hair faster” is doing enormous lifting in that sentence, because the input maxes out around 15 characters. Either loop runs maybe fifteen times, so the real compute is microseconds either way, and fifteen tiny allocations is rounding error. What the timer reports is dominated by stuff that has nothing to do with your code: when V8’s JIT decides to optimize the function, harness overhead, and how loaded the grading box happens to be when you hit submit. It’s like timing a 15-meter dash with a wall clock that only ticks in whole seconds; the number you read off is mostly about the clock, not the runner.

And the percentile makes it look meaningful. Tens of thousands of submissions pile up in that 0–5ms band, so the histogram there is a dense wall. A 2ms jitter, pure dice, slides you across a huge slice of that wall, and suddenly “beats 40%” becomes “beats 98%” with zero change to your logic. The leaderboard is measuring luck in that range, plus whether you left a console.log in. ¯_(ツ)_/¯

Reflections. So “breaking LeetCode” turns out to mean: there’s nothing to break. The fast solution is better for honest reasons: it’s the cleaner expression of the idea, one table instead of two, the boundary handled by language semantics rather than a guard. But its rank is not a measurement of that. The most reliable way to “beat” the runtime chart, once you’re already at the right complexity, is to remove I/O and allocations and then resubmit until the noise lands on 0ms. That is a depressing optimization target and also completely true.

Treat the green number as a yes/no (did I hit the right complexity class?) and ignore the decimal places. If you want the flex, resubmit the elegant one five times and screenshot whichever run the dice rendered as “0ms, beats 100%.” It’s the same code each time, which is sort of the whole point.