Roman to Integer – Leetcode 13 Solution

The “Roman to Integer” problem, Leetcode problem #13, is a classic interview question that tests your understanding of algorithms and data structures. In this problem, you’re tasked with converting a given Roman numeral string to an integer.

Problem Description

Roman numerals are represented by seven different symbols:

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

For example:

• III = 3
• IV = 4
• IX = 9
• LVIII = 58
• MCMXCIV = 1994

The challenge is to convert a Roman numeral string into an integer. The basic idea is that Roman numerals are written from largest to smallest from left to right, except for certain cases where a smaller numeral appears before a larger numeral to indicate subtraction.

Problem Constraints

• The Roman numeral string is guaranteed to be a valid Roman numeral.
• The input string can be at most 15 characters long.

Steps to Solve the Problem

To solve this problem, we can follow a straightforward approach:

1. Create a Map for Roman Numerals: First, create a map where each Roman character is mapped to its corresponding integer value.
2. Iterate Through the Roman String: As we traverse the Roman numeral string, we will check whether the current numeral is less than the next numeral. If it is, we subtract it from the result (since Roman numerals like IV represent 5 - 1 = 4). Otherwise, we add the numeral value to the result.

Approach 1: One Pass Solution (Greedy Approach)

This solution works by iterating through the string and applying the rule of subtraction when necessary. Here’s the step-by-step process:

1. Initialize a variable result to store the final integer.
2. Traverse the string from left to right:
   • If the current numeral is less than the next numeral, subtract the current numeral’s value.
   • Otherwise, add the current numeral’s value.
3. Return the result after the loop.

Java Code for Roman to Integer

import java.util.HashMap;

public class RomanToInteger {
    
    public int romanToInt(String s) {
        // Mapping Roman numerals to integer values
        HashMap<Character, Integer> romanMap = new HashMap<>();
        romanMap.put('I', 1);
        romanMap.put('V', 5);
        romanMap.put('X', 10);
        romanMap.put('L', 50);
        romanMap.put('C', 100);
        romanMap.put('D', 500);
        romanMap.put('M', 1000);
        
        int result = 0;
        
        // Traverse the Roman numeral string
        for (int i = 0; i < s.length(); i++) {
            // Get the value of the current numeral
            int currentValue = romanMap.get(s.charAt(i));
            
            // If not at the last character and the next character is larger, subtract the current value
            if (i < s.length() - 1 && currentValue < romanMap.get(s.charAt(i + 1))) {
                result -= currentValue;
            } else {
                result += currentValue;
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        RomanToInteger converter = new RomanToInteger();
        
        // Test cases
        System.out.println(converter.romanToInt("III"));  // Output: 3
        System.out.println(converter.romanToInt("IV"));   // Output: 4
        System.out.println(converter.romanToInt("IX"));   // Output: 9
        System.out.println(converter.romanToInt("LVIII")); // Output: 58
        System.out.println(converter.romanToInt("MCMXCIV")); // Output: 1994
    }
}

Explanation of the Code

1. Creating the Roman Map:
   • We create a HashMap called romanMap to map each Roman numeral character to its respective integer value.
   • For example, romanMap.put('I', 1);, romanMap.put('V', 5);, etc.
2. Iterating Through the String:
   • We loop through the given Roman numeral string using a for loop.
   • For each character, we check if the value of the current character is less than the next character. If true, this means we’re in a subtractive combination (like IV for 4), so we subtract the current character’s value from the result.
   • If the current character is greater than or equal to the next character, we add its value to the result.
3. Edge Cases:
   • The logic ensures that the subtractive combinations are handled correctly (e.g., IV, IX, XL, etc.).
   • If the numeral is simple, like III, the loop just adds the values of each character.

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the Roman numeral string. We iterate through the string once.
• Space Complexity: O(1), since the map of Roman numeral values is fixed and does not depend on the input size.

Conclusion

In this blog post, we’ve explored the Roman to Integer problem, discussed the optimal solution using a greedy approach, and implemented the solution in Java. This problem is not only a great way to practice string manipulation but also helps solidify the understanding of basic algorithms.

By following the solution explained here, you should be able to solve similar problems that involve converting different numeral systems into integers.

Feel free to test the code with additional test cases to ensure your solution works for all possible inputs!