Roman to Integer

🎯

Roman to Integer

easyMATHAmazonGoogleMicrosoft

Imagine you are building a historical data parser that needs to convert ancient Roman numerals into modern integers for analysis.

💡 This problem involves converting a string representation of Roman numerals into an integer. Beginners often struggle because Roman numerals use subtractive notation (like IV for 4), which requires careful lookahead logic rather than simple summation.

📋

Problem Statement

Given a string representing a Roman numeral, convert it to an integer. Roman numerals are composed of the symbols I, V, X, L, C, D, and M, which represent values 1, 5, 10, 50, 100, 500, and 1000 respectively. The numeral is valid and follows standard subtractive notation rules. Return the integer value corresponding to the Roman numeral.

1 ≤ length of input string ≤ 15Input string contains only valid Roman numeral charactersRoman numeral is guaranteed to be valid and in the range from 1 to 3999

💡

Example

Input"III"

Output3

Each 'I' adds 1, so 1 + 1 + 1 = 3.

Input"IV"

Output4

'I' before 'V' means 5 - 1 = 4.

Input"IX"

Output9

'I' before 'X' means 10 - 1 = 9.

Input"LVIII"

Output58

L=50, V=5, III=3, total 50 + 5 + 3 = 58.

Input"MCMXCIV"

Output1994

M=1000, CM=900, XC=90, IV=4, total 1000 + 900 + 90 + 4 = 1994.

• Single character input 'I' → 1
• Largest valid numeral 'MMMCMXCIX' → 3999
• Subtractive pairs at string end 'IX' → 9
• No subtractive pairs 'VIII' → 8

⚠️

Common Mistakes

Not handling subtractive pairs correctly

Incorrect output for inputs like 'IV' or 'IX'

✅ Implement lookahead logic to subtract when current symbol is less than next

Accessing next character without boundary check

Index out of range runtime error

✅ Always check if next index is within string length before accessing

Using incorrect symbol values

Wrong final integer output

✅ Use a correct and consistent mapping of Roman symbols to integers

Ignoring invalid input cases

Solution may produce incorrect results or crash

✅ Add validation or assume input is always valid as per problem statement

Using recursion or complex data structures unnecessarily

Overcomplicated solution, possible stack overflow

✅ Use simple iterative approach with constant space

🧠

Brute Force (Check Each Symbol and Subtractive Pair Explicitly)

💡 This approach exists to build intuition by explicitly checking each character and its next character to decide whether to add or subtract values. It helps beginners understand the subtractive rule by brute force scanning.

Intuition

Iterate through the string, at each character check if the next character forms a subtractive pair. If yes, subtract the current value; otherwise, add current value. Sum all values to get the integer.

Algorithm

1. Create a map from Roman symbols to their integer values.
2. Initialize result to 0.
3. Iterate over the string from left to right.
4. For each character, if the next character exists and its value is greater, subtract current value; else add current value.
5. Return the accumulated result.

💡 The key difficulty is remembering to look ahead and decide whether to add or subtract, which is not obvious at first glance.

</>

Code

def romanToInt(s: str) -> int:
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    result = 0
    for i in range(len(s)):
        value = roman_map[s[i]]
        if i + 1 < len(s) and roman_map[s[i]] < roman_map[s[i + 1]]:
            result -= value
        else:
            result += value
    return result

# Driver code
if __name__ == '__main__':
    test_cases = ['III', 'IV', 'IX', 'LVIII', 'MCMXCIV']
    for tc in test_cases:
        print(f'{tc} -> {romanToInt(tc)}')

Line Notes

roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}Defines the value of each Roman numeral symbol for quick lookup.

for i in range(len(s))Iterates over each character index to process symbols sequentially.

value = roman_map[s[i]]Gets the integer value of the current Roman symbol.

if i + 1 < len(s) and roman_map[s[i]] < roman_map[s[i + 1]]Checks if the current symbol is less than the next symbol to detect subtractive pairs.

result -= valueSubtracts the current value when a subtractive pair is detected.

else:Handles the case when no subtractive pair is detected.

result += valueAdds the current value when no subtractive pair is detected.

import java.util.*;
public class RomanToInteger {
    public static int romanToInt(String s) {
        Map<Character, Integer> romanMap = new HashMap<>();
        romanMap.put('I', 1);
        romanMap.put('V', 5);
        romanMap.put('X', 10);
        romanMap.put('L', 50);
        romanMap.put('C', 100);
        romanMap.put('D', 500);
        romanMap.put('M', 1000);
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            int value = romanMap.get(s.charAt(i));
            if (i + 1 < s.length() && value < romanMap.get(s.charAt(i + 1))) {
                result -= value;
            } else {
                result += value;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String[] testCases = {"III", "IV", "IX", "LVIII", "MCMXCIV"};
        for (String tc : testCases) {
            System.out.println(tc + " -> " + romanToInt(tc));
        }
    }
}

Line Notes

Map<Character, Integer> romanMap = new HashMap<>();Creates a map to store Roman numeral values for O(1) lookup.

for (int i = 0; i < s.length(); i++)Loops through each character in the input string.

int value = romanMap.get(s.charAt(i));Retrieves the integer value of the current Roman numeral.

if (i + 1 < s.length() && value < romanMap.get(s.charAt(i + 1)))Checks if current symbol is less than next to detect subtractive notation.

result -= value;Subtracts current value when a subtractive pair is found.

else {Handles the case when no subtractive pair is detected.

result += value;Adds current value when no subtractive pair is detected.

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int romanToInt(string s) {
    unordered_map<char, int> romanMap = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    int result = 0;
    for (int i = 0; i < s.size(); i++) {
        int value = romanMap[s[i]];
        if (i + 1 < s.size() && value < romanMap[s[i + 1]]) {
            result -= value;
        } else {
            result += value;
        }
    }
    return result;
}

int main() {
    string testCases[] = {"III", "IV", "IX", "LVIII", "MCMXCIV"};
    for (auto &tc : testCases) {
        cout << tc << " -> " << romanToInt(tc) << endl;
    }
    return 0;
}

Line Notes

unordered_map<char, int> romanMap = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};Maps Roman symbols to their integer values for constant-time access.

for (int i = 0; i < s.size(); i++)Iterates through each character index in the input string.

int value = romanMap[s[i]];Fetches the integer value of the current Roman numeral character.

if (i + 1 < s.size() && value < romanMap[s[i + 1]])Detects subtractive pairs by comparing current and next symbol values.

result -= value;Subtracts current value when a subtractive pair is found.

else {Handles the case when no subtractive pair is detected.

result += value;Adds current value when no subtractive pair is detected.

function romanToInt(s) {
    const romanMap = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000};
    let result = 0;
    for (let i = 0; i < s.length; i++) {
        let value = romanMap[s[i]];
        if (i + 1 < s.length && value < romanMap[s[i + 1]]) {
            result -= value;
        } else {
            result += value;
        }
    }
    return result;
}

// Test cases
const testCases = ['III', 'IV', 'IX', 'LVIII', 'MCMXCIV'];
testCases.forEach(tc => console.log(`${tc} -> ${romanToInt(tc)}`));

Line Notes

const romanMap = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000};Defines a lookup table for Roman numeral values.

for (let i = 0; i < s.length; i++)Loops through each character index in the input string.

let value = romanMap[s[i]];Gets the integer value of the current Roman numeral character.

if (i + 1 < s.length && value < romanMap[s[i + 1]])Checks if current symbol is less than next to identify subtractive notation.

result -= value;Subtracts current value when a subtractive pair is detected.

else {Handles the case when no subtractive pair is detected.

result += value;Adds current value when no subtractive pair is detected.

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan the string once, performing constant time operations per character. The map is fixed size.

💡 For n=15 (max length), this means at most 15 operations, which is very efficient.

Interview Verdict: Accepted

This approach is efficient enough for all valid inputs and is commonly accepted in interviews.

🧠

Better (Precompute Subtractive Pairs and Use Greedy Parsing)

💡 This approach improves clarity by explicitly checking for known subtractive pairs first, then adding values for single symbols. It reduces conditional complexity and makes the code easier to reason about.

Intuition

Scan the string left to right, at each step check if the next two characters form a known subtractive pair. If yes, add the pair's value and skip two characters; else add the single symbol's value and move one character.

Algorithm

1. Create a map for single Roman symbols and a map for subtractive pairs.
2. Initialize result to 0 and index i to 0.
3. While i < length of string:
4. Check if substring s[i:i+2] is a subtractive pair; if yes, add its value and increment i by 2.
5. Otherwise, add value of s[i] and increment i by 1.
6. Return the accumulated result.

💡 This approach is easier to debug because it separates subtractive pairs from single symbols explicitly.

</>

Code

def romanToInt(s: str) -> int:
    single_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    pair_map = {'IV': 4, 'IX': 9, 'XL': 40, 'XC': 90, 'CD': 400, 'CM': 900}
    result = 0
    i = 0
    while i < len(s):
        if i + 1 < len(s) and s[i:i+2] in pair_map:
            result += pair_map[s[i:i+2]]
            i += 2
        else:
            result += single_map[s[i]]
            i += 1
    return result

# Driver code
if __name__ == '__main__':
    test_cases = ['III', 'IV', 'IX', 'LVIII', 'MCMXCIV']
    for tc in test_cases:
        print(f'{tc} -> {romanToInt(tc)}')

Line Notes

single_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}Maps single Roman numerals to their integer values.

pair_map = {'IV': 4, 'IX': 9, 'XL': 40, 'XC': 90, 'CD': 400, 'CM': 900}Maps known subtractive pairs to their integer values.

while i < len(s)Iterates through the string using an index to allow skipping characters.

if i + 1 < len(s) and s[i:i+2] in pair_mapChecks if the next two characters form a subtractive pair.

result += pair_map[s[i:i+2]]Adds the value of the subtractive pair to the result.

i += 2Skips two characters after processing a pair.

else:Handles the case when no subtractive pair is found.

result += single_map[s[i]]Adds the value of a single symbol when no pair is found.

i += 1Moves to the next character.

import java.util.*;
public class RomanToInteger {
    public static int romanToInt(String s) {
        Map<String, Integer> pairMap = new HashMap<>();
        pairMap.put("IV", 4);
        pairMap.put("IX", 9);
        pairMap.put("XL", 40);
        pairMap.put("XC", 90);
        pairMap.put("CD", 400);
        pairMap.put("CM", 900);
        Map<Character, Integer> singleMap = new HashMap<>();
        singleMap.put('I', 1);
        singleMap.put('V', 5);
        singleMap.put('X', 10);
        singleMap.put('L', 50);
        singleMap.put('C', 100);
        singleMap.put('D', 500);
        singleMap.put('M', 1000);
        int result = 0;
        int i = 0;
        while (i < s.length()) {
            if (i + 1 < s.length() && pairMap.containsKey(s.substring(i, i + 2))) {
                result += pairMap.get(s.substring(i, i + 2));
                i += 2;
            } else {
                result += singleMap.get(s.charAt(i));
                i++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String[] testCases = {"III", "IV", "IX", "LVIII", "MCMXCIV"};
        for (String tc : testCases) {
            System.out.println(tc + " -> " + romanToInt(tc));
        }
    }
}

Line Notes

Map<String, Integer> pairMap = new HashMap<>();Stores subtractive pairs and their values for quick lookup.

Map<Character, Integer> singleMap = new HashMap<>();Stores single Roman numeral values.

while (i < s.length())Uses a while loop to allow skipping characters when pairs are found.

if (i + 1 < s.length() && pairMap.containsKey(s.substring(i, i + 2)))Checks if the next two characters form a subtractive pair.

result += pairMap.get(s.substring(i, i + 2));Adds the value of the subtractive pair.

i += 2;Skips two characters after processing a pair.

else {Handles the case when no subtractive pair is found.

result += singleMap.get(s.charAt(i));Adds single symbol value.

i++;Moves forward by one character.

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int romanToInt(string s) {
    unordered_map<string, int> pairMap = {{"IV",4},{"IX",9},{"XL",40},{"XC",90},{"CD",400},{"CM",900}};
    unordered_map<char, int> singleMap = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    int result = 0;
    int i = 0;
    while (i < s.size()) {
        if (i + 1 < s.size() && pairMap.count(s.substr(i, 2))) {
            result += pairMap[s.substr(i, 2)];
            i += 2;
        } else {
            result += singleMap[s[i]];
            i++;
        }
    }
    return result;
}

int main() {
    string testCases[] = {"III", "IV", "IX", "LVIII", "MCMXCIV"};
    for (auto &tc : testCases) {
        cout << tc << " -> " << romanToInt(tc) << endl;
    }
    return 0;
}

Line Notes

unordered_map<string, int> pairMap = {{"IV",4},{"IX",9},{"XL",40},{"XC",90},{"CD",400},{"CM",900}};Maps subtractive pairs to their integer values.

unordered_map<char, int> singleMap = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};Maps single Roman numerals to values.

while (i < s.size())Iterates through the string with index i, allowing skipping characters.

if (i + 1 < s.size() && pairMap.count(s.substr(i, 2)))Checks if the next two characters form a subtractive pair.

result += pairMap[s.substr(i, 2)];Adds the value of the subtractive pair.

i += 2;Skips two characters after processing a pair.

else {Handles the case when no subtractive pair is found.

result += singleMap[s[i]];Adds single symbol value.

i++;Moves forward by one character.

function romanToInt(s) {
    const pairMap = {'IV':4, 'IX':9, 'XL':40, 'XC':90, 'CD':400, 'CM':900};
    const singleMap = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000};
    let result = 0;
    let i = 0;
    while (i < s.length) {
        if (i + 1 < s.length && pairMap[s.substring(i, i + 2)]) {
            result += pairMap[s.substring(i, i + 2)];
            i += 2;
        } else {
            result += singleMap[s[i]];
            i++;
        }
    }
    return result;
}

// Test cases
const testCases = ['III', 'IV', 'IX', 'LVIII', 'MCMXCIV'];
testCases.forEach(tc => console.log(`${tc} -> ${romanToInt(tc)}`));

Line Notes

const pairMap = {'IV':4, 'IX':9, 'XL':40, 'XC':90, 'CD':400, 'CM':900};Stores subtractive pairs and their values.

const singleMap = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000};Stores single Roman numeral values.

while (i < s.length)Uses a while loop to allow skipping characters when pairs are found.

if (i + 1 < s.length && pairMap[s.substring(i, i + 2)])Checks if the next two characters form a subtractive pair.

result += pairMap[s.substring(i, i + 2)];Adds the value of the subtractive pair.

i += 2;Skips two characters after processing a pair.

else {Handles the case when no subtractive pair is found.

result += singleMap[s[i]];Adds single symbol value.

i++;Moves forward by one character.

⏱

Complexity

TimeO(n)

SpaceO(1)

Each character is processed once or twice in the worst case, with constant time map lookups.

💡 For n=15, this approach performs at most 15 iterations, making it very efficient.

Interview Verdict: Accepted

This approach is clean and efficient, often preferred for clarity in interviews.

🧠

Optimal (Single Pass with Value Comparison and No Extra Maps)

💡 This approach optimizes space by using a fixed function to get symbol values instead of maps, and uses a single pass with lookahead subtraction logic. It is optimal for interviews requiring minimal memory usage.

Intuition

Iterate through the string, convert each symbol to its value using a function, and if the current value is less than the next, subtract it; otherwise add it. This avoids extra data structures.

Algorithm

1. Define a function to convert a Roman symbol to its integer value.
2. Initialize result to 0.
3. Iterate over the string indices.
4. For each symbol, get its value and the next symbol's value (if any).
5. If current value < next value, subtract current; else add current.
6. Return the accumulated result.

💡 This approach is elegant because it uses no extra memory and a simple function to get values.

</>

Code

def value(c: str) -> int:
    if c == 'I': return 1
    if c == 'V': return 5
    if c == 'X': return 10
    if c == 'L': return 50
    if c == 'C': return 100
    if c == 'D': return 500
    if c == 'M': return 1000
    return 0

def romanToInt(s: str) -> int:
    result = 0
    for i in range(len(s)):
        curr = value(s[i])
        next_val = value(s[i + 1]) if i + 1 < len(s) else 0
        if curr < next_val:
            result -= curr
        else:
            result += curr
    return result

# Driver code
if __name__ == '__main__':
    test_cases = ['III', 'IV', 'IX', 'LVIII', 'MCMXCIV']
    for tc in test_cases:
        print(f'{tc} -> {romanToInt(tc)}')

Line Notes

def value(c: str) -> int:Defines a helper function to convert Roman symbols to integers without extra memory.

if c == 'I': return 1Returns the integer value for symbol 'I'.

for i in range(len(s))Iterates over each character index in the string.

curr = value(s[i])Gets the integer value of the current symbol.

next_val = value(s[i + 1]) if i + 1 < len(s) else 0Gets the next symbol's value or 0 if at the end.

if curr < next_val:Checks if current value is less than next to detect subtractive notation.

result -= currSubtracts current value if next is larger, indicating subtractive notation.

else:Handles the case when no subtraction is needed.

result += currAdds current value otherwise.

public class RomanToInteger {
    public static int value(char c) {
        switch(c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }

    public static int romanToInt(String s) {
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            int curr = value(s.charAt(i));
            int next_val = (i + 1 < s.length()) ? value(s.charAt(i + 1)) : 0;
            if (curr < next_val) {
                result -= curr;
            } else {
                result += curr;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String[] testCases = {"III", "IV", "IX", "LVIII", "MCMXCIV"};
        for (String tc : testCases) {
            System.out.println(tc + " -> " + romanToInt(tc));
        }
    }
}

Line Notes

public static int value(char c)Helper method to convert Roman numeral character to integer without extra data structures.

switch(c)Uses switch-case for efficient symbol to value mapping.

for (int i = 0; i < s.length(); i++)Iterates over each character index in the input string.

int curr = value(s.charAt(i));Gets integer value of current Roman symbol.

int next_val = (i + 1 < s.length()) ? value(s.charAt(i + 1)) : 0;Gets next symbol's value or 0 if at end.

if (curr < next_val) {Checks if current value is less than next to detect subtractive notation.

result -= curr;Subtracts current value if next is larger.

} else {Handles the case when no subtraction is needed.

result += curr;Adds current value otherwise.

#include <iostream>
#include <string>
using namespace std;

int value(char c) {
    switch(c) {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
        default: return 0;
    }
}

int romanToInt(string s) {
    int result = 0;
    for (int i = 0; i < s.size(); i++) {
        int curr = value(s[i]);
        int next_val = (i + 1 < s.size()) ? value(s[i + 1]) : 0;
        if (curr < next_val) {
            result -= curr;
        } else {
            result += curr;
        }
    }
    return result;
}

int main() {
    string testCases[] = {"III", "IV", "IX", "LVIII", "MCMXCIV"};
    for (auto &tc : testCases) {
        cout << tc << " -> " << romanToInt(tc) << endl;
    }
    return 0;
}

Line Notes

int value(char c)Helper function to convert Roman numeral character to integer using switch-case.

switch(c)Maps each Roman symbol to its integer value efficiently.

for (int i = 0; i < s.size(); i++)Iterates through each character index in the input string.

int curr = value(s[i]);Gets integer value of current Roman symbol.

int next_val = (i + 1 < s.size()) ? value(s[i + 1]) : 0;Gets next symbol's value or 0 if at end.

if (curr < next_val) {Checks if current value is less than next to detect subtractive notation.

result -= curr;Subtracts current value if next is larger.

} else {Handles the case when no subtraction is needed.

result += curr;Adds current value otherwise.

function value(c) {
    switch(c) {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
        default: return 0;
    }
}

function romanToInt(s) {
    let result = 0;
    for (let i = 0; i < s.length; i++) {
        let curr = value(s[i]);
        let next_val = (i + 1 < s.length) ? value(s[i + 1]) : 0;
        if (curr < next_val) {
            result -= curr;
        } else {
            result += curr;
        }
    }
    return result;
}

// Test cases
const testCases = ['III', 'IV', 'IX', 'LVIII', 'MCMXCIV'];
testCases.forEach(tc => console.log(`${tc} -> ${romanToInt(tc)}`));

Line Notes

function value(c)Helper function to convert Roman numeral character to integer using switch-case.

switch(c)Maps Roman symbols to their integer values.

for (let i = 0; i < s.length; i++)Iterates over each character index in the input string.

let curr = value(s[i]);Gets integer value of current Roman symbol.

let next_val = (i + 1 < s.length) ? value(s[i + 1]) : 0;Gets next symbol's value or 0 if at end.

if (curr < next_val) {Checks if current value is less than next to detect subtractive notation.

result -= curr;Subtracts current value if next is larger.

} else {Handles the case when no subtraction is needed.

result += curr;Adds current value otherwise.

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the string with constant time operations and no extra data structures.

💡 For n=15, this means 15 iterations and minimal memory usage, ideal for constrained environments.

Interview Verdict: Accepted

This is the most memory-efficient approach and is often preferred in interviews for demonstrating clean, optimal code.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, the first or third approach is best to code: the first for clarity and the third for optimal memory usage.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(1)	No	N/A	Mention to show understanding, but code only if asked
2. Better (Explicit Subtractive Pairs)	O(n)	O(1)	No	N/A	Good for clarity and easy debugging, often coded
3. Optimal (Function + Single Pass)	O(n)	O(1)	No	N/A	Best for demonstrating clean, memory-efficient code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding. Progress to better and optimal solutions, and practice coding and testing each.

How to Present

Step 1: Clarify the input format and constraints.Step 2: Describe the brute force approach with lookahead subtraction logic.Step 3: Discuss improvements by explicitly handling subtractive pairs.Step 4: Present the optimal approach using a helper function and minimal memory.Step 5: Code the chosen approach and test with sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your understanding of Roman numeral rules, ability to handle subtractive notation, code correctness, and optimization skills.

Common Follow-ups

• How would you convert integer to Roman numeral? → Use greedy subtraction with symbol-value pairs.
• What if input is invalid? → Add validation logic checking symbol order and allowed subtractive pairs.

💡 These follow-ups test your ability to extend the problem and handle edge cases beyond the basic conversion.

🔍

Pattern Recognition

When to Use

1) Input is a string encoding numbers with special symbols; 2) Symbols have values and subtractive rules; 3) Need to convert to integer; 4) Lookahead or pair checking is required.

Signature Phrases

Roman numeralsubtractive notationconvert to integer

NOT This Pattern When

Problems involving pure arithmetic without symbol encoding or those requiring DP for optimization.

Similar Problems

Integer to Roman - inverse conversion problemValid Roman Numeral - validation of Roman numeral strings

Practice

1. Given the following Python code, what is the value of result after processing the input "AB"?

easy

A. 28

B. 27

C. 52

D. 26

Solution

1. Step 1: Compute powers array for "AB"

   Length n=2, powers initialized as [1,1]. Loop sets powers[0] = powers[1]*26 = 1*26=26, so powers = [26,1].

2. Step 2: Calculate result by summing value * power

   For 'A': value=1, result += 1*26=26; For 'B': value=2, result += 2*1=2; total result=28.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches manual base-26 calculation: A=1*26 + B=2*1=28 [OK]

Hint: Precompute powers from right to left [OK]

Common Mistakes:

• Off-by-one in powers array
• Using zero-based letter values
• Adding instead of multiplying powers

2. You are given a list of points on a 2D plane. Your task is to find the rectangle with the minimum area such that all four corners are points from the list. Which approach guarantees finding the optimal solution efficiently?

easy

A. Use a hash set to store points and check pairs of points as diagonals to find rectangles.

B. Use dynamic programming to build rectangles from smaller sub-rectangles.

C. Use a greedy approach by sorting points and selecting closest pairs to form rectangles.

D. Use a brute force approach checking all quadruples of points to find rectangles.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding rectangles formed by points with minimum area, which involves checking pairs of points as potential diagonals.

2. Step 2: Evaluate approaches

   Brute force (checking all quadruples) is correct but inefficient (O(n^4)). Greedy and DP approaches do not guarantee correctness or efficiency here. Using a hash set to check existence of complementary points for diagonals is both correct and efficient (O(n^2)).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set + diagonal pairs -> optimal and correct [OK]

Hint: Hash set + diagonal pairs is key [OK]

Common Mistakes:

• Thinking greedy or DP solves this efficiently
• Using brute force without pruning

3. Identify the bug in the following code snippet that calculates the angle between clock hands:

class ClockAngle:
    def __init__(self):
        self.precomputed = [[0]*60 for _ in range(12)]
        for h in range(12):
            for m in range(60):
                hour_angle = h * 30  # Bug here
                minute_angle = m * 6
                diff = abs(hour_angle - minute_angle)
                self.precomputed[h][m] = min(diff, 360 - diff)

    def angleClock(self, hour: int, minutes: int) -> float:
        return self.precomputed[hour % 12][minutes]

medium

A. Line calculating hour_angle ignores minute progress, should be h * 30 + m * 0.5

B. Line calculating minute_angle should use (m % 60) * 6 to handle invalid minutes

C. Line computing diff should use (hour_angle + minute_angle) instead of abs difference

D. Line returning precomputed angle should use hour instead of hour % 12

Solution

1. Step 1: Analyze hour_angle calculation

   Hour hand moves 30 degrees per hour plus 0.5 degrees per minute. Ignoring minutes causes incorrect angles at times like 3:30.

2. Step 2: Verify other lines

   Minute angle calculation is correct, diff uses absolute difference properly, and hour modulo 12 is correct for indexing.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing minute contribution in hour_angle -> wrong angle [OK]

Hint: Hour hand moves continuously with minutes, not just discrete hours [OK]

Common Mistakes:

• Ignoring minute progress in hour hand angle
• Not normalizing hour to 12-hour format

4. What is the time complexity of the optimal happy number detection algorithm that uses a fixed set of known unhappy cycle numbers and repeatedly computes the sum of squares of digits until reaching 1 or a cycle?

medium

A. O(n^2) due to repeated digit extraction and sum computations

B. O(n) where n is the input number

C. O(k * log n) where k is the number of iterations until termination and log n is digits count

D. O(1) constant time because the unhappy cycle set is fixed

Solution

1. Step 1: Identify operations per iteration

   Each iteration computes sum of squares of digits, which takes O(log n) time since number of digits is proportional to log n.

2. Step 2: Count number of iterations

   Number of iterations k until reaching 1 or cycle is variable but bounded; total time is O(k * log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time depends on iterations and digit count, not linear or constant [OK]

Hint: Sum of digit squares costs O(log n) per iteration [OK]

Common Mistakes:

• Assuming linear O(n) time
• Confusing fixed cycle set with constant time
• Mistaking digit extraction cost

5. The following code attempts to determine if a number is happy but contains a subtle bug. Identify the line with the bug.

def isHappy(n: int) -> bool:
    def digit_square_sum(num: int) -> int:
        total = 0
        while num > 0:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total

    while n != 1:
        n = digit_square_sum(n)
    return True

medium

A. Line with 'while n != 1:' loop condition

B. Missing cycle detection causing infinite loop

C. Line with 'return True' after the loop

D. Line with 'n = digit_square_sum(n)' inside the loop

Solution

1. Step 1: Analyze loop termination condition

   The loop only terminates when n == 1, but if n falls into an unhappy cycle, it never reaches 1.

2. Step 2: Identify missing cycle detection

   Without tracking seen numbers or using a known cycle set, the code loops infinitely for unhappy numbers.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Infinite loop occurs due to missing cycle detection [OK]

Hint: No cycle detection -> infinite loop on unhappy numbers [OK]

Common Mistakes:

• Assuming loop condition suffices
• Ignoring cycle detection necessity
• Misreading return placement