LeetCode (Algorithms#13) ‒ Roman to Integer

Problem

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Solution

Converting Roman to Integer is a little easier to compregend than Integer to Roman, and is more or less the same solution. We can treat consecutive roman characters as contributing to digits in the 1s, 10s, 100s, or 1000s place. We iterate over each character, carefully considering each case in the right order. The code below handles these cases properly.

Notice that the code can be generalized to any number of digits, but we only need to consider up to 3999.

Time complexity: $O(n)$
Space complexity: $O(n)$
Runtime: 79 ms (99.92%)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

public int romanToInt(String s) { char[] cs = s.toCharArray(); int i = 0, val = 0; while (i<cs.length) { switch (cs[i++]) { case 'M': val+=1000; break; case 'D': val+=500; break; case 'C': if (i<cs.length && cs[i]=='D') { val+=400; i++; } else if (i<cs.length && cs[i]=='M') { val+=900; i++; } else val+=100; break; case 'L': val+=50; break; case 'X': if (i<cs.length && cs[i]=='L') { val+=40; i++; } else if (i<cs.length && cs[i]=='C') { val+=90; i++; } else val+=10; break; case 'V': val+=5; break; case 'I': if (i<cs.length && cs[i]=='V') { val+=4; i++; } else if (i<cs.length && cs[i]=='X') { val+=9; i++; } else val+=1; break; } } return val; }

LeetCode (Algorithms#12) ‒ Integer to Roman

Problem

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Solution

The problem is pretty straightforward once you realize all cases of roman numerals. The cases can be split up into $n < 4$, $4 \leq n < 5$, $5 \leq n < 9$, and $n \geq 9$, and are repeated for 10s, 100s, etc. In the code below, we simply iterate over each digit of the integer, and append characters according to the case.

Time complexity: $O(n)$
Space complexity: $O(n)$
Runtime: 97 ms (69.14%)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

public String intToRoman(int num) { StringBuilder sb = new StringBuilder(); int n = num/1000; if (n > 0) appendN(sb,'M',n); num%=1000; if (num>=400 && num<500) sb.append("CD"); else if (num<400) appendN(sb,'C',num/100); else if (num<900) appendN(sb.append("D"),'C',(num-500)/100); else sb.append("CM"); num%=100; if (num>=40 && num<50) sb.append("XL"); else if (num<40) appendN(sb,'X',num/10); else if (num<90) appendN(sb.append("L"),'X',(num-50)/10); else sb.append("XC"); num%=10; if (num==4) sb.append("IV"); else if (num<4) appendN(sb,'I',num); else if (num<9) appendN(sb.append("V"),'I',num-5); else sb.append("IX"); return sb.toString(); } void appendN(StringBuilder sb, char c, int n) { for (int i=0; i<n; i++) sb.append(c); }

LeetCode (Algorithms#11) ‒ Container With Most Water

Problem

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Solution

To clarify the problem, we are searching for the coordinates a_i and a_j for j>i, 0<i,j<n such that the area (j-i)*min(a_i,a_j) is maximized. The bruteforce solution is clearly O(n^2), and the problem cannot benefit from being sorted (since the solution depends on the original ordering). The trick to finding the optimal solution, which runs in O(n), is to recognize that as you reduce the width of the container by one, then either the lower height must increase, or both height must increase by one or more to have a larger area. Thus, starting with a_0 and a_n, yielding the widest container, we can iterate on the side with the shorter height while maintaining the maximum area. If a larger container does exist, the height will have to be larger to make up for the smaller width, and so the side with the smaller height will iterate towards it. Trying a few examples can convince yourself that this is correct.

Time complexity: O(n)
Space complexity: O(n)
Runtime: 10 ms (63.17%)

1 2 3 4 5 6 7 8 9 10 11 12

public int maxArea(int[] height) { int i=0, j=height.length-1, area=0; while (i<j) { area = Math.max(area, (j-i)*Math.min(height[i],height[j])); if (height[i] > height[j]) { j--; } else { i++; } } return area; }

LeetCode (Algorithms#10) ‒ Regular Expression Matching

Problem

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Solution

The problem may seem simple at first, but becomes complicated when considering some cases involving *. For instance isMatch("aaa","a*a"), which requires you to match a* with varying numbers of a to find the right match. This effectively eliminates any linear solution as we cannot simply iterate through the strings once.

The solution that stood out most to me was the recursive one. Recursion allows us to check each case of matching, and then backtrack to the last successful match to try a different branch. The primary cases of matching are to match a single character (s[i]==p[j] or p[j]='.'), or 0+ characters when a ".*" or "a*" is present. These evaluate into the two cases of recursive calls in the code below. Although it is slow as the recursion tree quickly branches out, and so a better solution can come from Dynamic Programming as we will see.

Time complexity: O(2^n)
Space complexity: O(2^n)
Runtime: 59 ms (28.61%)

public boolean isMatch(String s, String p) {
    return helper(s,p,0,0);
}
boolean helper(String s, String p, int i, int j) {
    if (j>=p.length()) return i>=s.length();
    if (j+1<p.length() && p.charAt(j+1)=='*') { // .* or c*
        return helper(s,p,i,j+2) || i<s.length() 
            && ((s.charAt(i)==p.charAt(j) || p.charAt(j)=='.') && helper(s,p,i+1,j));
    } else { // single character match
        return i<s.length() && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.')
            && helper(s,p,i+1,j+1);
    }
}

The Dynamic Programming solution follows the standard formula for DP. We formulate a 2D array and fill in values for where a character i in the string matches a character j in the pattern while considering previously computed cells. The solution then simply lies in the value of the last cell. The code below should make sense upon realizing the cases commented at the top. Note that in line 15, the first row of the array is filled with true for sequences of characters containing '*'. This allows us to match the string with "a*" zero times. Also note the significant improvements in complexity and runtime.

Time complexity: O(n^2)
Space complexity: O(n^2)
Runtime: 27 ms (97.46%)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

public boolean isMatch(String s_, String p_) { /** * DP[i][j] truth cases: * 1) s[i]==p[j] OR p[j]=='.' AND DP[row-1][col-1] * 2) p[j]=='*' * a) s[i]!=p[j], then the character preceeding p[j] is counted 0 times * b) s[i]==p[j] OR p[j]=='.', then we must consider counting it any number * of times. **/ char[] s = s_.toCharArray(), p = p_.toCharArray(); int n=s_.length(), m=p_.length(); boolean[][] DP = new boolean[n+1][m+1]; DP[0][0]=true; for (int col=1; col<=m; col++) DP[0][col] = p[col-1]=='*' && col>1 && DP[0][col-2]; for (int row=1; row<=n; row++) { for (int col=1; col<=m; col++) { if (p[col-1]=='*') { if (isCharMatch(s[row-1],p[col-2])) { DP[row][col] = DP[row-1][col] || DP[row][col-1] || DP[row][col-2]; } else { DP[row][col] = DP[row][col-2]; } } else { DP[row][col] = isCharMatch(s[row-1],p[col-1]) && DP[row-1][col-1]; } } } return DP[n][m]; } public boolean isCharMatch(char c, char pc) { return c==pc || pc=='.'; }

LeetCode (Algorithms#9) ‒ Palindrome Number

Problem

Determine whether an integer is a palindrome. Do this without extra space.

Solution

First, note that the complexity of the problem should be on the order of the number of digits in the integer. Thus, as long as you only use numeric data types (single instances, not arrays), your code will run in O(1) space. The problem is again similar to that of Reverse Integer, but with some optimizations we can make.

There are a few cases that can be determined to produce an early decision for the function, these are in the first few lines of the code below (note the last line, which decides in O(1) whether a two digit number is a palindrome). Other than these conditions, the main optimization is to only reverse half of the number. We do not actually know the length of the number, so we keep checking for equality between the original and reversed portion of the number until the original becomes shorter than the reversed: x / 10 =< xr.

Time complexity: O(n)
Space complexity: O(n)
Runtime percentile: 89.99%

public boolean isPalindrome(int x) {
    if (x < 0 || (x!=0 && x % 10 == 0)) return false;
    else if (x < 10) return true;
    else if (x < 100) return x % 11 == 0;   
    long xr = 0;
    while (x > 0 && x/10 > xr) {
        xr = xr*10 + x%10;
        x /= 10;
        if (x == (int)xr || x/10 == (int)xr) return true;
        else if (xr > Integer.MAX_VALUE) return false;
    }
    return false;
}

LeetCode (Algorithms#8) ‒ String to Integer (atoi)

Problem

Implement atoi to convert a string to an integer.

Note: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Solution

The solution clearly takes O(n) as you iterate through each character of the string. The general case of the algorithm is similar to that of Reverse Integer where the resulting number is shifted before adding each new digit. The tricky part is handling all cases, which is the only reason this code is more than 3 lines long.

Time complexity: O(n)
Space complexity: O(n)
Runtime percentile: 72.65%

public int myAtoi(String str) {
    long res = 0l;
    if (str != null && str.length() > 0) {
        long sign = 1l;
        boolean numFound = false;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (!numFound && c==32) continue;
            if (c<48 || c>57) {
                if ((c==45 || c==43) && !numFound) {
                    sign = (c==45?-1l:1l);
                    numFound = true;
                } else break;
            } else {
                numFound = true;
                res = res*10 + sign*((int)c-48);
                if (res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
                else if (res < Integer.MIN_VALUE) return Integer.MIN_VALUE;
            }
        }
    }
    return (int)res;
}

LeetCode (Algorithms#7) ‒ Reverse Integer

Problem

Reverse digits of an integer.

The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

Examples:

x = 123, return 321
x = -123, return -321

Solution

The solution is pretty straightforward. We want to iterate through the numbers and add each one to a new number after shifting it to the correct position, while checking if the addition would cause an overflow. With the number assumed to be an int, this can be done in a hackish way by using a long, and comparing to the max int values. This problem is a good example of one that can be optimized after a naive implementation.

I personally started this problem by directly translating the approach into code. How do you know how far to shift each number over? Compute the length of the number first, iterate through it, isolate each digit, then shift and add it.

public int reverse(int x) {
    int n = 0, res = 0;
    for (int _x=x; _x!=0; _x/=10) n++; // count digits
    long k;
    for (int i=1; i<=n; i++) {
        k = x % (int)Math.pow(10,i) / (int)Math.pow(10,i-1); // isolate ith digit
        long q = k*(long)Math.pow(10,n-i); // shift digit over
        if (q+(long)res<Integer.MIN_VALUE || q+(long)res>Integer.MAX_VALUE) return 0; 
        res += (int)q;
    }
    return res;
}

Naturally, we'd first want to try and combine this into a single loop. This can be done by shifting the whole reversed number each iteration, instead of fully shifting each number in each iteration (which requires n):

public int reverse(int x) {
    long k, _x=x, res = 0;
    for (int i=1; _x!=0; i++) {
        k = x % (int)Math.pow(10,i) / (int)Math.pow(10,i-1);
        res *= 10;
        res += k;
        _x /= 10;
        if (res<Integer.MIN_VALUE || res>Integer.MAX_VALUE) return 0; 
    }
    return (int)res;
}

The problem with this code is that the calls to Math.pow() do not run in constant time, and so the algorithm does no run in the O(n) time complexity that is expect. These can be eliminated by noticing that while shifting the original digits right (to determine when there are no more digits), we can take the first digit (by modding it with 10), and add it to the reversed number, which is being shifted left at the same time. This produces the more concise code below.

Time complexity: O(n)
Space complexity: O(n)
Runtime percentile: 72.56%

public int reverse(int x) {
    long _x=x, res = 0;
    while (_x!=0) {
        res = res*10 + _x%10;
        _x /= 10;
        if (res<Integer.MIN_VALUE || res>Integer.MAX_VALUE) return 0; 
    }
    return (int)res;
}

(Another less elegant solution is to simply convert it to a string, reverse the string, and convert it back to an int)