Roman to Integer

Parse a Roman numeral into its integer value — subtract when a smaller numeral precedes a larger.

Easy
Time O(N) Space O(1)
LeetCode
3 min read
hash-map strings

Problem#

Convert a Roman numeral string (I, V, X, L, C, D, M) to its integer value.

Examples#

  • "III"3.
  • "LVIII"58.
  • "MCMXCIV"1994.

Constraints#

  • 1 <= s.length <= 15, s is a valid Roman numeral in [1, 3999].

Hints#

Hint
Each character contributes its value, but subtract instead of add when followed by a strictly larger character.

Approach#

Map each Roman symbol to its value. Walk left to right; if value[s[i]] < value[s[i+1]], subtract; else add.

Solution#

Roman to Integer
class Solution {
public:
int romanToInt(string s) {
unordered_map<char,int> v = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int n = s.size(), ans = 0;
for (int i = 0; i < n; ++i) {
if (i + 1 < n && v[s[i]] < v[s[i+1]]) ans -= v[s[i]];
else ans += v[s[i]];
}
return ans;
}
};

Editorial#

Subtractive notation (IV = 4, CM = 900) is the only twist. The rule “smaller before larger means subtract” is purely local — one lookahead character is all we need. For raw speed, replace the hash map with a 128-entry int[] indexed by character.

Complexity#

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

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.