Leetcode: Integer to Roman
Tags: java, leetcode, programming
Published: 2020-05-25 20:59:38

---
title: Leetcode: Integer to Roman
published: true
description: My solution to leetcode Integer to Roman problem
tags: java, leetcode, programming
series: programming-exercises
---
## 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](https://leetcode.com/problems/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](https://github.com/deepakvenkat/LeetCodeExamples/blob/master/src/com/company/RomanNumbers.java)

```java
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.