Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Array

Roman to Integer

Array, Iterative Approach

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.

  • X can be placed before L (50) and C (100) to make 40 and 90.

  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

  • 1 <= s.length <= 15

  • s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').

  • It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Solutions

The problem is to convert a Roman numeral to an integer. The solution involves a process of iterating over the Roman numeral from left to right. For each character, it adds its corresponding integer value to the result. If a character represents a value that is less than the next character’s value, it subtracts this value instead of adding it. The final result is the integer representation of the original Roman numeral.

Approach - Brute Force Technique

Checks each character in the string one by one.

Steps

  1. Dictionary Initialization: A dictionary romanLatters is initialized with Roman numerals as keys and their corresponding integer values as values.

  2. Input Validation: The IsValidInput function checks if the input string s is within the valid length (1 to 15 characters) and if all characters in s are valid Roman numerals. If the input string is invalid, the function returns false, and the RomanToInt function will return zero.

  3. Roman Numeral Conversion: The RomanToInt function converts the input Roman numeral to an integer. It initializes an integer output to store the result and a variable pre to keep track of the value of the previous Roman numeral.

  4. Iteration Over String: The function iterates over each character in the input string s. For each character, it gets the corresponding integer value current from the romanLatters dictionary.

  5. Addition and Subtraction: If pre is zero or pre is greater than or equal to current, the function adds current to output. Otherwise, it subtracts pre from output and adds current - pre to output.

  6. Update Previous Value: After processing each character, the function updates pre to current.

  7. Completion: The function continues this process until all characters in the string have been processed. At this point, output is the integer equivalent of the input Roman numeral.

  8. Return Result: Finally, the function returns the integer output.

public class Solution {
    
    public Dictionary<char,int> romanLatters=new Dictionary<char,int>()
    {
        {'I',1},
        {'V',5},
        {'X',10},
        {'L',50},
        {'C',100},
        {'D',500},
        {'M',1000}
    };
    public int RomanToInt(string s) {
        
         int output=0;
        if(IsValidInput(s)){
             
           
            int pre=0;
            foreach(char ch in s.ToArray()){
                
                int current=romanLatters[ch];
                if(pre==0 || pre>=current){
                   output+=current;
                }
                else {
                    output = output - pre;
                    output = output + (current-pre);
                }
                 pre=current;
            }
        }
        return output;
    }
    
    private bool IsValidInput(string input){
        
        return 1<=input.Length && input.Length<=15 &&IsValidRomanInput(input);
    }
    
    private bool IsValidRomanInput(string input){
        
        foreach(char item in input.ToArray()){
             
            if(!romanLatters.ContainsKey(item)){
                return false;
            }
        }
        return true;
    }
}

Complexity

  • Time Complexity: O(1)

  • Auxiliary Space: O(1)

Time Complexity: The time complexity is O(1). This is because the max length of string is 15 characters.

Space Complexity: The space complexity is O(1). The space used by the program does not grow with the size of the input string. The dictionary of Roman numerals uses a constant amount of space, and the integer variables output and pre also use a constant amount of space.

Please note that this analysis assumes that dictionary lookups can be done in constant time.

Approach - Iterative Technique

The solution involves a process of iterating over the Roman numeral from left to right. For each character, it checks if it represents a value that is less than the next character’s value. If it is, it subtracts this value from the result. Otherwise, it adds this value to the result. The final result is the integer representation of the original Roman numeral.

Steps

  1. Dictionary Initialization: A dictionary romanLatters is initialized with Roman numerals as keys and their corresponding integer values as values.

  2. Input Validation: The IsValidInput function checks if the input string s is within the valid length (1 to 15 characters) and if all characters in s are valid Roman numerals. If the input string is invalid, the function returns false, and the RomanToInt function will return zero.

  3. Roman Numeral Conversion: The RomanToInt function converts the input Roman numeral to an integer. It initializes an integer output to store the result.

  4. Iteration Over String: The function iterates over each character in the input string s using a for loop. For each character, it gets the corresponding integer value current from the romanLatters dictionary.

  5. Addition and Subtraction: Inside the for loop, it checks if the current character’s value is less than the next character’s value. If it is, it subtracts current from output. Otherwise, it adds current to output.

  6. Completion: The function continues this process until all characters in the string have been processed. At this point, output is the integer equivalent of the input Roman numeral.

  7. Return Result: Finally, the function returns the integer output.

public class Solution {
    public Dictionary<char,int> romanLatters=new Dictionary<char,int>()
    {
        {'I',1},
        {'V',5},
        {'X',10},
        {'L',50},
        {'C',100},
        {'D',500},
        {'M',1000}
    };
    public int RomanToInt(string s) {
        
        int output=0;
        if(IsValidInput(s)){
             
            int pre=0;
            for(int i=0; i<s.Length; i++){
                
                int current=romanLatters[s[i]];
                if(i+1<s.Length && current<romanLatters[s[i+1]]){
                   output-=current;
                }
                else {
                    output+=current;
                }
                 pre=current;
            }
        }
        return output;
    }
    
    private bool IsValidInput(string input){
        
        return 1<=input.Length && input.Length<=15 &&IsValidRomanInput(input);
    }
    
    private bool IsValidRomanInput(string input){
        
        foreach(char item in input.ToArray()){
             
            if(!romanLatters.ContainsKey(item)){
                return false;
            }
        }
        return true;
    }
}

Complexity

  • Time Complexity: O(1)

  • Auxiliary Space: O(1)

Time Complexity: The time complexity is O(1). This is because the max length of string is 15 characters.

Space Complexity: The space complexity is O(1). The space used by the program does not grow with the size of the input string. The dictionary of Roman numerals uses a constant amount of space, and the integer variables output and pre also use a constant amount of space.

Please note that this analysis assumes that dictionary lookups can be done in constant time.

PreviousMissing NumberNextFirst Missing Positive

Last updated 1 year ago