Roman To Integer Leetcode Solution

How the Roman to Integer conversion actually works

The core mechanic is simpler than most people think. You iterate through the string from left to right, comparing each symbol's value to the one that follows it. If the current value is smaller than the next value, you subtract it. Otherwise, you add it. That single rule handles all the tricky cases like IV=4 or IX=9 without needing any special conditional branches for subtraction pairs. I remember hitting a wall on this one during a coding interview back when I was still fresh out of college. I wrote the naive approach—just summing values by looking up each character. It failed silently on the test case MCMLXXXIX, which is 1989. My code spat out 2091 because it was adding M, then C, then L, then X, X, X, I, X, I instead of recognizing that CM should be 900 and XC should be 90. I spent twenty minutes debugging before someone pointed out I wasn't accounting for the subtractive notation at all. That mistake cost me the offer, honestly. But it stuck with me.

Roman To Integer Leetcode Solution walkthrough

The cleanest way to implement this in practice is a reverse-pass approach. Go from right to left, keeping a running minimum. Each symbol's contribution depends on whether it's less than the minimum value you've seen so far. If it is, subtract it. If it's equal to or greater than the minimum, add it and update the minimum. This naturally handles all subtraction cases in a single pass without any substring matching. Here is the logic laid out plainly. Start with a variable for the total set to zero and another for the previous value set to zero. Traverse the string backwards. For each character, look up its integer value in a hash map or switch statement. Compare it to the previous value. If the current value is less than the previous, subtract it from the total. If it is greater than or equal, add it. Update the previous value and move to the next character. The hash map lookup for Roman numerals is straightforward. M equals 1000, D equals 500, C equals 100, L equals 50, X equals 10, V equals 5, and I equals 1. That is all seven symbols you need to handle. The problem guarantees valid input, so you do not need to validate the string format. That simplifies things considerably. Invalid Roman numerals like AAXX or VV are not part of the problem space.

Time complexity is O(n) where n is the length of the string. Each character is visited exactly once. Space complexity is O(1) since the hash map always contains exactly seven entries regardless of input size. The space usage is constant by definition.

Edge cases and practical gotchas

The most common failure point is treating subtraction pairs as independent additive operations. Another pitfall is iterating forward and trying to look ahead, which requires bounds checking and feels unnecessarily complicated. The reverse iteration sidesteps this entirely because you only need to remember one value from the previous step. I once shipped a version of this in a production tool that processed user-submitted Roman numeral strings. We rejected malformed input with a regex validator first. The regex pattern we used was specific enough to catch most obvious errors without being overzealous. Things like IIII for 4 got rejected even though some historical Roman inscriptions use that form. The LeetCode problem does not care about historical accuracy. It follows the standard modern conventions strictly. One thing people overlook is that the reverse approach naturally handles four-character subtractions correctly. Take MCMXCIV, which is 1994. Going right to left: V gets added (5), I gets subtracted (4), X gets subtracted (90 total), C gets added (190), M gets subtracted (190 minus 900 equals negative 710, wait no, let me trace this carefully). V is 5, I is 1 which is less than 5 so subtract to get 4, X is 10 which is greater than 1 so add to get 14, C is 100 which is greater than 10 so add to get 114, M is 1000 which is greater than 100 so add to get 1114, X is 10 which is less than 1000 so subtract to get 1104, M is 1000 which is greater than 10 so add to get 2104, C is 100 which is less than 1000 so subtract to get 1904. That is correct.

When this approach breaks down

The O(n) solution assumes valid Roman numeral input. If you encounter extended forms beyond the standard subtractive pairs, or if historical notation variations matter for your use case, this algorithm will produce incorrect results. For example, some medieval manuscripts use IIX for 8 instead of VIII. The standard algorithm would interpret IIX as 6, not 8. There is no universal consensus on what counts as a valid Roman numeral outside the LeetCode problem constraints. If you need to handle non-standard input, you would need a preprocessing step or a completely different parsing strategy. There is no single authoritative grammar for Roman numerals the way there is for Arabic digits. The backward-pass method is optimal for the standardized problem but fragile outside those boundaries.

Implementation notes

Using an array indexed by ASCII values is slightly faster than a hash map for this problem. You can map characters directly to integers with a small lookup table. The performance difference is negligible for the string lengths LeetCode tests against, but it avoids hash collisions and overhead. In competitive programming, that micro-optimization sometimes matters. In production code, readability usually wins. The code itself is roughly ten to fifteen lines depending on your language of choice. Python makes it trivial with a dictionary. C++ requires a bit more boilerplate for the lookup table but runs significantly faster. Java sits somewhere in between. The logic is identical across all implementations.