Roman To Integer Problem

Problem

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Examples

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 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.

Solution

Method 1 - Using Hashtable Greedily

The primary challenge in counting Roman numerals arises when a numeral acts as a subtractive value rather than an additive one. For instance, in “IV”, the value of “I” (1) is subtracted from the value of “V” (5). Apart from these cases, you simply sum the values of all the numerals.

Subtractive numerals can be recognized because they appear before a larger numeral. To handle this, we track two variables: prev and curr. For IV, prev is I and curr is V. When prev is less than curr, we subtract prev. After this, we continue by adding prev.

Code

Java

public int romanToInt(String s) {
	if (s == null || s.length() == 0) {
		return 0;
	}

	Map<Character, Integer> map = Map.of(
		'M', 1000,
		'D', 500,
		'C', 100,
		'L', 50,
		'X', 10,
		'V', 5,
		'I', 1
	);

	int sum = 0;
	int prev = map.get(s.charAt(0));
	int curr = 0;

	for (int i = 1; i<s.length(); i++) {
		curr = map.get(s.charAt(i));

		if (prev<curr) {
			sum -= prev;
		} else {
			sum += prev;
		}

		//udpare prev because it is like sliding window
		prev = curr;
	}

	sum += prev; //corner case when only one digit, we need to let sum = prev, so we add prev, not next
	return sum;
}

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(1) as we are storing 7 values in map

Problem#

Examples#

Solution#

Method 1 - Using Hashtable Greedily#

Code#

Java#

Complexity#