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%)
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%)
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%)
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%)
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%)
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%)
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%)
publicbooleanisMatch(String s, String p){returnhelper(s,p,0,0);}booleanhelper(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*returnhelper(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 matchreturn 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%)
publicbooleanisMatch(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 =newboolean[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];}publicbooleanisCharMatch(char c,char pc){return c==pc || pc=='.';}
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%
publicbooleanisPalindrome(int x){if(x <0||(x!=0&& x %10==0))returnfalse;elseif(x <10)returntrue;elseif(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)returntrue;elseif(xr > Integer.MAX_VALUE)returnfalse;}returnfalse;}
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%
publicintmyAtoi(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;}elsebreak;}else{
numFound =true;
res = res*10+ sign*((int)c-48);if(res > Integer.MAX_VALUE)return Integer.MAX_VALUE;elseif(res < Integer.MIN_VALUE)return Integer.MIN_VALUE;}}}return(int)res;}
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.
publicintreverse(int x){int n =0, res =0;for(int _x=x; _x!=0; _x/=10) n++;// count digitslong k;for(int i=1; i<=n; i++){
k = x %(int)Math.pow(10,i)/(int)Math.pow(10,i-1);// isolate ith digitlong q = k*(long)Math.pow(10,n-i);// shift digit overif(q+(long)res<Integer.MIN_VALUE|| q+(long)res>Integer.MAX_VALUE)return0;
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):
publicintreverse(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)return0;}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%
publicintreverse(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)return0;}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)
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
Examples:
convert("PAYPALISHIRING",3) should return "PAHNAPLSIIGYIR"
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();}
