Programming with Passion

Sunday, July 9, 2017

LeetCode (Algorithms#16) ‒ 3Sum Closest

Problem

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Solution

This problem is identical to 3Sum. The difference being, instead of returning all sums, we return the (first) closest sum to the target. This simplification results in maintaining a solution with minimum distance to the target, mind in the code below, instead of checking for equivalence with the target and storing in a list.

Time complexity: $O(n^2)$
Space complexity: $O(1)$
Runtime: 18 ms (96.18%)

public int threeSumClosest(int[] nums, int target) {
    if (nums==null || nums.length < 3) return 0;
    Arrays.sort(nums);
    // System.out.println(Arrays.toString(nums));
    int l, r, v, len=nums.length, res=0, mind=Integer.MAX_VALUE;
    for (int i=0; i<len-1; i++) {
        if (i>0 && nums[i-1]==nums[i]) continue;
        l = i+1; r = len-1;
        while (l < r) {
            v = nums[i]+nums[l]+nums[r];
            if (Math.abs(v-target)<mind) {
                mind = Math.abs(v-target);
                res = v;
            }
            if (v < target) l++;
            else if (v > target) r--;
            else return v;
        }
    }
    return res;
}

Sunday, June 4, 2017

LeetCode (Algorithms#15) ‒ 3Sum

Problem

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Example:

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution

The problem is a direct extension of2Sum, which runs in $O(n)$. With 3Sum, it should be reasonable to assume that a $O(n^2)$ solution is possible. The trick is in handling repeated combinations of the same three numbers, which I initially tried using a hashset of solutions, with a sum of each number's hash to hash to a solution. This worked, but was too slow for one of the tests.

The better approach is to first sort the array, and then while considering each of the $n$ numbers, use a left and right pointer, and while moving them inward, solve the 2Sums problem with a target of $-n$. To iterate the left and right pointers, we chose to increase the left pointer if the sum is less than 0, and decrease the right pointer if the sum is greater than the 0. Since the array is sorted, increasing or decreasing either pointer will change the sum to the next lowest or highest value, respectively, ensuring that no solution is skipped. We can simultaneously skip over any numbers on both the left and right side that are repeats to ensure only a new solution is considered. The code below implements this approach.

Time complexity: $O(n^2)$
Space complexity: $O(n^2)$
Runtime: 82 ms (77.86%)

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> sums = new ArrayList<List<Integer>>();
    if (nums==null || nums.length < 3) return sums;
    Arrays.sort(nums);
    int l, r, v, len = nums.length;
    List<Integer> L;
    for (int i=0; i<len-1; i++) {
        if (i>0 && nums[i-1]==nums[i]) continue;
        l = i+1; r = len-1;
        while (l < r) {
            v = nums[i]+nums[l]+nums[r];
            if (v < 0) l++;
            else if (v > 0) r--;
            else { // sum == 0
                L = new ArrayList<Integer>(3);
                L.add(nums[i]); L.add(nums[l]); L.add(nums[r]);
                sums.add(L);
                v=nums[l++]; while (l<r && nums[l]==v) l++;
                v=nums[r--]; while (r>l && nums[r]==v) r--;
            }
        }
    }
    return sums;
}

LeetCode (Algorithms#14) ‒ Longest Common Prefix

Problem

Write a function to find the longest common prefix string amongst an array of strings.

Solution

For a set of $n$ strings, the brute force solution is sufficient as you must compare a character in each string to determine if it belongs to a common prefix. Thus, the optimal solution is $O(n^2)$, where the worst case is all strings match.

Time complexity: $O(n^2)$
Space complexity: $O(n^2)$
Runtime: 12ms (52.13%)

public String longestCommonPrefix(String[] strs) {
    if (strs.length==0 || strs[0].length()==0) return "";
    else if (strs.length==1) return strs[0];

    StringBuilder sb = new StringBuilder();
    int j = 0;
    char prefChar;
    boolean isPrefChar;
    while (j<strs[0].length()) {
        prefChar = strs[0].charAt(j);
        isPrefChar = true;
        for (int i=1; i<strs.length; i++)
            isPrefChar &= j<strs[i].length() && strs[i].charAt(j)==prefChar;
        if (isPrefChar) sb.append(prefChar);
        else break;
        j++;
    }
    return sb.toString();
}

Sunday, May 28, 2017

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%)

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%)

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);
}

Friday, May 26, 2017

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%)

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;
}

Sunday, May 21, 2017

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%)

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=='.';
}

Home

Development

LeetCode

Sunday, July 9, 2017

LeetCode (Algorithms#16) ‒ 3Sum Closest

Problem

Example:

Solution

Sunday, June 4, 2017

LeetCode (Algorithms#15) ‒ 3Sum

Problem

Example:

Solution

LeetCode (Algorithms#14) ‒ Longest Common Prefix

Problem

Solution

Sunday, May 28, 2017

LeetCode (Algorithms#13) ‒ Roman to Integer

Problem

Solution

LeetCode (Algorithms#12) ‒ Integer to Roman

Problem

Solution

Friday, May 26, 2017

LeetCode (Algorithms#11) ‒ Container With Most Water

Problem

Solution

Sunday, May 21, 2017

LeetCode (Algorithms#10) ‒ Regular Expression Matching

Problem

Solution