Leetcode with Golang: Integer to Roman Conversion
A Golang solution with better runtime and memory performance than ~95% of accepted Golang solutions
Motivation
Recently, I decided that I wanted to prep for interviews, coding competitions, and learn a new programming language. To kill all of these birds with one stone, I decided to practice Leetcode problems daily with Golang. Solving algorithm problems in a language you aren’t familiar with forces you to think about the problem that actually needs to be solved, which helps you become a better developer. Of course, there are the initial hiccups with getting the correct syntax, but the most important thing is being able to solve problems regardless of tooling.
Soon after this journey began, I noticed that there isn’t nearly as much support for Leetcode problems in Golang as there is C++, Python, or Java. Given the history of those languages, its not surprising that a modern language like Go doesn’t have the same level of support. However, this article will be the first in a series of posts where I provide solutions to Leetcode problems in Golang.
DISCLAIMER: As mentioned before, I am still learning Go. If anyone has any recommendations to make my code more idiomatic, please provide in the comments.
Integer to Roman
Difficulty: Medium
Pass Rate: 58.9%
Problem Breakdown
This problem isn’t too difficult conceptually. Essentially, we are given a number and need to convert it to the roman numeral format. This problem is designed to test your logic around your ability to address edge cases. As noted in the problem description, there are six exceptions to when we break the standard rules for roman conversions. Those are the meat of what this problem wants us to address.
Something that is important to note is the constraints. We won’t be given a number greater than 3999. This is very important to notice, and I will explain why in the following sections
Naïve Solution
In both the naive and the optimized solution, the core part of our algorithm is essentially the same. We check to see if the target number is greater than a number corresponding to a roman numeral. If it is, we subtract the second number from the target number and repeat. We will eventually get to 0, and the loop will terminate.
For example:
7 is our target number
5 is our closest value with a roman numeral association
We subtract 5 from 7 and are left with 2
2 is our new target number
Repeat until 0
In between these operations, we would be adding the associated roman numeral to a string to form the correct corresponding sequence.
The naivety comes around the edge cases. We could write a long decision sequence of If/else branches to do hard comparisons against and determine the appropriate number to be displayed. Or, we could notice the explicit and implicit problem constraints
Optimized Solution
Our constraints are that the target number’s initial value will never be greater than 3999. This means that the largest roman numeral we would have to convert to is “M”. This helps to reduce uncertainty in how we handle the problem. Implicitly, another constraint is that the values and roman numerals mapped to them are fixed. “I” is always going to be 1, “IV” is always going to be 4.
How does this help us? Knowing this, we don’t have to worry about handling any uncertainty or complex cases. In fact, we could simply use slices or a map to tie these values together since they are fixed.
We can order the values to be in ascending order, and then we can process from the largest value to the smallest. Starting at the back will help us avoid out-of-bounds errors or maintaining multiple pointers to prevent said out-of-bounds errors. By the time the main pointer reaches zero, the problem will have already been solved.
Here is the optimized solution:
func intToRoman(num int) string {
var roman string = ""
var numbers = []int{1,4,5,9,10,40,50,90,100,400,500,900,1000}
var romans = []string{"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM", "M"}
var index = len(romans)-1
for num > 0 {
for numbers[index]<=num {
roman += romans[index]
num -= numbers[index]
}
index -= 1
}
return roman
}Closing Remarks
Here are the performance metrics for the optimized solution
As I am still learning Go, I was attempting to utilize maps in this solution instead of two separate slices. I was running into issues with extracting the keys in a concise way that fits my simple solution. If anyone has any recommendations, please provide!
