algoadvance

Leetcode 13. Roman to Integer

Problem Statement

The problem asks us to convert a Roman numeral into an integer. Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M.

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Roman numerals are usually 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 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.

Example:

Input: s = "III"
Output: 3

Input: s = "IV"
Output: 4

Input: s = "IX"
Output: 9

Input: s = "LVIII"
Output: 58

Input: s = "MCMXCIV"
Output: 1994

Clarifying Questions

1. Input Constraints:
   • Will the input always be a valid Roman numeral string?
   • What is the maximum length of the string?

   Let’s assume the input is always valid and the length can be up to 15 characters.

2. Case Sensitivity:
   • Should the Roman numerals always be in uppercase?

   Yes, Roman numerals will always be provided in uppercase.

3. Special Cases:
   • Are we expecting inputs like empty strings or other non-standard formats?

   No, inputs will always be valid Roman numerals.

Strategy

1. Initial Setup:
   • Create a map to hold Roman numeral values.
   • Iterate through the input string from left to right.
2. Core Logic:
   • Initialize an int variable to store the final integer result.
   • Traverse through each character of the string.
   • For each character, compare its value with the value of the next character:
     • If the current character’s value is smaller than the next character’s value, subtract its value from the final result.
     • Otherwise, add its value to the final result.
3. Edge Cases:
   • Single character input.
   • Numerals consisting of only one type of character, e.g., “IIII”.

Code

import java.util.HashMap;
import java.util.Map;

public class RomanToInt {
    public static int romanToInt(String s) {
        Map<Character, Integer> romanToIntMap = new HashMap<>();
        romanToIntMap.put('I', 1);
        romanToIntMap.put('V', 5);
        romanToIntMap.put('X', 10);
        romanToIntMap.put('L', 50);
        romanToIntMap.put('C', 100);
        romanToIntMap.put('D', 500);
        romanToIntMap.put('M', 1000);

        int result = 0;
        int length = s.length();

        for (int i = 0; i < length; i++) {
            int currentValue = romanToIntMap.get(s.charAt(i));
            if (i + 1 < length) {
                int nextValue = romanToIntMap.get(s.charAt(i + 1));
                if (currentValue < nextValue) {
                    result -= currentValue;
                } else {
                    result += currentValue;
                }
            } else {
                result += currentValue;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(romanToInt("III")); // Output: 3
        System.out.println(romanToInt("IV"));  // Output: 4
        System.out.println(romanToInt("IX"));  // Output: 9
        System.out.println(romanToInt("LVIII")); // Output: 58
        System.out.println(romanToInt("MCMXCIV")); // Output: 1994
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the input string. This is because we are iterating over the string once.
• Space Complexity: O(1), because the space required for storage of the map and variables does not depend on the input size (constant memory for the map of size 7).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?