DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Roman to Integer

#algorithms #beginners #interview #java
leetcode.com

Problem Statement

Roman numerals are represented using:

I → 1
V → 5
X → 10
L → 50
C → 100
D → 500
M → 1000
Enter fullscreen mode Exit fullscreen mode

Convert a Roman numeral into its integer value.

Brute Force Intuition

In an interview, you can explain it like this:

Traverse the string from left to right. For each character, check whether it forms a special subtraction pair like IV, IX, XL, etc. Handle those pairs separately.

This works but requires checking multiple special cases.

Complexity

  • Time Complexity: O(N)
  • Space Complexity: O(1)

Brute Force Code 

// Check IV, IX, XL, XC, CD, CM separately
Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Approach

Observe the pattern:

If a smaller value appears before a larger value,

it should be subtracted.

Otherwise,

it should be added.

Examples:

IV

1 < 5

Answer = 5 - 1
Enter fullscreen mode Exit fullscreen mode 
VI

5 > 1

Answer = 5 + 1
Enter fullscreen mode Exit fullscreen mode

Pattern Recognition

Whenever you see:

  • Roman Numerals
  • Previous/Next Character Comparison

Think:

Linear Traversal

Key Observation

Traverse from left to right.

If:

Current Value

<

Next Value
Enter fullscreen mode Exit fullscreen mode

Subtract.

Otherwise,

Add.

Optimal Java Solution 

class Solution {

    public int romanToInt(String s) {

        HashMap<Character, Integer> map = new HashMap<>();

        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);

        int ans = 0;

        for (int i = 0; i < s.length(); i++) {

            int curr = map.get(s.charAt(i));

            if (i < s.length() - 1 &&
                curr < map.get(s.charAt(i + 1))) {

                ans -= curr;

            } else {

                ans += curr;
            }
        }

        return ans;
    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run

Input 

MCMIV
Enter fullscreen mode Exit fullscreen mode

Process:

M = +1000

C < M

-100

M = +1000

I < V

-1

V = +5
Enter fullscreen mode Exit fullscreen mode

Answer:

1904
Enter fullscreen mode Exit fullscreen mode

Why This Works?

Whenever a smaller numeral appears before a larger numeral,

Roman notation represents subtraction.

Otherwise,

the numeral contributes positively.

Complexity Analysis

Metric Complexity
Time Complexity O(N)
Space Complexity O(1)

Interview One-Liner

Traverse the Roman numeral once. Add the current value if it's greater than or equal to the next value; otherwise subtract it.

Pattern Learned 

Current < Next

↓

Subtract

-----------------

Current ≥ Next

↓

Add
Enter fullscreen mode Exit fullscreen mode

Similar Problems

  • Roman to Integer
  • Integer to Roman
  • Excel Sheet Column Number
  • Excel Sheet Column Title

Memory Trick

Think:

Smaller Before Bigger

↓

Subtract

Else

↓

Add
Enter fullscreen mode Exit fullscreen mode

Mental Model 

Compare

Current

↓

Next

↓

Add / Subtract
Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

"Roman Numerals"

your brain should immediately think:

Compare Current with Next 🚀

Top comments (0)