Roman to Integer (LeetCode 13) – C++ Solution with Dry Run

Introduction

Roman to Integer (LeetCode 13) is one of the most common beginner string parsing problems asked in coding interviews. Although the rules of Roman numerals are simple, the challenge lies in correctly handling the six subtractive combinations such as IV (4) and IX (9) while scanning the string efficiently.

In this article, we'll build the solution step by step. We'll begin with the intuitive left-to-right approach, improve it using a cleaner right-to-left traversal, and finally discuss a small constant-factor optimization using a switch statement. Along the way, you'll understand why the algorithm works, not just how to memorize it.

2. Problem Statement

Description

Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M.

Usually, Roman numerals are written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five, we subtract it making four. The same principle applies to the number nine, which is written as IX.

There are six distinct instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Constraints

• $1 \le s.length \le 15$
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Example 1

Input: s = "III"

Output: 3

Explanation: III = 1 + 1 + 1 = 3.

Example 2

Input: s = "LVIII"

Output: 58

Explanation: L = 50, V= 5, III = 3.

Example 3

Input: s = "MCMXCIV"

Output: 1994

Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Approach 1: Left-to-Right Lookahead (The Intuitive Approach)

Intuition

When humans read a Roman numeral, we scan from left to right. We look at a character, and then we peek at the next character.

• If the current character's value is greater than or equal to the next character's value, we simply add it to our total. (e.g., in "VI", V > I, so 5 + 1).
• If the current character's value is less than the next character's value, it means we've encountered a subtractive pair. We must subtract the current character's value from our total. (e.g., in "IV", I < V, so -1 + 5).

To implement this programmatic translation, we can use a Hash Map (std::unordered_map in C++) to bind each Roman character to its integer equivalent.

Algorithm

1. Initialize an unordered_map containing the 7 Roman symbols and their integer values.
2. Initialize an accumulator variable total = 0.
3. Iterate through the string s from index 0 to n-1.
4. For each character s[i]:
   • Check if there is a next character s[i+1] AND if the value of s[i] is strictly less than the value of s[i+1].
   • If true, subtract the value of s[i] from total.
   • If false (or if it's the last character), add the value of s[i] to total.
5. Return the total.

c++ code:

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int romanToInt(string s) {

        // Create a hash map that stores the integer value
        // corresponding to each Roman numeral.
        unordered_map<char, int> romanMap = {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000}
        };

        // Variable to store the final integer value.
        int total = 0;

        // Store the length of the string to avoid
        // calling s.length() repeatedly.
        int n = s.length();

        // Traverse every Roman numeral in the string.
        for (int i = 0; i < n; i++) {

            // Check whether there is a next character
            // and whether the current Roman numeral is
            // smaller than the next Roman numeral.
            //
            // Examples:
            // IV : I < V  -> subtract I
            // IX : I < X  -> subtract I
            // XL : X < L  -> subtract X
            //
            // The condition (i + 1 < n) ensures we do not
            // access beyond the last character.
            if (i + 1 < n && romanMap[s[i]] < romanMap[s[i + 1]]) {

                // Current value should be subtracted.
                total -= romanMap[s[i]];

            } else {

                // Otherwise, add the current value.
                //
                // Examples:
                // VI : V > I  -> add V, add I
                // XV : X > V  -> add X, add V
                total += romanMap[s[i]];
            }
        }

        // Return the final integer.
        return total;
    }
};

Visualisation:

Complexity Analysis

• Time Complexity: $O(n)$, where $n$ is the length of the string. We iterate through the string exactly once. Map lookups take $O(1)$ average time.
• Space Complexity: $O(1)$. The size of the map is strictly fixed at 7 key-value pairs, regardless of the input string length.

Why This Approach Has Friction

While accurate, this approach has two minor inefficiencies that backend systems programming seeks to eliminate:

1. Bounds Checking: In every single iteration, we evaluate i + 1 < n. This is a small but constant overhead.
2. Double Map Lookups: When a subtraction case happens, we look up s[i] and s[i+1]. On the next iteration, we will look up s[i+1] again as the new s[i]. We are performing redundant hashing.

We can solve both issues by changing our iteration direction.

Approach 2: Right-to-Left Processing (Logical Optimization)

Intuition

Instead of looking ahead (which requires checking if we've fallen off the edge of the string), what if we look backwards?

By iterating from right to left, we process the smallest (or logically "final") components of the number first. We can simply keep a tracking variable of the previous_value we encountered.

• If the current character is greater than or equal to the previous_value, we add it to our total.
• If the current character is strictly less than the previous_value, we subtract it.

This brilliantly eliminates the need to check string boundaries (i + 1 < n) and ensures we only evaluate each character exactly once!

Algorithm

1. Initialize the romanMap.
2. Initialize total = 0 and prev_val = 0.
3. Iterate from $i = n - 1$ down to $0$.
4. Retrieve the current_val from the map for s[i].
5. If current_val < prev_val, subtract current_val from total.
6. Else, add current_val to total.
7. Update prev_val = current_val.
8. Return total.

Dry Run

Input: s = "MCMXCIV" (Reading right-to-left)

C++ Code:

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> romanMap = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
            {'C', 100}, {'D', 500}, {'M', 1000}
        };
        
        int total = 0;
        int prev_val = 0;
        
        // Iterate backwards
        for (int i = s.length() - 1; i >= 0; i--) {
            int current_val = romanMap[s[i]];
            
            if (current_val < prev_val) {
                total -= current_val;
            } else {
                total += current_val;
            }
            // Update prev_val for the next iteration
            prev_val = current_val;
        }
        
        return total;
    }
};

Complexity Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(1)$.

The Lingering Issue: The Overhead of Hashing

Optimization Note: Since there are only seven possible Roman numeral characters, we can replace the hash map with a switch statement or a fixed lookup array to avoid hashing overhead. While this reduces constant factors, it does not change the overall time complexity and offers little practical benefit for this problem due to the small input size.

Edge Cases Discussed

Because the problem guarantees that the input s is a valid Roman numeral in the range [1, 3999], we are spared from extensive validation logic (like checking if someone entered "IIII" or "VV"). However, understanding why our code works structurally is vital:

1. Maximum Value ("MMMCMXCIX"): Parses flawlessly. The logic easily handles the consecutive 'M's by adding them sequentially before applying the subtractive pairs.
2. Consecutive Subtractions: Valid Roman numerals never contain chained subtractions (e.g., "IXC" is invalid; it should be "XCI" for 91). Our logic naturally expects this standard formatting.
3. Single Characters: "X" skips the subtraction block entirely and just adds 10.

Common Mistakes

1. Incorrect Map Initialization: In C++, forgetting that single quotes ('I') denote a char and double quotes ("I") denote a std::string. The map must be unordered_map<char, int>.
2. Left-to-Right Out of Bounds: Attempting romanMap[s[i+1]] without checking if i + 1 < s.length(). This will cause undefined behavior or memory access violations.
3. Overcomplicating the Subtraction Rule: Some candidates try to string-match exact pairs like "IV", "IX", "XL" using s.substr(). This inflates the code length and makes scaling difficult. The mathematical rule (curr < prev) handles all 6 cases inherently without hardcoding them.

code link:

https://leetcode.com/problems/roman-to-integer/description/