Programming with Passion Algorithms, Mobile Development, Robotics

## Sunday, July 9, 2017

### 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%)
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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; i0 && 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) target) r--; else return v; } } return res; } 

## Sunday, June 4, 2017

### 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%)
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public List> threeSum(int[] nums) { List> sums = new ArrayList>(); if (nums==null || nums.length < 3) return sums; Arrays.sort(nums); int l, r, v, len = nums.length; List L; for (int i=0; i0 && 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(3); L.add(nums[i]); L.add(nums[l]); L.add(nums[r]); sums.add(L); v=nums[l++]; while (ll && nums[r]==v) r--; } } } return sums; } 

### 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%)
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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

## Sunday, May 28, 2017

### 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

### 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

## Friday, May 26, 2017

### 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 height[j]) { j--; } else { i++; } } return area; } 

## Sunday, May 21, 2017

### Problem

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

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

## Thursday, May 4, 2017

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


## Tuesday, May 2, 2017

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


## Monday, May 1, 2017

### 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.

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

## Sunday, April 30, 2017

### Problem

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:

P   A   H   N
A P L S I I G
Y   I   R


### Solution

The problem is essentially of remapping indices to the known pattern. Given the number rows n in the zigzag, it is easy to find that the number of characters in a single zigzag is 2n-2. Additionally, there is a one to one correspondence between the indices in each ordering, so with information of the zigzag size, there should be no problem traversing through and reassigning each character's indices in O(n).

Time complexity: O(n)
Space complexity: O(n)
Percentile: 98.12%

public String convert(String s, int nRows) {
if (s==null || s.length()==0) return "";
if (nRows < 2) return s;

int N = s.length();
int n = 2*nRows-2;

int idx = 0;
StringBuilder sb = new StringBuilder();

for (int i=0; i<nRows; i++) {
for (int j=i; j<N; j+=n) {
sb.append(s.charAt(j));
if (i>0 && i<nRows-1 && j+n-2*i<N)
sb.append(s.charAt(j+n-2*i));
}
}

return sb.toString();
}
`