Leetcode: Integer to Roman

Background

Recently, I decided to solve some of the problems in leetcode.com for fun and practicing my java which I have not used in a while. I decided to document my thought process as I solve these problems. Any feedback on improving the solution is welcome. This is not really meant to be instructive but rather just a journal for my own thought process.

Problem

Integer to Roman

So the problem is straightforward. Given an integer value, return the roman numeral version of it. (In this specific problem, the input range was limited between 1 and 3999)

Solution whiteboarding

I had previously solved the roman numeral to integer problem and similar to that solution, my first idea was to create a map with all possible values -> symbol combination.

This yielded this :

{
    1000: M,
    500: D,
    100: C
   //  … so on
}

First idea : Division (incorrect?)

Having solved number based problems before, my first thought was to use a division based solution. I thought I could keep a static highestDivisor
value and then somehow step through the values by dividing by the highest divisor possible for a number (for e.g. for 432 the highest divisor would be 100)

Roadblock 1: 5xx and special cases

The first roadblock I hit was that there was 5xx (5, 50, so on) so dividing by 10 might not be a very good way? Also do I do about the special cases?

To address the second problem first, I added the special cases to the map.

{
    1000: M,
    900: CM,
    500: D,
    400: CD,
    100: C
   //  … so on
}

But I still had the issue with division.

Second idea

So I thought my initial assumption to try and parse the numbers were right. But division might not be the best approach. Maybe, I could try just subtraction?

I had created the map from highest to lowest values. So, the solution I came up with was the subtract (when I was done, I checked the solutions tab of leetcode the first solution was similar to this)

So the steps would be :

1. Starting with the highest value in the map see if subtracting the number gives a positive number
2. If I can't move to the next smaller value.
3. When I find the value which can be subtracted from the number, concat the corresponding symbol and keep subtracting until you can't subtract anymore.

This yielded the following java method (You can find my whole solution here

Set<Integer> keys = valueSymbolMap.keySet();
Integer [] keysI = keys.toArray(new Integer[keys.size()]);
String result = "";
int i = 0;
while (num > 0) {
    while (i < keysI.length) {
        if (num - keysI[i] >= 0) {
            result = result.concat(valueSymbolMap.get(keysI[i]));
            num -= keysI[i];
        } else {
            i+= 1;
        }
    }
}
return result;

Implementation Notes:

1. I used a LinkedHashMap to make sure I get the keyset in the same order as the element added always.
2. I can probably do without the double while loop.

Final Thoughts

I wonder if there is a more elegant solution to this without some of the hardcoded values but I couldn't think of any.