Roman To Integer (Leetcode Problem #13)
Java Solution for https://leetcode.com/problems/roman-to-integer/
If you prefer video format : https://youtu.be/BC-mHuUAaZA
- Find the enitre problem here : https://leetcode.com/problems/roman-to-integer/
- We have been given roman symbols with its value and we need to convert roman numeral to integer value.
input_x = "LVIII"
output_x = 58
L = 50; V=5; III=3
- There some facts about roman numerals. They are usually written from largest to smallest. In above example L is larger than V.
- There some instances mentioned below where subtraction is used.
- I can be placed before (V & X); X can be placed before (L & C); C can be placed before (D & M).
- So four is not written lie IIII , rather it is written as IV.
My Thought About Solution
- I can convert roman numeral string to char array.
- Since generally roman numerals are written largest to smallest usually except some cases where subtraction is needed, I can just check the case that if current char value is greater than next char value, if yes than i can just add the value of it to my sum.
- But if i have case where current roman numeral value is less than next roman value then i have to subtract it. For example if roman numeral is “IV”, in that case if my current char is I then sum = sum- Value of (I) due to subtraction rule of roman numerals
- Data structure: We need hashmap to store roman numerals and its corrosponding value
Time-complexity: O(length(N)) where N is the input roman numeral
Space-complexity: Constant Space since roman numerals are constant in time
1: Convert Input roman numeral to char array
2: Create Map of each roman numeral char and its corrosponding value
3: Traverse input char array
4: for each char array calculate
a: if current roman numeral value is greater than next roman
numeral - value then add the value of current roman numeral
to the total sum b: if the current roman numeral value is less than the next roman
numeral then we should subtract it from total sum
5: finally add the last numeral value to the sum and return the total sum
Our code beats 65% of the Java solution , not great solution but it does the job in O(N) time and O(1) space.
- This problem is good excercise to understand the use case of HashMap since we need to store constant key-values and lookup the keys and corrosponding values while traversing each character in input string.
- We shouldnt hesitate to use HashMap whenever we think we need to store and access data quickly without traversing entire data structure. This typically improves such performance on added space complexity
Let me know if you have some opinion on the solution in the comment section !