1-Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].



Brute Force

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public int[] twoSum(int[] nums, int target) {
	for (int i=0; i<nums.size; i++){
		for (int j=i+1;j<nums.length;j++){
			if (nums[j]==target-nums[i]){
				return new int[] {i,j};
			}
		}
	}
	throw new IllegalArgumentException("No two sum solution");
} 

Complexity Analysis

1
2
* Time complexity:   O(n^2)       we have a nested loop 
* Space complexity:  O(1) 	  we do not allocate any additional memory

One Pass Hash Table

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public int[] twoSum(int[] nums, int target) {
	Map<Integer, Integer> map = new HashMap<>();
	for(int i=0; i<nums.length; i++){
		int complement=target-nums[i];
		if (map.containsKey(complement)){
			return new int[] {map.get(complement),i};
		}
		map.put(nums[i],i);
	}
	throw new IllegalArgumentException("No two sum solution"); 
}

Complexity Analysis

1
2
* Time complexity:   O(n)		each lookup in the hash table only requires O(1) time
* Space complexity:  O(n)		we require additional space for the hash table which stores at most n





2-Add Two Numbers

Given two non-empty linked lists representing two non-negative integers with the digits stored in reverse order and each node containing a single digit, add the two numbers and return as a linked list

Example:

1
2
3
4
Input (2 -> 4 -> 3) + (5 -> 6 -> 4) 
Output 7 -> 0 -> 8 

342 + 465 = 807



Elementary Math Solution

 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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */



class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead= new ListNode(0); 
        ListNode p=l1, q=l2, curr=dummyHead; 
        int carry=0; 
        while (p!=null||q!=null){
            int x= (p!=null) ? p.val :0; //if (p!=null) then x contains p.val
            int y= (q!=null) ? q.val :0;
            int sum=carry+x+y;
            carry=sum/10;
            curr.next=new ListNode(sum%10);
            curr=curr.next; 
            if (p!=null) p=p.next; 
            if (q!=null) q=q.next; 
        }
        if (carry>0){
            curr.next= new ListNode(carry);
        }
        return dummyHead.next; 
    }
}

Complexity analysis

1
2
* Time Complexity:  O(max(m,n))         depends on the lengths of the two linked lists 
* Space Complexity: O(max(m,n))		the maximum length of the new list is max(m,n)+1





3-Substring No Repeat

Longest Substring Without Repeating Characters

Given a string find the length of the longest substring without repeating characters.

1
2
3
4
Example
Input: 		"abcabcbb"
Output:		3
Explanation:	The answer is "abc", with the length of 3
1
2
3
4
Example 2
Input:		"bbbbb"
Output:		1
Explanation:	The answer is "b", with the length of 1
1
2
3
4
5
Example 3
Input:		"pwwkew"
Output:		3
Explanation: 	The answer is "wke", with the length of 3. Note that the answer must be a substring
		"pwke" is a subsequence and not a substring 



Brute Force

Algorithm

Suppose we have a function “boolean allUnique(String substring)” which returns true if all the characters in the substring are unique and false otherwise. We can iterate through all the possible substrings of the given string s and call the function allUnique. If it turns out to be true, then we update our answer of the maximum length of substring without duplicate characters.

To enumerate all substrings of a given string we enumerate the start and end indices of them. Suppose the start and end indices are i and j respectively. Then we have 0 <= i <= j <= n. Thus using two nested loops with i from 0 to n-1 and j from i+1 to n, we can enumerate all the substrings of s

To check if one string has duplicate characters we can use a set. We iterate through all the characters in the string and put them into the set one by one. Before putting one character, we check if the set already contains it. If so we return false and after the loop we return true.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}

Complexity Analysis

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
* Time Complexity:   O(n^3)		Verifying if characters in   [i,j) are unique requires us to scan all of
					them which would cost O(j-i) time. 

					For a given i, the sum of time costed by each j -> [i+1,n] is 
					"Summation from i+1 to n O(j-1)"

					Thus, the sum of all the time consumption is: 
					O(summation from 0 to n-1(summation from j=i+1 to n (j-1))) 
					O(summation from i=0 to n-1(1+n-i)(n-i)/2)) = O(n^3)


					*Note that the sum of all numbers up to n 1+2+3+...+n = n(n+1)/2


* Space Complexity:  O(min(n,m))	We require O(k) space for checking a substring has no duplicate 
					characters, where k is the size of the set. The size of the Set is 
					upper bounded by the size of the string n amd the size of the charset
					or alphabet m 
				
				



Sliding Window

A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in the array/string which usually defined by the start and end indices

1
Ex. [i,j) left-closed, right-open

A sliding window is a window that slides its two boundaries in a certain direction, for example if we slide [i,j) to the right by 1 element, then it becomes [i+1, j+1) - left closed, right open.

Sliding Window approach, whenever we are looking at a section on an array usual to perform calculations we don’t need to completely recalculate everything for every section of the array. Usually we can use the value obtained from another section of the array to determine something about this section of the array. For example if we are calculating the sum of sections of an array we can use the previously calculated value of a section to determine the sum of an adjacent section in the array.

1
Ex. 1 2 3 4 5 6 7 8 

If we calculate the first section of four values we get 1+2+3+4 = 10 , then to calculate the next section 2+3+4+5 we can just take our first section (window_sum) and perform the operation:

1
window_sum-first entry + last entry = 10-1+5= 14

So essentially for the window sliding technique we use what we know about an existing window to determine properties for another window.



Algorithm

In the brute force approach, we repeatedly check a substring to see if it has duplicate characters but this is unnecessary. If a substring from index i to j-1 is already checked to have no duplicate characters we only need to check if s[j] is already in the substring.

To check if a character is already in the substring we can scan the substring which leads to an O(n^2) algorithm but we can improve on this runtime using a HashSet as a sliding window to check if a character exists in the current set O(1).

We use a HashSet to store the characters in the current window [i,j) and then we slide the index j to the right, if it is not in the HashSet, we slide j further until s[j] is already in the HashSet. At this point we found the maximum size of substrings without duplicate characters starting with index i. If we do this for all i, then we obtain our answer.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

Complexity Analysis

1
2
3
4
5
6
Time complexity:	O(2n)=O(n)	Worst case each character will be visited twice by i and j

Space complexity: 	O(min(m,n))	Same as the brute force method, we need O(k) space for the 
					sliding window where k is the size of the set. The size of the
					set is bounded by the size of the string n and the size of the
					charset/alphabet m



Sliding Window Optimized

The previously discussed sliding window approach requires at most 2n steps and this could in fact be optimized even further to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character

If s[j] has a duplicate in the range [i , j) with index j’, we don’t need to increase i little be little we can just skip all the elements in the range [i , j’] and let i be j’+1 directly

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}





4-Median of Two Sorted Arrays

There are two sorted arrays num1 and num2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty.

1
2
3
4
5
6
Example 

nums1 = [1, 3] 
nums2 = [2]

The median is 2.0
1
2
3
4
5
6
Example 2

nums1= [1, 2] 
nums2= [3, 4] 

The median is (2+3)/2 = 2.5



Recursive Approach

In statistics the median is used for dividing a set into two equal length subsets with one set being always greater than the other set. To approach this problem first we cut A into two parts at a random position i:

1
2
3
         left_A                |           right_A 

  A[0], A[1], ... , A[i-1]         A[i], A[i+1], ... , A[m-1]

Since A has m elements, there are m+1 kinds of cutting as i can range from 0-m. We can also see that left_A is empty when i is zero and right_A is empty when i=m

1
len(left_A) = i and len(right_A)= m-i

We can similarly cut B into two parts at a random position j:

1
2
3
	left_B			|	right_B

  B[0], B[1], ... , B[j-1]	   B[j], B[j+1], ... , B[n-1]

Now if we put left_A and left_B into one set and put right_A and right_B into another set and name them left_part and right_part, then we get

1
2
3
	left_part		|	right_part
  A[0], A[1], ... , A[i-1]	  A[i], A[i+1], ... , A[m-1]
  B[0], B[1], ... , B[j-1]	  B[j], B[j+1], ... , B[n-1]

If we can ensure that

  1. the len(left_part) = len(right_part)
  2. max(left_part) <= min(right_part)

then we divide all the elements in {A,B} into two parts with equal length and one part is always greater than the other. Then

1
median= (max(left_part)+min(right_part))/2

To ensure these two conditions, we need to ensure:

  1. i+j= m-i+n-j (or: m-i+n-j+1) if n>m, we just need to set i=0~m, j= (m+n+1)/2 - i
  2. B[j-1]<=A[i] and A[i-1]<=B[j]

So, all we need to do is search for i in [0,m] to find an object i such that B[j-1]<=A[i] and A[i-1]<=B[j] where j=(m+n+1)/2 -i

Then we perform a binary search following the steps described below:

  1. Set imin=0, imax=0, then start searching in [imin, imax]
  2. Set i=(imin+imax)/2 , j=(m+n+1)/2 - i
  3. Now we have len(left_part) = len(right_part) and there are only 3 more situations which we may encounter:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
   - B[j-1] <= A[i] and A[i-1]<=B[j] 
     This means that we have found the object i, so we can stop searching

   - B[j-1] > A[i]
     Means A[i] is too small, we must adjust i to get B[j-1]<=A[i] so we increase i because this will
     cuase j to be decreased. We cannot decrease i because when i is decreased, j will be increased
     so B[j-1] is increased and A[i] is decreased (B[j-1]<= A[i] will never be satisfied)

   - A[i-1] > B[j] 
     Means A[i-1] is too big and thus we must decrease i to get A[i-1]<=B[j]. In order to do that we 
     must adjust the searching range to [imin, i-1] so we set imax=i-1 and go back to step 2

When the object i is found, then the media is:

max(A[i-1],B[j-1]), when m+n is odd (max(A[i-1],B[j-1])+min(A[i],B[j]))/2, when m+n is even

Next is to consider the edge values i=0, i=m, j=0, j=n where A[i-1], B[j-1], A[i], B[j] may not exist

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
	public double findMedianSortedArrays(int[] A, int[] B) {
		int m=A.length;
		int n=B.length;
		if (m>n) {   	//ensuring that m<=n
			int[] temp=A; A=B; B=temp;
			int tmp=m; m=n; n=tmp;
		}
		int iMin=0, iMax=m, halfLen=(m+n+1)/2;
		while (iMin<=iMax) {
			int i=(iMin+iMax)/2
			int j= halfLen - i;
			if (i<iMax && B[j-1] > A[i]){
				iMin=i+1; //i is too small
			}
			else if (i>iMin && A[i-1]>B[j]) {
				iMax=i-1; //i is too big
			}
			else{ //we have found the object i 
				int maxLeft=0; 
				if (i==0) {
					maxLeft=B[j-1];
				}
				else if (j==0){
					maxLeft=A[i-1];
				}
				else{
					maxLeft=Math.max(A[i-1], B[j-1]);
				}

				if ((m+n)%2 ==1) {
					return maxLeft;
				}

				int minRIght=0;
				if (i==m) {
					minRight=B[j];
				}
				else if (j==n) {
					minRight=A[i];
				}
				else {
					minRight=Math.min(B[j], A[i]);
				}

				return (maxLeft+minRight)/2.0;
			}
		}
		return 0.0;
	}
}

Complexity Analysis

1
2
3
4
5
6
7
8
Time Complexity: O(log(min(m,n)))	At first the searching range is [0,m] and the length of this 
					searching range will be reduced by half after each loop so we
					only need log(m) loops. Since we do constant operations in 
					each loop the time complexity is O(log(m) and since m<=n the
					time complexity is O(log(min(m,n))

Space Complexity: O(1)			We only need constant memory to store 9 local variables so the
					space complexity is O(1)





5-Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

1
2
3
4
5
6
Example 1: 

Input: "babad" 
Output: "bab" 

Note: "aba" is also a valid answer 
1
2
3
4
Example 2: 

Input: "cbbd"
Output: "bb" 



Longest Common Substring

Some people will be tempted to come up with this quick solution which is unforunately flawed, “reverse S and become S’. Find the longest common substring between S and S’ and that will be the longest palindromic substring.” This will work with some examples but there are some cases where the longest common substring is not a valid palindrome.

Ex. S="abacdfgdcaba", S'="abacdgfdcaba" 	

The longest common substring between S and S’ is “abacd” and clearly this is not a valid palindrome

We can solve this problem however by checking if the substring’s indices are the same as the reversed substring’s original indices each time we find a longest common substring. If it is, then we attempt to update the longest palindrome found so far, if not we skip this and find the next candidate

Complexity Analysis

1
2
Time Complexity: O(n^2) 
Space Complexity: O(n^2) 



Brute Force

The obvious brute force solution is to pick all possible starting and ending position for a substring and verify if it is a palindrome

Complexity Analysis

1
2
3
4
5
Time Complexity: O(n^3)		If n is the length of the input string, there are a total of 
				(n 2) = n(n-1)/2 substrings and since verifying each substring takes 
				O(n) time, the run time complexity is O(n^3)

Space Complexity: O(1) 



Dynamic Programming

We can improve on the brute force solution by avoid some unnecessary re-computation while validating palidromes. Consider the word “ababa”, if we already know that “bab” is a palindrome then we can determine that ababa is a palindrome by noticing that the two left and right letters connected to bab are the same.

This yields a straight forward dynamic programming solution where we initialize the one and two letters palindromes and then work our way up finding all three letters palindromes and so on.

Complexity Analysis

1
2
3
Time Complexity: 	O(n^2)	

Space Complexity: 	O(n^2)	Using O(n^2) space to store the table 



Expand Around Center

This approach allows us to solve this problem in O(n^2) time using only constant space complexity. We observe that a palindrome mirrors around its enter and therefore a palindrome can be expanded from its center and there are only 2n-1 such centers (for palindromes with an even number of letters like “abba” its center is in between two letters).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String longestPalindrome(String s) {
	if (s==null || s.length() < 1) return "";     //edge case 
	int start=0, end=0;
	for (int i=0; i<s.length(); i++) {
		int len1=expandAroundCenter(s,i,i);
		int len2=expandAroundCenter(s,i,i+1);
		int len=Math.max(len1,len2);
		if (len>end-start) {
			start= i-(len-1)/2;
			end=i+len/2
		}
	}
	return s.substring(start,end+1);
}

private int expandAroundCenter(String s, int left, int right) {
	int L=left, R=right;
	while(L>=0 && R<s.length() && s.charAt(L)==s.charAt(R)) {
		L--;
		R++;
	}
	return R-L-1;
}



Manacher’s Algorithm

There is an O(n) algorithm called Manacher’s algorithm, however, it is a non-trivial algorithm and no one would expect you to come up with this algorithm in a 45 minute coding session





6-ZigZag Conversion

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

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”. Write a code that will take a string and make this conversion given a number of rows:

1
string convert(string s, int numRows);
1
2
3
4
Example 1: 

Input: s="PAYPALISHIRING", numRows=3
Output: "PAHNAPLSIIGYIR"
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Example 2:

Input: s="PAYPALISHIRING", numRows=4
Output: "PINALSIGYAHRPI"

Explanation:

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



Sort by Row

By iterating through the string from left to right we can easily determine which row in the Zig-Zag pattern that a character belongs to



Algorithm

We can use min(numRows,len(s)) lists to represent the non-empty rows of the Zig-Zag Pattern. Iterate through s from left to right appending each character to the appropriate row. The appropriate row can be tracked using two variables: the current row and the current direction.

The current direction only changes when we moved to the topmost row or moved down to the bottommost row

 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
class Solution {
	public String convert(String s, int numRows) {
		if (numRows==1) return s;		//if there is only one row return string

		List<StringBuilder> rows=new ArrayList<>();
		for (int i=0; i<Math.min(numRows, s.length()); i++){
			rows.add(new StringBuilder());
		}
		int curRow=0;
		boolean goingDown=false;

		for(char c: s.toCharArray()) {
			rows.get(curRow).append(c);
			if (curRow==0 || curRow==numRows-1) {
				goingDown=!goingDown;
			}
			curRow+=goingDown ? 1 : -1;
		}	

		StringBuilder ret= new StringBuilder();
		for(StringBuilder row:rows) {
			ret.append(row);
		}
		return ret.toString();
	}
}

Complexity Analysis

1
2
Time Complexity:  O(n)	where n==len(s)
Space Complexity: O(n)



Visit by Row

Visit the characters in the same order as reading the Zig-Zag pattern line by line



Algorithm

Visit all characters in row 0 first, then row 1, then row 2, and so on. For all whole numbers k, * characters in row 0 are located at indexes k*(2*numRows-2) * characters in row numRows -1 are located at indexes k*(2*numRows-2)+ numRows -1 * characters in inner row i are located at indexes k*(2*numRows-2)+i and (k+1)(2*numRows-2)-i

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
	public String convert(String s, int numRows) {
		if (numRows==1) return s; 

		StringBuilder ret=new StringBuilder();
		int n=s.length();
		int cycleLen= 2* numRows -2;

		for (int i=0; i<numRows; i++) {
			for (int j=0; j+1<n; j+= cycleLen) {
				ret.append(s.charAt(j+i));
				if (i!=0 && i!=numROws-1 && j+cycleLen-i<n) {
					ret.append(s.charAt(j+cycleLen-i));
				}
			}
			return ret.toString();
		}
	}
}

Complexity Analysis

1
2
3
4
Time Complexity: O(n)	where n==len(s) Each index is visited once

Space Complexity: O(n) 	C++ implementation can achieve O(1) if the return string is not considered 
			extra space





7-Reverse Integer

Given a 32- bit signed integer, reverse digits of an integer.

1
2
3
4
Example 1: 

Input: 123
Output: 321
1
2
3
4
Example 2: 

Input: -123
Output: -321
1
2
3
4
Example 3: 

Input: 120 
Output: 21

For the purpose of this problem assume that your function returns 0 when the reversed integer overflows



Pop and Push Digits and Check Before Overflow

We can build up the reverse integer one digit at and time and before doing so we can check whether or not appedning another digit would cause overflow



Algorithm

Reversing an integer can be done similarly to reversing a string. We want to repeatedly “pop” the last digit off of x and push it to the back of the rev so that in the end rev is the reverse of x.

To push and pop digits without the help of some auxiliar stack/array we can use math

1
2
3
4
5
6
7
//pop operation: 
pop = x%10; 
x/=10;

//push operation:
temp=rev*10+pop;
rev =temp;

This statement is dangerous however as the statement temp=rev*10+pop may cause an overflow and luckily it is easy to check beforehand whether or not this statement would cause an overflow.

  1. If temp=rev*10+pop causes an overflow, then rev>=INTMAX/10
  2. If rev> INTMAX/10, then temp=rev*10+pop is guaranteed to overflow
  3. if rev==INTMAX/10, then temp=rev*10 + pop will overflow if an only if pop>7
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
	public int reverse(int x) {
		int rev=0; 
		while (x!=0) {
			int pop=x%10;
			x/=10;
			if (rev>Integer.MAX_VALUE/10||(rev==Integer.MAX_VALUE/10 && pop>7)) return 0;
			if (rev<Integer.MIN_VALUE/10||(rev==Integer.MIN_VALUE/10 && pop<-8)) return 0;
			rev=rev*10 +pop;
		}
		return rev;
	}
}

Complexity Analysis

1
2
Time Complexity:  O(log(x))	There are roughly log10(x) digits in x 
Space Complexity: O(1)





8-String to Integer (atoi)

Implement atoi which converts a string to an integer

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exits because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed a zero value is returned

Note:

  • only the space character ’ ’ is considered as whitespace character
  • assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [-2^31, 2^31-1]. If the numerical value is out of the range of representable values, INT_MAX (2^31-1) or INT_MIN (-2^31) is returned
1
2
3
4
	Example 1: 

	Input: "42"
	Output: 42
1
2
3
4
	Example 2: 

	Input: "      -42" 
	Output: -42
1
2
3
4
	Example 3:

	Input: "4193 with words "
	Output: 4193
1
2
3
4
	Example 4: 
	
	Input: "words and 987"
	Output: 0
1
2
3
4
	Example 5:
	
	Input: "-91283472332"
	Output: -2147483648 	//out of the range of a 32-bit signed integer so INT_MIN is returned



ASCII Conversion

Recognize that ASCII characters are actually numbers and 0-9 digits are numbers starting from decimal 48 (0x30 hexadecimal)

1
2
3
4
	'0' is 48
	'1' is 49
	...
	'9' is 57

So to get the value of any character digit you can just remove the ‘0’

1
2
	'1' - '0' => 1
	49  -  48 => 1
 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
public int myAtoi(String str) {
	int index=0, sign=1, total=0;
	
	//1. Empty string 
	if (str.length() ==0) return 0;

	//2. Remove Spaces 
	while(str.charAt(index)==' ' && index < str.length())
		index++;
	
	//3. Handle signs 
	if (str.charAt(index)=='+' || str.charAt(index)=='-'){
		sign= str.charAt(index) == '+' ? 1:-1;
		index++;
	}

	//4. COnvert number and avoid overflow
	while(index<str.length()){
		int digit= str.charAt(index) - '0'; 
		if (digit<0||digit>9) break;

		//check if total will overflow after 10 times and add digit
		if (Integer.MAX_VALUE/10 < total || Integer.MAX_VALUE/10 == total 
		    && Integer.MAX_VALUE%10<digit) {    
		    return sign==1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
		}
		total= 10* total+digit;
		index++;
	}
	return total*sign;
}





9-Palindrome Number

Determines whether an interger is a palindrome. An integer is a palindrome when it reads the same backward as forward.

1
2
3
4
Example 1: 

Input: 121
Output: true
1
2
3
4
5
6
Example 2: 

Input: -121
Output: false 
Explanation: 	From left to right, it reads -121, meanwhile from right to left it becomes 121- . 
		Therefore it is not a palindrome
1
2
3
4
5
Example 3: 

Input: 10 
Output: false 
Explanation: 	Reads 01 from right to left. Therefore it is not a palindrome



Revert Half of the Number

A first idea which may come to mind is to convert the number into a string and check if the string is a palindrome but this would require extra non-constant space for creating the string not allowed by the problem description

Second idea would be reverting the number itself and comparing the number with the original number, if they are the same then the number is a palindrome, however if the reversed number is larger than int.MAX we will hit integer overflow problem.

To avoid the overflow issue of the reverted number, what if we only revert half of the int number? The reverse of the last half of the palindrome should be the same as the first half of the number if the number is a palindrome.

If the input is 1221, if we can revert the last part of the number “1221” from “21” to “12” and compare it with the first half of the number “12”, since 12 is the same as 12, we know that the number is a palindrome.



Algorithm

At the very beginning we can deal with some edge cases. All negative numbers are not palindrome and numbers ending in zero can only be a palindrome if the first digit is also 0 (only 0 satisfies this property)

Now let’s think about how to revert the last half of the number. For the number 1221 if we do 1221%10 we get the last digit 1. To get the second last digit we divide the number by 10 1221/10=122 and then we can get the last digit again by doing a modulus by 10, 122%10=2. If we multiply the last digit by 10 and add the second last digit 1*10+2=12 which gives us the reverted number we want. COntinuing this process would give us the reverted number with more digits.

Next is how do we know that we’ve reached the half of the number? Since we divided the number by 10 and multiplied the reversed number by 10 when the original number is less than the reversed number, it means we’ve gone through half of the number digits.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isPalindrome(int x) {
        if (x<0 || (x%10==0 && x!=0)) {
            return false;
        }
        
        int revertedNumber=0;
        while (x>revertedNumber){
            revertedNumber=x%10+revertedNumber*10;
            x/=10;
        }
        //when the length is an odd number, we can get rid of the middle digit by 
        //revertedNumber/10
        
        //For example when the input is 12321, at the end of the while loop we get x=12, 
        //revertedNumber=123, since the middle digit doesn't matter in a palindrome we can
        //simply get rid of it 
        
        return x==revertedNumber||x==revertedNumber/10;
    }
}





10-Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’

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

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

Note:

  • s could be empty and contains only lower case letters a-z
  • p could be empty and contains only lower case letters a-z and characters like . or *
1
2
3
4
5
6
7
Example 1: 

Input:
	s="aa" 
	p="a" 
	Output: false 
	Explanation: 	"a" does not match the entire string "aa" 
1
2
3
4
5
6
7
8
Example 2: 

Input: 
	s="aa"
	p="a*" 
	Output: true 
	Explanation: 	'*' means zero of more of the preceding element, 'a'. Therefore, by repeating
			'a' once it becomes "aa"
1
2
3
4
5
6
7
Example 3: 

Input: 
	s="ab" 
	p=".*" 
	Output: true 
	Explanation: 	'.*' means "zero or more (*) of any character (.)"
1
2
3
4
5
6
7
8
Example 4: 

Input: 
	s="aab" 
	p="c*a*b" 
	Output: true
	Explanation: 	c can be repeated 0 times, a can be repeated 1 time. Therefore it matches 
			"aab" 
1
2
3
4
5
6
Example 5: 

Input: 
	s="mississippi" 
	p="mis*is*p*."
	Output: false 



Recursion

If there were no Kleene stars (the * wildcard characters for regular expressions), the problem would be easier- we simply check from left to right if each character of the text matches the pattern. When a star is present we may need to check for may different suffixes of the text and see if they match the rest of the pattern. A recursive solution is a straightforward way to represent this relationship

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
	public boolean isMatch(String text, String pattern) {
		if (pattern.isEmpty()) return text.isEmpty(); 
		
		boolean first_match=(!text.isEmpty() && 
				    (pattern.charAt(0)==text.charAt(0) || pattern.charAt(0)=='.'));

		if (pattern.length()>=2 && pattern.charAt(1) =='*'){
			return (isMatch(text,pattern.substring(2))||
			       (first_match && isMatch(text.substring(1),pattern)));
		
		//note: pattern.substring(2) returns all of the characters after index 2 of pattern
		}
		else {
			return first_match && isMatch(text.substring(1), pattern.substring(1));
		}
		
	}
}

Complexity Analysis

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Time Complexity: 	Let T, P be the lengths of the text and the pattern respectively. In the worst
			case, a call to match(text[i:],pattern[2j:]) will be made (i+j i) times, and 
			strings of the order O(T-i) and O(P-2*j) will be made. Thus the complexity has
			the order: 

			summation from i=0 to T * summation from j=0 to P/2 * (i+j i) O(T+P-i-2j).

			We can show that this is bounded by O((T+P)2^(T+P/2))

Space Complexity:	For every call to match, we will create those strings as described above 
			possibly creating duplicates. If memory is not freed, this will also take a
			total of O((T+P)2^(T+P/2)) space even though there are only order O(T^2+P^2) 
			unique suffixes of P and T that are actually required 



Dynamic Programming

As the problem has an optimal substructure, it is natural to cache intermediate results. We ask the question dp(i,j): does text[i:] and pattern[j:] match? We can describe our answer in terms of answers to questions involving smaller strings



Algorithm

We proceed with the same recursion as in Approach 1, except because calls will only ever be made to match(text[i:], pattern[j:]), we use dp(i,j) to handle those calls instead, saving us expensive string-building operations and allowing us to cache the intermediate results

Java Top-Down Variation

 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
36
enum Result {
	TRUE, FALSE
	
}

class Solution {
	Result[][] memo; 

	public boolean isMatch(String text, String pattern) { 
		memo=new Result[text.length() +1][pattern.length() +1];
		return dp(0,0,text,pattern);
	}

	public boolean dp(int i, int j, String text, String pattern) {
		if (memo[i][j]!=null) {
			return memo[i][j]==Result.TRUE;
		}
		boolean ans; 
		if (j==pattern.length()){
			ans=i==text.length();
		}
		else {
			boolean first_match=(i<text.length() && (pattern.charAt(j) == text.charAt(i) ||
					     patter.charAt(j) == '.'));

			if (j+1<pattern.length() && pattern.charAt(j+1)=='*'){
				ans=(dp(i,j+1,text,pattern)||first_match&& dp(i+1,j,text,pattern));
			}
			else {
				ans=first_match && dp(i+1, j+1, text, pattern); 
			}
		}
		memo[i][j]=ans? Result.TRUE: Result.FALSE; 
		return ans; 
	}
}

Complexity Analysis

1
2
3
4
5
Time Complexity: 	Let T, P be the lengths of the text and the pattern respectively. The work 
			for every call to dp(i,j) for i=0,...,T; j=0,...,P is done once and it is O(1) 				work. Hence the time complexity is O(TP)

Space Complexity:	The only memory we use is the O(TP) boolean entries in our cache. Hence, the 
			space complexity is O(TP) 



Non-Recursive

The recursive programming solutions are pretty confusing so this implementation uses 2D arrays and Dynamic Programming

The logic works as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
1. If p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1]; 
2. If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1]; 
3. If p.charAt(j) == '*': 
	
	Subconditions
	1. If p.charAt(j-1)!= s.charAt(i):dp[i][j]=dp[i][j-2]  	//in this case a* only counts as empty
	2. If p.charAt(i-1)== s.charAt(i) or p.charAt(i-1) == '.': 
		
		dp[i][j] = dp[i-1][j]	//in this case a* counts as multiple a 
	     or dp[i][j] = dp[i][j-1]	//in this case a* counts as single a 
	     or dp[i][j] = dp[i][j-2]	//in this case a* counts as empty 
 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
public boolean isMatch(String s, String p) {
	if (s==null || p==null){
		return false;
	}
	boolean[][] dp=new boolean[s.length()+1][p.length()+1];
	dp[0][0]=true; 
	for (int i=0;i<p.length(); i++){
		if (p.charAt(i)=='*' && dp[0][i-1]){
			dp[0][i+1]=true; 
		}
	}
	for (int i=0;i<s.length();i++){
		for (int j=0;j<p.length();j++){
			if (p.charAt(j)=='.'){
				dp[i+1][j+1]=dp[i][j];
			}
			if (p.charAt(j)==s.charAt(i)){
				dp[i+1][j+1]=dp[i][j];
			}
			if (p.charAt(j)=='*'){
				if (p.charAt(j-1)!=s.charAt(i) && p.charAt(j-1) !='.'){
					dp[i+1][j+1]=dp[i+1][j-1];
				}
				else{
					dp[i+1][j+1]=(dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
				}
			}
		}
	}
	return dp[s.length()][p.length()];
}





11-Container with the Most Water

Given n non negative integers a1,a2, … , an where each represents a point at coordinate (i, ai). 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 forns a container such that the container contains the most water.

1
2
3
4
5

		      ^		    ^
	 These two values form the container which could hold water at a max height of 7, these values
	 are also 7 array indexes apart from each other so it could hold water at a max width of 7. The
	 area of water which could be held is thus 7 x 7 = 49

Brute Force

In this case we simply consider the area for every possible pair of the lines and find out the maximum area out of those.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public class Solution {
	public int maxArea(int[] height) {
		int maxarea=0; 
		for (int i=0; i<height.length; i++){
			for (int j=i+1;j<height.length;j++){
				maxarea=Math.max(maxarea, Math.min(height[i],height[j])*(j-i));
			}
		}
		return maxarea;
	}
}

Complexity Analysis

1
2
Time complexity: 	O(n^2) 	Calculating the area for all n(n-1)/2 height pairs 
Space complexity: 	O(1) 	Constant extra space is used 



Two Pointer Approach

The intuition behind this approach is that the area formed between the lines will always be limited by the height of the shorter line. Further, the farther the lines, the more will be the area obtained.

We take two pointers, one at the beginning and one at the end of the array constituting the length of the lines. Further, we maintain a variable maxarea to store the maximum area obtained till now. At every step, we find out the area formed between them, update maxarea and move the pointer pointing to the shorter line towards the other end by one step.

Initially we consider the area constituting the exterior most lines. Now to maximize the area we need to consider the area between the lines of larger lengths. If we try to move the pointer at the longer line inwards, we won’t gain any increase in area, since it is limited by the shorter line. But moving the shorter line’s pointer could turn out to be benefical, as per the same argument, despite the reduction in width. This is done since a relatively longer line obtained by moving the shorter line’s pointer might overcome the reduction in area caused by the width reduction.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class Solution {
	public int maxArea(int[] height) {
		int maxarea=0, l=0, r=height.length-1; 
		while (l<r){
			maxarea=Math.max(maxarea,Math.min(height[l],height[r])*(r-l));
			if (height[l]<height[r]){
				l++;
			}
			else{
				r--;
			}
		}
		return maxarea; 
	}
}

Complexity Analysis

1
2
Time complexity: 	O(n) 	Single pass
Space complexity: 	O(1) 	Constant space is used 





12-Integer To Roman

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

1
2
3
4
5
6
7
8
Symbol		Value 
I		1
V		5
X		10
L		50
C		100
D		500
M		1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as XII which is simply X + II. The number twenty seven 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 an integer, convert it to a roman numeral, input is guaranteed to be within the range from 1 to 3999

1
2
3
4
Example 1: 

Input: 3 
Output: "III" 
1
2
3
4
Example 2: 

Input: 4
Output: "IV" 
1
2
3
4
Example 3: 

Input: 9 
Output: "IX" 
1
2
3
4
5
Example 4: 

Input: 58 
Output: "LVIII" 
Explanation: L=50, V=5, III=3
1
2
3
4
5
Example 5: 

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

String Array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public static String intToRoman(int num) { 
	
	String M[]={"", "M", "MM", "MMM"};
	//represents 1000, 2000, and 3000 since we know the number is in the range 1 to 3999
	
	String C[]={"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
	//represents 0, 100,  200,   300,  400, 500,  600,   700,    800,  900

	String X[]={"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
	//represents 0,  10,   20,    30,   40,  50,   60,    70,     80,   90

	String I[]={"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}; 
	//represents 0,   1,    2,     3,    4,  5,    6,     7,      8,    9

	return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10]; 
} 





13-Roman to Integer

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

1
2
3
4
5
6
7
8
Symbol 		Value 
I		1
V		5
X		10 
L		50
C		100
D		500
M		1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as XII which is simply X + II. The number twenty seven 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 an integer, convert it to a roman numeral, Input is guaranteed to be within the range from 1 to 3999

1
2
3
4
Example 1: 
	
Input: "III" 
Output: 3 
1
2
3
4
Example 2: 

Input: "IV" 
Output: 4
1
2
3
4
Example 3: 

Input: "IX" 
Output: 9 
1
2
3
4
5
Example 4: 

Input: "LVIII" 
Output: 58 
Explanation: L=50, V=5, III=3
1
2
3
4
5
Example 5: 

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



Character Array

 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
class Solution {
	public int romanToInt(String s) {
		Map<Character, Integer> map = new HashMap(); 
		map.put('I', 1); 
		map.put('V', 5); 
		map.put('X', 10); 
		map.put('L', 50); 
		map.put('C', 100); 
		map.put('D', 500); 
		map.put('M', 1000); 

		char[] sc= s.toCharArray(); 
		int total= map.get(sc[0]); 
		int pre=map.get(sc[0]); 
		for (int i=1; i<sc.length; i++) {
			int curr=map.get(sc[i]); 
			if (curr<=pre) {
				total= total + curr; 
			}
			else {
				total=total+curr -2*pre; 
			}
			pre=curr; 
		}
		return total; 
	}

}





14-Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string ""

1
2
3
4
Example 1: 

Input: ["flower", "flow", "flight"]
Output: "fl"
1
2
3
4
5
6
Example 2: 

Input: ["dog", "racecar", "car"] 
Output: ""

Explanation: There is no common prefix among the input strings 

Note: All given inputs are in lowercase letters a-z



Horizontal Scanning


*Intuition:*

For a start we will describe a simple way of find the longest prefix shared by a set of strings LCP(S1 … Sn).We will use the observation that:

1
LCP(S1 ... Sn) = LCP(LCP(LCP(S1, S2), S3), ... Sn) 



Algorithm:

To employ this idea, the algorithm iterates through the strings [S1 … Sn]. finding at each iteration i the longest common prefix of strings LCP(S1 … Si). When LCP(S1 … Si) is an empty string, the algorithm ends. Otherwise after n iterations, the algorithm returns LCP(S1 … Sn)

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

Example: 

{leets, leetcode, leet, leeds}
   \       /      
  LCP{1,2} = leets
  	     leetcode
	     leet 

	 	\	{leets, leetcode, leet, leeds}
		 \ 			   /

		 LCP{1,3} = leet
		 	    leet
			    leet

			      \          {leets, leetcode, leet, leeds}
			       \ 				  /
			       LCP{1,4}   leet
			       		  leeds
					  lee

				LCP{1,4} = "lee"
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public String longestCommon Prefix(String[] strs){
	if (strs.length==0){
		return ""; 
	}
	String prefix=strs[0]; 
	for (int i=1; i<strs.length; i++) {
		while (strs[i].indexOf(prefix) != 0) {
			prefix=prefix.substring(0, prefix.length() -1);
			if (prefix.isEmpty()) {
				return "";
			}
		}
		return prefix; 
	}
}

Complexity Analysis

1
2
3
4
5
6
Time complexity: 	O(S)	Where S is the sum of all characters in all strings. In the worse case
				all n strings are the same. The algorithm compares the string S1 with 
				the other strings [S2 ... Sn]. There are S character comparisons where
				S is the sum of all characters in the input array 

Space complexity: 	O(1) 	We only used constant extra space 



Vertical Scanning

Imagine a very short string is at the end of the array. The above approach will still do S comparisons. One way to optimize this case is to do vertical scanning. We compare characters from top to bottom on the same column (same character index of the strings) before moving on to the next column.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public String longestCommonPrefix(String[] strs) {
	if (strs==null || strs.length==) return ""; 
	for (int i=0; i<strs[0].length(); i++){
		char c=strs[0].charAt(i); 
		for (int j=1; j<strs.length; j++) {
			if (i==strs[j].length() || strs[j].charAt(i)!=c){
				return strs[0].substring(0,i);
			}
		}
	}
	return strs[0]; 
}

Complexity Analysis

1
2
3
4
5
6
7
Time complexity: 	O(S) 	Where S is the sum of all characters in all strings. In the worst case
				there will be n equal strings with length m and the algorithm performs
				S=n*m character comparisons. Even the worst case is still the same as 
				Approach 1, in the best case there are at most n*minLen comparisons 
				where minLen is the length of the shortest string in the array. 

Space complexity: 	O(1)	We only used constant extra space



Divide and Conquer

The idea of the algorithm comes from the associative property of LCP operation. We notice that: LCP(S1 … Sn) = LCP(LCP(S1 … Sk), LCP(Sk+1 … Sn)), where LCP(S1 … Sn) is the longest common prefix in a set of strings [S1 … Sn], 1<k<n



Algorithm

To apply the previous observation, we use the divide and conquer technique, where we split the LCP(Si … Sj) problem into two subproblems LCP(Si … Smid) and LCP(Smid+1 … Sj), where mid is (i+j)/2. We use their solutions lcpLeft and lcpRight to construct the solution of the main problem LCP(Si … Sj). To accomplish this we compare one by one the characters of lcpLeft and lcpRight till there is no character match. The found common prefix of lcpLeft and lcpRight is the solution of the LCP(Si … Sj)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
				{leetcode, leet, lee, le} 

				    /                \   
Divide 			{leetcode, leet}            {lee, le} 

Conquer				|			 | 

			     {leet} 		        {le} 

			         \                      /

				 	   {le} 

	Searching for the longest common prefix (LCP) in dataset {leetcode, leet, lee, le} 
 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
public String longestCommonPrefix(String[] strs) { 

	if (strs == null || strs.length ==0) return "";
		return longestCommonPrefix(strs, 0, strs.length-1); 

}

private String longestCommonPrefix(String[] strs, int l, int r) { 
	if (l==r) {
		return strs[l];
	}
	else {
		int mid=(l+r)/2; 
		String lcpLeft= longestCommonPrefix(strs,l, mid); 
		String lcpRight= longestCommonPrefix(strs,mid+1;r); 
		return commonPrefix(lcpLeft,lcpRight);
	}
}

String commonPrefix(String left, String right) {
	int min=Math.min(left.length(), right.length()); 
	for (int i=0; i<min; i++) {
		if (left.charAt(i) !=right.charAt(i) ){
			return left.substring(0, i);
		}
	}
	return left.substring(0, min);
}

Complexity Analysis

In the worst case we have n equal strings with length m

1
2
3
4
5
6
7
8
Time Complexity: O(S)		where S is the number of all characters in the array, S=m*n so time
				complexity is 2*T(n/2)+O(m). Therefore time complexity is O(S). In the
				best case the algorithm performs O(minLen * n) comparisons, where
				minLen is the shortest string of the array 

Space Complexity: O(m*log(n))	There is a memory overhead since we sotre recursive call in the 
				execution stack. There are log(n) recursive calls, each store needs m
				space to store the result so space complexity is O(m*log(n))



The idea is to apply binary search method to find the string with maximum value L, which is common prefix of all the strings. The algorithm searches the space in the interval (0 … minLen), where minLen is minimum string length and the maximum possible common prefix. Each time search space is divided in two equal parts, one of them is discarded because it is sure that it doesn’t contain the solution. There are two possible cases:

  • S[1…mid] is not a common string. This means that for each j>i, S[1…j] is not a common string and we discard the second half of the search space
  • S [1…mid] is common string. This means that for each i<j, S[1…i] is a common string and we discard the first half of the search space, because we try to find longer common prefix
 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
 				{leets, leetcode, leetc, leeds} 

						|
					      
					     "leets"
					    /        \
					 "lee"      "ts"

					     midpoint 
				
				"lee" in "leetcode" : yes
				"lee" in "leetc" : yes
				"lee" in "leeds" : yes

						|

					     "leets"
					     /     \
					  "lee"    "ts"
					    |      /   \

					  "lee"   "t"   "s"
					        
						   midpoint


						   "leet" in "leetcode" : yes
						   "leet" in "leetc" : yes 
						   "leet" in "leeds" : no

						   LCP= "lee" 
 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
public String longestCommonPrefix(String[] strs) {
	if (strs==null || strs.length==0)
		return "";
	int minLen=Integer.MAX_VALUE; 
	for (String str: strs)
		minLen=Math.min(minLen, str.length());
	int low=1; 
	int high=min Len; 
	while (low<=high) {
		int middle=(low+high)/2;
		if (isCommonPrefix(strs, middle)
			low=middle+1;
		else 
			high=middle-1;
	}
	return strs[0].substring(0, (low + high)/2);
} 

private boolean isCommonPrefix(String[] strs, int len) {
	String str1=strs[0].substring(0,len);
	for (int i=1; i<strs.length; i++)
		if (!strs[i].startsWith(str1))
			return false;
	return true;
}

**Complexity Analysis

In the worst case we have n equal strings with length m

1
2
3
4
5
	Time complexity: 	O(S * log(n)), where S is the sum of all characters in all strings. The
				algorithm makes log(n) iterations, for each of them there are S=m*n 
				comparisons, which gives in total O(S * log(n)) time complexity

	Space complexity: 	O(1). We only used constant extra space 



Further Thoughts

Considering a slightly different problem:

1
2
	Given a set of keys S= [S1, S2 ... Sn], find the longest common prefix among a string q and S.
	This LCP query will be called frequently

We coule optimize LCP queries by storing the set of keys S in a Trie. See this for Trie implementation. In a Trie, each node descending from the root represents a common prefix of some keys. But we need to find the longest common prefix of a string q and all key strings. This means that we have to find the deepest path from the root, which satisfies the following conditions

  • it is a prefix of query string q
  • each node along the path must contain only one child element. Otherwise the found path will not be a common prefix among all strings
  • the path doesn’t comprise of nodes which are marked as end of key. Otherwise the path couldn’t be a prefix of a key which is shorter than itself



Algorithm

The only question left is how to find the deepest path in the Trie, that fulfills the requirements above. The most effective way is to build a trie from {S1 … Sn] strings. Then find the prefix of query string q in the Trie. We traverse the Trie from the root, till it is impossible to continue the path in the Trie because one of the conditions above is not satisfied.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
Searching for the longest common prefix of string "le" in a Trie from dataset {lead, leet}

			Root

			 1

	l   ===========>  \  l

			     2

	e   ===============>   \ e

LCP "le" FOUND	=============>   3   

			     a	/  \ e    End of Key "lee" 
				     
			      6      4

			 d  /	       \ t
				        
END OF KEY "lead"	  7		 5   End of key "leet"
 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public String longestCommonPrefix(String q, String[] strs) {
    if (strs == null || strs.length == 0)
         return "";  
    if (strs.length == 1)
         return strs[0];
    Trie trie = new Trie();      
    for (int i = 1; i < strs.length ; i++) {
        trie.insert(strs[i]);
    }
    return trie.searchLongestPrefix(q);
}

class TrieNode {

    // R links to node children
    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

    // number of children non null links
    private int size;    
    public void put(char ch, TrieNode node) {
        links[ch -'a'] = node;
        size++;
    }

    public int getLinks() {
        return size;
    }
    //assume methods containsKey, isEnd, get, put are implemented as it is described
   //in  )
}

public class Trie {

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

//assume methods insert, search, searchPrefix are implemented
    private String searchLongestPrefix(String word) {
        TrieNode node = root;
        StringBuilder prefix = new StringBuilder();
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter) && (node.getLinks() == 1) && (!node.isEnd())) {
                prefix.append(curLetter);
                node = node.get(curLetter);
            }
            else
                return prefix.toString();

         }
         return prefix.toString();
    }
}

Complexity Analysis

1
2
3
4
5
6
7
In the worst case query q has length m and is equal to all n strings of the array 

Time Complexity:   O(S)   where S is the number of all characters in the array, LCP query O(m) 
  			  Trie build has O(S) time complexity. To find the common prefix of q 
			  in the Trie takes in the worst O(m). 

Space complexity:  O(S)   we only used additional S extra space for the Trie. 





15-3Sum

Given an array “nums” of n integers, are there elements a, b, c in nums 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

1
2
3
4
5
6
7
8
9
Example: 

Given array nums = [-1, 0, 1, 2, -1, -4]. 

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



Sorted Array

The method is to sort an input array and then run through all indices of a possible first element of a triplet. For each element we make another 2Sum sweep of the remaining part of the array. Also we want to skip elements to avoid duplicates in the answer without expending extra memory.

 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
public List<List<Integer>> threeSum(int[] num) {
    
    //Arrays.sort re-arranges the array of integers in ascending order
    //ex. [1, 2, 3, 4]

    Arrays.sort(num);
    List<List<Integer>> res = new LinkedList<>(); 
    for (int i = 0; i < num.length-2; i++) {
        if (i == 0 || (i > 0 && num[i] != num[i-1])) {
            
	    //This lets us skip some of the duplicate entries in the array
	    
	    int lo = i+1, hi = num.length-1, sum = 0 - num[i];

	    //This is for the 2 Sum sweep 

            while (lo < hi) {
                if (num[lo] + num[hi] == sum) {
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
                    while (lo < hi && num[lo] == num[lo+1]) lo++;
                    while (lo < hi && num[hi] == num[hi-1]) hi--;

		    //This lets us skip some of the duplicate entries in the array

                    lo++; hi--;
                } else if (num[lo] + num[hi] < sum) lo++;
                else hi--;

		//This allows us to optimize slightly since we know that the array is sorted
           }
        }
    }
    return res;
}

Complexity Analysis

1
2
3
4
5
6
Time Complexity:  O(n^2)   We go through a maximum of n elements for the first element of a triplet, 
			   and then when making a bi-directional 2Sum sweep of the remaining part of 
			   the array we also go through a maxiumum of n elements. 

Space Complexity: O(1)	   If we assume the return linked list is not extra space, then we do not 
			   allocate any significant extra space





16-3Sum Closest

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

1
2
3
4
5
Example:

Given array nums=[-1, 2, 1, -4], and target=1.

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



3 Pointers

Similar to the previous 3Sum problem, we use three pointers to point to the current element, next element and the last element. If the sum is less than the target, it means that we need to add a larger element so next element move to the next. If the sum is greater, it means we have to add a smaller element so last element move to the second last element. Keep doing this until the end. Each time compare the difference between sum and target, if it is less than minimum difference so far, then replace result with it, otherwise continue iterating.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
		public int threeSumClosest(int[] num, int target) {
		int result=num[0] + num[1] + num[num.length-1];
		Arrays.sort(num);
		for (int i=0; i<num.length -2; i++) {
			int start= i+1, end = num.length -1;
			while (start < end) {
				int sum = num[i] + num[start] + num[end];
				if (sum > target) {
					end--;
				} else {
					start++;
				}
				if (Math.abs(sum-target) < Math.abs(result-target)) {
					result=sum;
				}
			}
		}
		return result;
	}
}





17-Letter Combinations of a Phone Number

Given a string contianing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

1
2
3
2 - abc 	3 - def 	4 - ghi		5 - jkl		6 - mno		7 - pqrs 	8 - tuv
				
						9 - wxyz
1
2
3
4
5
6
Example: 


Input: "23" 

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 

Note: The above answer is in lexicographical order but the answer can be in any order



Backtracking

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to not be a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, ie backtracks and then tries again.

Here is a backtrack function backtrack(combination, next_digits) which takes as arguments an ongoing letter combination and the next digits to check.

  • If there are no more digits to check that means the current combination is done
  • If there are still digits to check:
    • Iterate over the letters mapping to the next available digit
    • Append the current letter to the current combination and proceed to check next digits:
1
2
3
	  combination = combination + letter

	  backtrack(combination + letter, next_digits[1:]).

Visual Representation

Visual Representation

Complexity Analysis

1
2
3
4
5
6
7

Time Complexity: 	O(3^N * 4^M) 	where N is the number of digits in the input that maps to 3
					letters (eg. 2, 3, 4, 5, 6, 8) and M is the number of digits 
					in the input that maps to 4 letters (eg. 7, 9) and N+M is the 
					total number digits in the input 

Space Complexity: 	O(3^N * 4^M)	since one has to keep 3^N * 4^M solutions 



First In First Out (FIFO) Queue

This solution utilizes the Single Queue Breadth First Search (BFS) which is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores all of the neighbor nodes.

 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
public List<String> letterCombinations(String digits) {
	
	LinkedList<String> ans = new LinkedList<String>();
	if (digits.isEmpty()) return ans; 
	String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", {wxyz"};
	ans.add(""); 
	for (int i = 0; i<digits.length(); i++) {
		int x = Character.getNumericValue(digits.charAt(i)); 
		
		//we terminate the while loop when we encounter a new-formed string which is more than
		//the current level i 
		
		//peek retrieves the first value of the linked list
		while (ans.peek().length==i){
			
			//removes the head or the first value in the linkedlist
			String t = ans.remove(); 
			for (char s : mapping[x].toCharArray()) {
				ans.add(t+s);
				//this works because add appends to the end of the list
			}
		}
		return ans; 
	}
}

Complexity Analysis

1
2
3
4
5
6
7

Time Complexity: 	O(3^N * 4^M) 	where N is the number of digits in the input that maps to 3
					letters (eg. 2, 3, 4, 5, 6, 8) and M is the number of digits 
					in the input that maps to 4 letters (eg. 7, 9) and N+M is the 
					total number digits in the input 

Space Complexity: 	O(3^N * 4^M)	since one has to keep 3^N * 4^M solutions 





18-4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target

Note: The solution set must not contain duplicate quadruplets

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


Given array nums = [1, 0, -1, 0, -2, 2], and target = 0


A solution set is: 

[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]



Sorted Array

The idea is the same as the other numbered sum problems like 2sum and 3sum. We sort the array and then proceed to interate through the values until we end up with a result that we are looking for.

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public class Solution {
	public List<List<Integer>> fourSum(int[] num, int target) {
		
		ArrayList<List<Integer>> ans = new ArrayList<>();
		
		if (num.length<4) {
			
			return ans;
		}
		Arrays.sort(num); 
		
		for (int i=0; i<num.length-3; i++) {   //picking the first candidate must leave room
						       //for the other values 
			
			if (num[i]+num[i+1]+num[i+2]+num[i+3]>target) {
				
				break;
				//first candidate too large, search finished
			}

			if (num[i]+num[num.length-1]+num[num.length-2]+num[num.length-3]<target) {
				
				continue;
				//first candidate too small 
			}

			if(i>0 && num[i]==num[i-1]) {
				
				continue;
				//prevents duplicate in ans list
			}
			
			for (int j=i+1; j<num.length-2; j++) {   //picking the second candidate must
								 //leave room for other values 
				
				if (num[i]+num[j]+num[j+1]+num[j+2]>target) {
					
					break;
					//second candidate too large
				}

				if (num[i]+num[j]+num[num.length-1]+num[num.length-2]<target) {
				
					continue;
					//second candidate too small
				}

				if(j>i+1 && num[j]==num[j-1]) {
					
					continue;
					//prevents duplicate results in ans list
				}

				int low=j+1, high=num.length-1;
				
				//two pointer search
				while(low<high) {
					
					int sum=num[i]+num[j]+num[low]+num[high];
					if (sum==target) {
						
						ans.add(Arrays.asList(num[i],num[j],num[low],num[high]));
						while(low<high&&num[low]==num[low+1]) {
							low++; //skipping over duplicates
						}

						while(low<high && num[high]==num[high-1] {
							high--; //skipping over duplicates 
						}
						low++;
						high--;
					}

					//moving window
					else if (sum<target) {
						low++;
					}

					else {
						high--;
					}
				}
			}
		}
		return ans;
	}
}





19-Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of the list and return its head

1
2
3
4
5
6
7
8
Example: 

Given linked list: 1 -> 2 -> 3 -> 4 -> 5, and n=2 


After removing the second node from the end, the linked list becomes 
		   
		   1 -> 2 -> 3 -> 5

Note: Given n will always be valid

Follow up: Could you do this in one pass?



Two Pass Algorithm

Intuition

We notice that the problem could be simply reduced to another one: Remove the (L-n+1)th node from the beginning of the list, where L is the list length. This problem is easy to solve once we found the list length L.



Algorithm

First we will add an auxiliary “dummy” node, which points to the list head. The “dummy” node is used to simplify some corner cases such as a list with only one node or removing the head of the list. On the first pass, find the list length L. Then we set a pointer to the dummy node and start to move it through the list till it comes to the (L-n)th node. We relink next pointer of the (L-n)th node to the (L-n+2)th node and we are done.

1
2
3
4
5
6
	D -> 1 -> 2 -> 3 -> 4 -> NULL

		    |
		    v

	D -> 1 -> 2 -> 4 -> NULL
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode removeNthFromEnd(ListNode head, int n) {
	
	ListNode dummy = new ListNode(0); 
	dummy.next = head; 
	int length =0; 
	ListNode first = head; 
	
	while (first!=null) {
		
		length++;
		first=first.next;
	}

	length -= n; 
	first = dummy;
	while (length>0) {
		
		length--;
		first=first.next;
	}
	first.next=first.next.next;
	return dummy.next; 
}

Complexity Analysis

1
2
3
4
5
Time Complexity: 	O(L) 	The algorithm makes two traversals of the list, first to calculate the 
				list length L and second to find the (L-n)th node. There are 2L-n 
				operations and time complexity is O(L)

Space Complexity: 	O(1) 	We only used constant extra space



One Pass Algorithm

The previous algorithm could be optimized to one pass. Instead of one pointer, we could use two pointers. The first pointer advances the list by n+1 steps from the beginning, while the second pointer starts from the beginning of the list. Now, both pointers are separated by exactly n nodes. We maintain this constant gap by advancing both pointers together until the first pointer arrives past the last node. The second pointer will be pointing at the nth node counting from the last. We relink the next pointer of the node referenced by the second pointer to point to the node’s next next node.

 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
36
37
38
39
40
41
42
43
44
Maintaining N=2 nodes apart between the first and second pointer 

	D	-> 1 -> 2 -> 3 -> 4 -> 5 -> NULL

       first 	 Head 
       second 

			   


Move the first pointer N+1 steps 


			     |
			     v


	D	-> 1 -> 2 -> 3 -> 4 -> 5 -> NULL

      second     Head       First


Move the first and second pointers together until the first pointer arrives past the last node 


			     |
			     v


	D	-> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
		
		 Head      Second           First

Second pointer points to the nth node counting from last so link node to the node's next next node 



				  |
				  v


	D	-> 1 -> 2 -> 3 ->   -> 5 -> NULL
	         
		 Head      Second           First
 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
public ListNode removeNthFromEnd(ListNode head, int n) {
	
	ListNode dummy = new ListNode(0);
	dummy.next = head; 
	ListNode first = dummy; 
	ListNode second = dummy;
	
	//Moves the first pointer so that the first and second nodes are separated by n nodes
	
	for (int i=1; i<=n+1; i++) {
		
		first = first.next;
	}

	//Move first to the end, maintaining the gap

	while (first!=null) {

		first=first.next;
		second=second.next;
	}

	second.next=second.next.next;
	return dummy.next;
}

Complexity Analysis

1
2
3
4
Time Complexity: 	O(L) 	The algorithm makes one traversal of the list of L nodes. Therefore
				time complexity is O(L)

Space Complexity: 	O(1)	Only constant extra space was used 





20-Valid Parentheses

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’, determine if the input string is valid

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets
  2. Open brackets must be closed in the correct order

Note that an empty string is also considered valid

1
2
3
4
Example 1: 

Input: "()"
Output: true
1
2
3
4
Example 2: 

Input: "()[]{}"
Output: true 
1
2
3
4
Example 3: 

Input: "(]"
Output: false
1
2
3
4
Example 4: 

Input: "([)]"
Output: false
1
2
3
4
Example 5: 

Input: "{[]}"
Output: true



Counting method

Intuition

Imagine you are writing a small compiler for your college project and one of the tasks or sub-tasks for the compiler would be to detect if the parenthesis are in place or not.

The algorithm we will look at in this article can be then used to process all the parenthesis in the program your compiler is compiling and checking if all the parenthesis are in place. This makes checking if a given string of parenthesis is valid or not, an important programming problem.

The expressions that we will deal with in this problem can consist of three different types of parenthesis:

  • ()
  • {}
  • []

Before looking at how we can check if a given expression consisting of thes parenthesis is valid or not, let us look at a simpler version of the problem that consists of just one type of parenthesis. So, the expressions we can encounter in this simplified version of the problem are:

1
2
3
4
5
6
7
(((((()))))) -- VALID

()()()()     -- VALID

(((((((()    -- INVALID

((()(())))   -- VALID

Let’s look at a simple algorithm to deal with this problem



  1. We process the expression one bracket at a time starting from the left

  2. Suppose we encounter an opening bracket ie. (, it may or may not be an invalid expression because there can be a matching ending bracket somewhere in the remaining part of the expression. Here, we simply increment the counter keeping track of the left parenthesis till now. left += 1

  3. If we encounter a closing bracket, this has two meanings:

    • There was no matching opening bracket for this closing bracket and in that case we have an invalid expression. This is the case when left==0 ie. when there are no unmatched left brackets available

    • We had some unmatched opening bracket available to match this closing bracket. This is the case when left>0 ie. we have unmatched left brackets available

  4. If we encounter a closing bracket ie. ) when left==0, then we have an invalid expression on our hands. Else, we decrement left thus reducing the number of unmatched left parenthesis available.

  5. Continue processing the string until all parenthesis have been processed

  6. If in the end we still have an unmatched left parenthesis available, this implies an invalid expression



The reason we discussed this particular algorithm here is because the approach for the approach for the original problem derives its inspiration from this very solution.

If we try and follow the same approach for our original problem, then it simply won’t work. The reason a simple counter based approach works above is because all the parenthesis are of the same type. So when we encounter a closing bracket, we simply assume a corresponding opening matching bracket to be available ie. if left>0

But in our problem, if we encounter say ], we don’t really know if there is a corresponding opening [ available or not. You could say:

Why not maintain a separate counter for the different types of parenthesis?

This doesn’t work because the relative placement of the parenthesis also matters here eg: [{]



If we simply keep counters here, then as soon as we encounter the closing square bracket, we would know there is an unmatched opening square bracket available as well. But, the **closest unmatched opening bracket available is a curly bracket and not a square bracket and hence the counting approach breaks here.



Stacks

An interesting property about a valid parenthesis expression is that a sub-expression. (Not every sub-expression) eg.

1
2
3
4
	{ [ [ ] { } ] } ( ) ( ) 

	  ^         ^
	  |         |

The entire expression is valid, but sub portions of it are also valid in themselves. This lends a sort of a recursive structure to the problem. For example consider the expression enclosed within the marked parenthesis in the diagram above. The opening bracket is at index 1 and the corresponding closing bracket is at index 6.

What if whenever we encounter a matching pair of parenthesis in the expression we simply remove it from the expression?

Let’s have a look at this idea below where we remove the smaller expressions one at a time from the overall expression and since this is a valid expression, we would be left with an empty string in the end.

1
2
3
The stack data structure can come in handy here in representing this recursive structure of the 
problem. We can't really process this from the inside out because we don't have an idea about the 
overall structure. But, the stack can help us process this recursively ie. from outside to inwards.

Lets take a look at the algorithm for this problem using stacks as the intermediate data structure.

Algorithm

  1. Initialize a stack S.
  2. Process each bracket of the expression one at a time
  3. If we encounter an opening bracket, we simply push it onto the stack. This means we will process it later, let us simply move onto the sub-expression ahead
  4. If encounter a closing bracket, then we check the element on top of the stack. If the element at the top of the stack is an opening bracket of the same type, then we pop it off the stack and continue processing. Else, this implies an invalid expression
  5. In the end, if we are left with a stack still having elements, then this implies an invalid expression

Lets take a look at the implementation for this algorithm

 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
36
37
38
39
40
41
42
43
44
45
46
class Solution {
	
	//Hash table that takes care of the mappings
	private HashMap<Character, Character> mappings; 

	//Initialize the hash map with mappings. This simply makes the code easier to read 
	public Solution() {
		
		this.mappings = new HashMap<Character, Character>(); 
		this.mappings.put(')', '(');
		this.mappings.put('}', '{');
		this.mappings.put(']', '[');
	}

	public boolean isValid(String s) { 
		
		// Initialize a stack to be used in the algorithm
		Stack<Character> stack = new Stack<Character>();

		for (int i=0; i< s.length(); i++) {
			
			char c = s.charAt(i);

			// If the current character is a closing bracket 

			if (this.mappings.containsKey(c)) {
				
				// Get the top element of the stack. If the stack is empty, set a dummy value of '#' 
				char topElement = stack.empty() ? '#' : stack.pop();

				// If the mapping for this bracket doesn't match the stack's top element, return false. 
				if (topElement != this.mappings.get(c)) {
					return false;
				}
			} else {
				
				//If it was an opening bracket, push to the stack  
				
				stack.push(c);
			}
		}

		//If the stack still contains elements, then it is an invalid expression. 
		return stack.isEmpty();
	}
}

Complexity Analysis

1
2
3
4
5
Time Complexity: 	O(n)	We simply traverse the given string one character at a time and push 
				and pop operations on a stack take O(1) time 

Space Complexity: 	O(n)	In the worst case, when we push all opening brackets onto the stack, we
				will end up pushing all the brackets onto the stack eg (((((((((((





21-Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

1
2
3
4
Example: 

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4



Recursive

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class solution {
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		
		if (l1 == null) return l2; 
		if (l2 == null) return l1;
		if (l1.val < l2.val) {
			
			l1.next = mergeTwoLists(l1.next, l2);
			return l1;
		} else {
			
			l2.next = mergeTwoLists(l1, l2.next);
			return l2;
		}
	}	
}



Non-Recursive

Similar approach and implemenation to the recursive solution above but a little more intuitive and does not require memory being held on the stack (as the recursive program runs it has to store variables on the stack so that when the program jumps back it is able to continue)

As with most other linked list solutions, a dummy node is utilized and two pointers are used to keep track of where we are in the the two linked lists.

 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
class solution {
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		
		ListNode returnNode = new ListNode(-1); 
		ListNode headNode = returnNode; 
		
		while (l1 != null && l2 != null) {
			if (l1.val <= l2.val) {
				returnNode.next = l1;
				l1 = l1.next;
			} else {
				returnNode.next = l2;
				l2 = l2.next; 
			}
			returnNode = returnNode.next;
		}

		if (l1 == null) {
			returnNode.next = l2;
		} else if (l2 == null) {
			returnNode.next = l1; 
		}

		return headNode.next; 
	}
}





22-Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
For example: 

Given n=3, a solution set is: 

[
  "((()))",
  "(()())".
  "(())()",
  "()(())",
  "()()()"
]



Brute Force

Intuition

We can generate all 2^(2n) sequences of ( and ) characters. Then we can check if each one is valid


Algorithm

To generate all sequences, we use recursion. All sequences of length n is just ( plus all sequences of length n-1, and then ) plus all sequences of length n-1.

To check whether a sequence is valid, we keep track of balance, the net number of opening brackets minuts closing brackets. If it falls below zero at any time, or doesn’t end in zero, the sequence is invalid - otherwise it is valid.

 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
36
37
38
39
40
41
42
43
44
class Solution {
	
	public List<String> generateParenthesis(int n) {
		
		List<String> combinations = new ArrayList(); 
		generateAll(new char[2*n], 0, combinations);
		return combinations;
	}

	public void generateAll(char[] current, int pos, List<String> result) {
		
		if(pos == current.length) {
			
			if (valid(current)) {
				result.add(new String(current));
			} 

		} else {
			current[pos] = '(';
			generateAll(current, pos+1, result);
			current[pos] = ')';
			generateAll(current, pos+1, result);
		
		}
	}

	public boolean valid(char[] current) {
		
		int balance = 0; 
		for (char c : current) {
			
			if(c == '(') {
				balance++;
			} else {
				balance--;
			}

			if(balance < 0) {
				return false; 
			}
		}
		return (balance == 0);
	}
}

Complexity Analysis

1
2
3
4
5
Time Complexity: 	O(2^2n * n)	For each of 2^2n sequences, we need to create an validate the 
					sequence, which takes O(n) work in the worst case 

Space Complexity: 	O(2^2n * n) 	Naively, every sequence could be valid, see Closure number for
					a tighter asymptotic bound 



Backtracking

Intuition and Algorithm

Instead of adding ( or ) every time as we do in the Brute Force algorithm, let’s only add them when we know it will remain a valid sequence. We can do this by keeping track of the number of opening and closing brackets we have placed so far.

We can start an opening bracket if we still have one (of n) left to place. And we can start a closing bracket if it would not exceed the number of opening brackets

 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
class Solution {
	
	public List<String> generateParenthesis(int n) {
		
		List<String> ans = new ArrayList(); 
		backtrack(ans, "", 0, 0, n);
		return ans; 
	}

	public void backtrack(List<String> ans, String cur, int open, int close, int max){
		
		if (cur.length() == max*2) {
			ans.add(cur);
			return;
		}

		if(open < max) {
			backtrack(ans, cur + "(", open + 1, close, max);
		} 
		
		if (close < open) {
			backtrack(ans, cur + ")", open, close +1, max);
		}
	}
}

Complexity Analysis

Our complexity analysis rests on understanding how many elements there are in generateParenthesis(n). This analysis is outside the scope of this article, but it turns out this is the nth Catalan number 1/(n+1) (2n choose n), which is bounded asymptotically by 4^n/(n* sqrt(n)).

1
2
3
4
5
Time Complexity: 	O((4^n)/sqrt(n))	Each valid sequence has at most n steps during the 
						backtracking procedure

Space Complexity: 	O((4^n)/sqrt(n))	As described above and using O(n) space to store the
						sequence

Another way to think about the runtime of backtracking algorithms on interviewers is O(b^d), where b is the branching factor and d is the maximum depth of recursion.

Backtracking is characterized by a number of decisions b that can be made at each level of recursion. If you visualize the recursion tree, this is the number of children each internal node has. You can also think of b as standing for “base”, which helps us remember that b is the base of the exponential.

If we make b decisions at each level of recursion, and we expand the recursion tree to d levels (ie. each path has a length of d), then we get b^d nodes. Since backtracking is exhaustive and must visit each of these nodes, the runtime is O(b^d)



Closure Number

To enumerate something, generally we would like to express it as a sum of disjoint subsets that are easier to count.

Consider the closure number of a valid parentheses sequence s: the least index >= 0 so that `S[0], S[1], … , S[2 * index + 1] is valid. Clearly, every parentheses sequence has a unique closure number. We can try to enumerate them individually.



Algorithm

For each closure number c, we know the starting and ending brackets must be at index 0 and 2 * c + 1. Then, the 2 * c elements between must be a valid sequence, plus the rest of the elements must be a valid sequence.

This is just some minor improvement to the backtracking solution using the fact that for all valid solutions the first char is always ‘(’ and the lat char is always ‘)’. We initialize the starting string to ‘(’ and set the recursion bottom condition to string reaching length of 2 * n - 1 - we know that we need to append a bracket at the end. There will not be much of an improvement in the runtime however.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
	public List<String> generateParenthesis(int n) {
		List<String> ans = new ArrayList(); 
		if (n==0) {
			ans.add("");
		} else {
			for (int c=0; c<n; ++c)
				for (String left: generateParenthesis(c))
					for (String right: generateParenthesis(n-1-c))
						ans.add("(" + left + ")" + right);
		}
		return ans;
	}
}

Complexity Analysis

1
2
3
Time Complexity: 	O((4^n)/sqrt(n))

Space Complexity: 	O((4^n)/sqrt(n))





23-Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and descibe its complexity:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Example: 

Input: 
[
	1 -> 4 -> 5,
	1 -> 3 -> 4,
	2 -> 6
]

Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6



Brute Force

Intuition and Algorithm

  • Traverse all the linked lists and collect the values of the nodes into an array
  • Sort and iterate over this array to get the proper value of nodes
  • Create a new sorted linked list and extend it with the new nodes

As for sorting you can refer to the Algorithms/Data Structures CheatSheet for more about sorting algorithms.





146-LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1

put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up: Could both of these operations be done in O(1) time complexity?

Example:

1
2
3
4
5
6
7
8
LRUCache cache = new LRUCache(2 /* capacity */);

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); 			// returns 1 
cache.put(3, 3); 		// evicts key 2
cache.get(2);			// returns -1 (not found)
	

Lowest Common Ancestor

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode current = root;
    while (current != null){
        if (p.val < current.val && q.val < current.val)		// Both located in left side.
            current = current.left;
        else if (p.val > current.val && q.val > current.val)	// Both located in right side
            current = current.right;
        else
            return current;		// Seperate branches, therefore current is lca.
    }
    return null;
}

Count And Say

The updated version runs in 2ms and passes 96.85% submissions.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public String countAndSay(int n) {
    String result = "1";		// initial result
    StringBuilder temp;			// to create intermediate strings efficiently.
    int len;					// length of the result string.
    for (int i = 1; i < n; ++i){	// We need to iterate n-1 times, because 1st result is 1
        int startIndex = 0;			// we will look at each index of result
        temp = new StringBuilder();	// and store freq,char in the builder
        len = result.length();
        while (startIndex < len){
            char ch = result.charAt(startIndex++);	// get the char at startIndex, and increment it, because we also want to look at the next character
            int count = 1;					// intialize it's count to 1, we just saw it.
            while (startIndex < len && ch == result.charAt(startIndex)){
                count++;			// If next also matches, increment count and startIndex
                startIndex++;
            }
            temp.append(count).append(ch);	// No more match, Add the freq and the char
        }
        result = temp.toString();	// Update result to generate the next cound-and-say
    }
    return result;
}

Maximum SubArray

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public int maxSubArray(int[] nums) {
    int localMax = nums[0];		// keeps track of max sum between the previous and current
    int globalMax = nums[0];	// keeps track of global max sum.

    /*
    The idea is as follows:
    If the current element is greater than the previous local max, then we found an element that is a better option then before.
    Then, if that localmax changed and is greater than our global max, update our global max.
    */

    for (int i = 1; i < nums.length; i++){
        localMax = Math.max(localMax + nums[i], nums[i]);
        globalMax = Math.max(localMax, globalMax);
    }

    return globalMax;
}

Plus One

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public int[] plusOne(int[] digits)
{
    digits[digits.length-1]++;			// Add one to the last place.
    if (digits[digits.length-1] == 10)	// If it became 10,
    {
        for (int i = digits.length-1; i > 0; i--)	// Then add one to its previous place
        {
            if (digits[i] == 10){	// If that also results in 10, keep propogating that 1
                digits[i-1]++;		// upstream
                digits[i] = 0;
            }
        }
        if (digits[0] == 10){	// If the index 0 is 10, then the number is a multiple of 10.
            digits = new int[digits.length+1];
            digits[0] = 1;		// So increase length by 1 and set index 0 to 1.
        }
    }
    return digits;
}

Sqrt of X

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public int mySqrt(int x) {
    long x1 = 10 - (100 - x)/20;		// Using Newton's method of computing square roots.
    boolean done = false;
    while (!done)
    {
        long x2 = x1 - (x1*x1 - x)/(2*x1);
        if (x2 == x1)
            done = true;
        else
            x1 = x2;
    }
    return (int)x1-1;
}

Climbing Stairs

 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
public int climbStairs(int n) {
    if (n < 4)		// I chose n < 4 because climbStairs(0 <= n <= 3) = n
        return n;
    int[] dp = new int[n+1];
    for (int i = 0; i < 4; i++)
        dp[i] = i;
    //return naiveDP(n, dp);
    return efficientDP(n);
}

public int naiveDP(int n, int dp[]){
    if (dp[n] != 0)		// If already computed, return it.
        return dp[n];
    int ways =  naiveDP(n-1, dp) + naiveDP(n-2, dp);	// Just like Fibonacci.
    dp[n] = ways;		// Save it.
    return ways;
}

public int efficientDP(int n){
    if (n < 4)
        return n;
    int[] dp = new int[n+1];		// Initialize dp of length n+1 to store n'th way.
    for (int i = 0; i < 4; i++)
        dp[i] = i;					// climbStairs(0 <= n <= 3) = n
    for (int i = 3; i <= n; i++)	// climbStairs(n) = climbStairs(n-1) + climbstairs(n-2);
        dp[i] = dp[i-1] + dp[i-2];  // So fetch those values from the dp array.
    return dp[n];
}

Remove Duplicates from sorted list

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public ListNode deleteDuplicates(ListNode head){
    ListNode current = head;
    // while we haven't reached the tail
    while (current != null && current.next != null)
    {
        // if current's next is the same as current, skip and update its next
        while (current.next != null && current.val == current.next.val)
            current.next = current.next.next;
        current = current.next;
    }
    return head;
}

Same Tree

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public boolean isSameTree(TreeNode p, TreeNode q)
{
    if (p == null && q == null)		// Two empty trees
        return true;
    // If one of the node is null, the two trees can't be equal.
    if ((p == null && q != null) || (p != null && q == null))
        return false;
    // If the values in the two nodes are same, compare its's left and right sub-tree.
    if (p.val == q.val)
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    return false;		// If nothing worked out, they can't be same.
}

Symmetric Tree

 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
36
37
38
39
public boolean isSymmetric(TreeNode root)
{
    return isSymmetricIterative(root);
}

public boolean isSymmetricIterative(TreeNode root)
{
    Queue<TreeNode> track = new LinkedList<>();
    track.add(root);		// Add the root twice so we can compare its left and right
    track.add(root);
    while (!track.isEmpty())
    {
        TreeNode x = track.poll();		// Remove 2 nodes
        TreeNode y = track.poll();

        if (x == null && y == null)		// If they are both null, skip it.
            continue;
        if (x == null || y == null || x.val != y.val)
            return false;				// If values don't match or one is null
        track.add(x.left);		// Otherwise add them in this order -> LRRL
        track.add(y.right);		// because we need to compare left most with the
        track.add(x.right);		// right most, then inner left with inner right.
        track.add(y.left);
    }
    return true;		// Everything's all right, so they must be symmetric.
}

public boolean isSymmetricRecursive(TreeNode root)
{
    return helperRecursive(root, root);
}

private boolean helperRecursive(TreeNode x, TreeNode y)
{
    if (x == null || y == null)		// Base Case: Both or one is null, so true
        return true;
    return (x.val == y.val && helperRecursive(x.left, y.right) && helperRecursive(x.right, y.left));
    // Check if values match and 1.left matches with the 2.right and 1.right matches with 2.left
}

Max Depth of Binary Tree

1
2
3
4
5
6
/*
If root is null, height is 0 else add 1 and find if the left or the right has a greater depth.
*/
public int maxDepth(TreeNode root) {
    return root == null ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Convert Sorted Array to Binary Search Tree

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public TreeNode sortedArrayToBST(int[] nums)
{
    return aux(nums, 0, nums.length-1);
}

private TreeNode aux(int[] n, int left, int right)
{
    if (left > right)					// Either empty, or return a null node
        return null;

    int mid = (left+right+1)/2;			// Create a node with the middle value
    TreeNode root = new TreeNode(n[mid]);
    root.left = aux(n, left, mid-1);	// Compute the left (which is the mid in left side)
    root.right = aux(n, mid+1, right);	// Compute the right (which is the mid in right side)
    return root;
}

Balanced Binary Tree

 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
36
37
38
39
40
41
42
43
public boolean isBalanced(TreeNode root)
{
    return isBalancedBottomUp(root);
}

public boolean isBalancedTopDown(TreeNode root)
{
    if (root == null)
        return true;
    // if difference between root's left and right is > 1, they're not balanced
    if (Math.abs((getHeight(root.left) - getHeight(root.right))) > 1)
        return false;
    // otherwise, we need to check if the left and right subtree are also balanced.
    return isBalanced(root.left) && isBalanced(root.right);
}

private int getHeight(TreeNode node)
{
    // Standard height of a binary tree calculator
    if (node == null)
        return 0;
    return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

public boolean isBalancedBottomUp(TreeNode root)
{
    return getHeight2(root) != -1;	// -1 means not balanced.
}

private int getHeight2(TreeNode node)
{
    if (node == null)
        return 0;

    int lHeight = getHeight2(node.left);	// Get the height of left and right tree
    int rHeight = getHeight2(node.right);

    // If at any point there was a height difference of more than 1 or previous node's leftheight || rightheight returned -1, return -1 to let the next node know there was an imbalance.
    if ((Math.abs(lHeight-rHeight) > 1) || lHeight == -1 || rHeight == -1)
        return -1;

    return 1 + Math.max(lHeight, rHeight); // Else carry on with the normal procedure
}

Minimum Depth of Binary Tree

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public int minDepth(TreeNode root) {
    // Base case
    if (root == null) return 0;
    // Left is null, find minheight from right side
    if (root.left == null) return 1 + minDepth(root.right);
    // Right is null, find minheight from left side
    if (root.right == null) return 1 + minDepth(root.left);
    // Else, both are not null, so compute min height from the two sides.
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

Path Sum

1
2
3
4
5
6
7
8
9
public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null)
        return false;	// No sum exist
    sum -= root.val;	// Sum decreases
    if (root.left == null && root.right == null)	// If we are at a leaf
        return sum == 0;	// Check if the sum is 0.
    return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    // Otherwise look if you can make sum = 0 by exploring the left or right side.
}

Pascal’s Triangle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> pt = new ArrayList<>();
    for (int i = 0; i < numRows; i++)	// Need to add all n rows
    {
        List<Integer> temp = new ArrayList<>();		// temp list to store values
        for (int j = 0; j <= i; j++)
        {
            if (j == 0 || i == j)		// First and last values are always 1.
                temp.add(1);
            else	// Else, get the previous row and surrounding two values and add them
                temp.add(pt.get(i-1).get(j-1) + pt.get(i-1).get(j));
        }
        pt.add(temp);		// Add it to pt.
    }
    return pt;
}

Valid Palindrome

 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
public boolean isPalindrome(String s) {
    if (s.length() > 0){		// Only do this is s is not empty
        s = s.toLowerCase();	// Convert it to lowercase
        int left = 0;			// Initialize left and right pointers
        int right = s.length()-1;
        while (left < right)	// continue while we haven't hit the middle of the string
        {
            // If char at left is not a letter or a number, skip it.
            if (!Character.isLetter(s.charAt(left)) && !Character.isDigit(s.charAt(left)))
                left++;
            // Same with char at right.
            else if (!Character.isLetter(s.charAt(right)) && !Character.isDigit(s.charAt(right)))
                right--;
            //Char's are now alphanumeric.
            else if (s.charAt(left) != s.charAt(right))	// If they don't match
                return false;	// return false
            else	// They matched, so try to match the inner string
            {
                left++;
                right--;
            }
        }
    }
    return true;	// No mismatch found, return true.
}

Pascal’s Triangle II

1
2
3
4
5
6
7
8
9
public List<Integer> getRow(int rowIndex)
{
    ArrayList<Integer> row = new ArrayList<>();
    row.add(1);	// First is always 1.
	// Using the nth row formula to compute the coeeficients. You can google "nth row Pascal"
    for (int i = 0; i < rowIndex; i++)
        row.add((int)(1.0*row.get(i)*(rowIndex-i)/(i+1)));
    return row;
}

Best Time to Buy and Sell Stock

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/*
The general idea is that if the price you are looking at right now in the array minus the minimum observed so far is greater than the maximum profit you recorded, update the max.
*/
public int maxProfit(int[] prices) {
    if (prices.length == 0)		// Empty array
        return 0;
    int min = prices[0];

    int max = 0;
    for (int i = 1; i < prices.length; i++)
    {
        if (prices[i] < min)
            min = prices[i];
        else if (prices[i] - min > max)
            max = prices[i]-min;
    }
    return max;
}

Best Time to Buy and Sell Stock II

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
/*
The general idea is that the moment you observe a valley and consecutive peak, make the trade by buying the stock on the valley day and selling it on the peak day.
*/
public int maxProfit(int[] prices) {
    int sum = 0;
    for (int i = 0; i < prices.length-1; i++)
        if (prices[i+1] > prices[i])
            sum += (prices[i+1] - prices[i]);
    return sum;
}

Single Number

1
2
3
4
5
6
7
8
9
/*
The general idea is that XOR of two same numbers returns 0 and XOR with 0 returns the same number. So if there is only one element that doesn't have a pair, all the remaining will XOR with themselves at one point and give 0 but not the singleton element.
*/
public int singleNumber(int[] nums) {
    int num = nums[0];
    for (int i = 1; i < nums.length; i++)
        num ^= nums[i];
    return num;
}

Linked List Cycle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// Using the slow-fast runner technique.
public boolean hasCycle(ListNode head) {
    if (head == null)
        return false;
    ListNode first = head;	// Slow runner
    ListNode second = first.next;		// Fast Runner
    // while second is not at the end or it isn't the tail
    while (second != null && second.next != null)
    {
        if (second == first)	// If fast made a full loop and met up with slow
            return true;		// We got a cycle
        first = first.next;		// Slow moves one step
        second = second.next.next;	// Second advances two.
    }
    return false;		// We don't have a cycle
}

Min Stack

 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
class MinStack {

    int min;
    Stack<Integer> stack;

    public MinStack() {
        min = Integer.MAX_VALUE;
        stack = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);		// Push the value
        if (x < min)		// If that value is minimum than we have, update min
            min = x;
        stack.push(min);	// Push the minimum on top of the stack for constant time
    }						// minimum retrieval.

    public void pop() {
        stack.pop();		// Pop the minimum.
        stack.pop();		// Pop the actual element meant to be popped
        if (stack.isEmpty())	// If empty, min is Max int value
            min = Integer.MAX_VALUE;
        else
            min = stack.peek();	// Otherwise, min would be the top most element since we
    }							// always push the minimum on top of any element we push.

    public int top() {
        return stack.elementAt(stack.size()-2);	// Top element is actually at second last
    }				// index since the last element is the minimum.

    public int getMin() {
        return min;
    }
}

Intersection of Two Linked Lists

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/*
The general idea is that if you are done traversing any of the lists, make it's pointer point to the head of the other list and start iterating. The reasoning is that the second time they iterate, they will have traversed exactly the same distance (it's length plus the other list's head to the intersecting node) and will meet at the intersecting node.
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int count = 0;
    ListNode pA = headA;
    ListNode pB = headB;
    while (pA != pB){
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

Two Sum II - Input array is sorted

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length-1;
    while (left < right)	// Narrow down the window from both sides until they add up.
    {
        int sum = numbers[left] + numbers[right];
        if (sum > target)	// We overshot, so decrease the window from right
            right--;
        else if (sum < target)	// Undershot, increase windows from left so next sum is more
            left++;
        else
            break;				// Found the two numbers
    }
    return new int[] {left+1, right+1};	// +1 because LeetCode followed 1-n indexing.
}

Excel Sheet Column Title

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public String convertToTitle(int n) {
    String res = "";
    while (n > 0)
    {
        /* 1 is A and 26 is Z, so n-1 to change it to 0-25 scheme. Then, % 26 to find how
        much it is off on a full alphabet cycle, add 65 (ASCII for A) and convert it to char
        */
        res = String.valueOf((char)(65+((n-1)%26))) + res;
        n = (n-1) / 26;	// Subtract 1 and divide by 26 to get prepare for the next character
    }
    return res;
}

Majority Element

Uses Moore’s Algorithm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// This is the implementation of Moore's Algorithm for O(n) complexity.
public int majorityElement(int[] nums) {
    int major = nums[0];
    int count = 1;

   for (int i = 0; i < nums.length; i++){
        if (major == nums[i])
            count++;
        else
            count--;
        if (count == 0){
            major = nums[i];
            count = 1;
        }
    }
    return major;
}

Excel Sheet Column Number

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
/*
Start from the end of String s, compute the ASCII for the char, +1 for 1-26 Alphabet-Scheme (hence -64 instead of -65) and multiply it to 26^{distance from the end of the string}
*/
public int titleToNumber(String s) {
    int length = s.length()-1;
    int total = 0;
    for (int i = length; i > -1; i--)
        total += (int)(s.charAt(i)-64) * Math.pow(26,length-i);
    return total;
}

Factorial Trailing Zeroes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/*
The general idea is that every factorial that has 5 as a multiple also has 2 to multiply to 10. So if we can count the number of times we can divide n by 5, should gives us the number of trailing zeroes. O(log(n) base 5) complexity.
*/
public int trailingZeroes(int n) {
    int res = 0;
    while (n > 4)
    {
        res += n / 5;
        n /= 5;
    }
    return res;
}

Combine Two Tables

1
2
select FirstName, LastName, City, State
from Person left join Address on Address.personId = person.personId;

Second Highest Salary

1
2
3
select max(salary) as SecondHighestSalary
from Employee
where salary not in (select max(salary) from employee);

Employees Earning More Than Their Managers

1
2
3
select emp.Name as Employee
from Employee emp, Employee man
where emp.managerId = man.Id and emp.salary > man.salary;

Duplicate Emails

1
2
3
4
select email
from person
group by (email)
having count(*) > 1;

Customers Who Never Order

1
2
3
select name as Customers
from Customers
where customers.id not in (select customerId from orders);

Rotate Array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public void rotate(int[] nums, int k) {
    k %= nums.length;		// k == nums.length ? Then it's a full rotation and no change
    if (k == 0)
        return;
    reverse(nums, 0 , nums.length-1);	// First reverse the full array
    reverse(nums, 0, k-1);				// Then reverse element from index 0 to k-1
    reverse(nums, k, nums.length-1);	// Then reverse all elements from k to end of Array
}

// Reverse function that reverses the array from specified indices.
public void reverse(int[] nums, int start, int end)
{
    while (start < end){
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

Delete Duplicate Emails

1
2
3
delete from Person
where Id not in (select min_id from
(select min(Id) as min_id from Person group by Email) as a)

Rising Temperature

1
2
3
select w2.id
from weather w1, weather w2
where Datediff(w2.recorddate, w1.recorddate) = 1 and w2.temperature > w1.temperature;

X of a Kind in a Deck of Cards

 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
public boolean hasGroupsSizeX(int[] deck) {
    HashMap<Integer, Integer> freq = new HashMap<>();

    for (int i = 0; i < deck.length; i++)		// Record the frequencies
        freq.put(deck[i],freq.getOrDefault(deck[i],0)+1);

/*
deck = [1,1,2,2,2,2,3,3,3,3,3,3]
number 1 has len of 2, number 2 has len of 4, number 3 has len of 6, they share a Greatest common divisor of 2, which means diving them into group of size X = 2, will be valid. Thus we just have to ensure each length (of a number) shares a Greatest Common Divisor that's >= 2.
*/
    int hcf = 0;
    for (int i: freq.keySet())
        hcf = gcd(hcf, freq.get(i));

    return hcf > 1;
}

private static int gcd(int x, int y)
{
    int temp = 0;
    while (y != 0){
        temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

Reverse Integer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public int reverse(int x) {
    int sign = x < 0 ? -1 : 1;
    x = x * sign;							// Make x positive
    long n = 0;
    while (x > 0){
        n = n * 10 + x % 10;				// Start adding from the end.
        x /= 10;
    }
    return (int)n == n ? (int)n*sign : 0;	// Try converting to int from long, if no change,
}											// Return n * sign, else 0 cause overflow.

Add Two Numbers

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    int carry = 0;							// To record the carry
    int sum = 0;							// To record the total of two vals
    ListNode dummy = new ListNode(0);		// Dummy's next is the actual head
    ListNode curr = dummy;
    do{
        if (l1 == null)						// If one of the node is null, we set it to a
            l1 = new ListNode(0);			// dummy value of 0 so we can adjust for
        if (l2 == null)						// different length of the two lists.
            l2 = new ListNode(0);
        sum = l1.val + l2.val + carry;		// Add the two vals and the carry.
        carry = sum < 10 ? 0 : 1;			// Record the carry for the next iteration
        curr.next = new ListNode(sum % 10);	// next node's value is sum % 10.
        curr = curr.next;					// advance current, l1 and l2.
        l1 = l1.next;
        l2 = l2.next;
    } while(l1 != null || l2 != null);
    if (carry == 1)							// In the end, if carry is 1, it was from
        curr.next = new ListNode(carry);	// from adding last terms, so make next node 1

    return dummy.next;						// Return the actual head.
}

Longest Substring Without Repeating Characters

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0)
        return 0;

    int[] hash = new int[128];					// To store the occurence of characters
    int maxLength = 0;
    for (int i = 0, j = 0; j < s.length(); j++){
        i = Math.max(hash[s.charAt(j)], i);		// Check the most recent index of character.
        maxLength = Math.max(maxLength, j-i+1);	// That minus current pointer gives length
        hash[s.charAt(j)] = j+1;				// Record the index of the next character.
    }
    return maxLength;
}

House Robber

 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
/*
The basic idea is that if you are robbing house i, the maximum loot may come from by robbing the i-2th house or by robbing the i-3th house. Therefore rob both and then find the path that gave the maximum profit.
Example: loot = [1,9,3,8,4,3,6,4,3,5,7,6]
Profit DP = [1,9,4,17,13,20,23,24,26,29,33,35]
Here,
	dp[2] = loot[2] + loot[1]
	dp[4] = loot[4] + max(dp[2], dp[1])
	dp[5] = loot[5] + max(dp[3], dp[2]) and so on.
In the end, just compare the last two elements to check which path gave us the maximum profit.
Some people might not prefer modifying the original nums array. In that case, you can initialize another dp array of same length, initialize the first two elements as dp[0] = nums[0] and dp[1] = nums[1] and dp[3] = nums[0] + nums[2] and then performing the same loop. In that case, you would be using O(n) space.
*/
public int rob(int[] nums) {
    if (nums.length == 0 || nums == null)			// 3 Base Case
        return 0;
    if (nums.length == 1)
        return nums[0];
    else if (nums.length == 2)
        return Math.max(nums[0], nums[1]);
    else{
        nums[2] = nums[0] + nums[2];				// House 3 profit is rob House 1 and 3.
        for (int i = 3; i < nums.length; i++)
            nums[i] = nums[i] + Math.max(nums[i-2], nums[i-3]);
        return Math.max(nums[nums.length-1], nums[nums.length-2]);
    }
}

Happy Number

 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
36
37
38
39
40
41
42
43
public boolean isHappy(int n) {
        return isHappyConstantSpace(n);		// Much faster than set method
        //return isHappySet(n);
    }

    private boolean isHappyConstantSpace(int n){
        int numSeenLessThan10 = 0;		// If I see 10 single digits, then it means that I am
        while (n != 1){					// now starting to see repititions.
            if (n < 10)					// Each time I see a num < 10, increment the counter
                numSeenLessThan10++;
            if (numSeenLessThan10 > 9)
                return false;
            n = getSquare(n);			// Get the total of square of its digits.
        }
        return true;
    }

/*
The general idea is that the moment you see a repition, it can't be a happy number, so keep track of digit square obtained so far. If they hit 1, well and good, otherwise there will be some repition, so return false.
*/
    private boolean isHappySet(int n){
        HashSet<Integer> seen = new HashSet<>();		// Keep track of numbers
        while (true){
            n = getSquare(n);							// Get the sum of digits square
            if (n == 1)									// If it's 1, it's a happy number
                return true;
            else if (seen.contains(n))					// If it's a repition of something
                return false;							// seen before, it's not a happy no.
            else
                seen.add(n);							// If not seen, add it.
        }
    }

    private int getSquare(int n){		// Add the squares of the digits.
        int total = 0;
        while (n != 0){
            int digit = n % 10;
            total += digit * digit;
            n /= 10;
        }
        return total;
    }
}

Remove Linked List Elements

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val)				// While head contains the val, skip
        head = head.next;								// the head
    ListNode current = head;
    while (current != null && current.next != null){	// While we have something to iterate
        if (current.next.val == val)					// If current's val match, skip the
            current.next = current.next.next;			// next node.
        else
            current = current.next;						// Else advance to the next node.
    }
    return head;
}

Count Primes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public int countPrimes(int n) {
    if (n < 2)
        return 0;							// No prime numbers for numbers < 2
    boolean[] store = new boolean[n];		// Using Sieve of Eratosthenes
    for (int i = 2; i*i <= n; i++)			// Start from i = 2 to sqrt(n)
        if (!store[i])						// If store[i] = false, then mark all its
            for (int j = i*i; j < n; j += i)// multiples in the store as true
                store[j] = true;			// True = not a prime, false = prime
    int count = 0;
    for (int i = 2; i < n; i++)				// Loop through the array, count
        if (!store[i])
            count++;
    return count;
}

Isomorphic Strings

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length())			// Can't be isomorphic is string lengths do not
        return false;						// match
    char[] hashS = new char[128];			// To store String s' match
    char[] hashT = new char[128];			// To store String t's match
    for (int i = 0; i < s.length(); i++){
        char charS = s.charAt(i), charT = t.charAt(i);
        if (hashS[charS] != hashT[charT])	// If the values at respective characters index
            return false;					// do not match, return false
        hashS[charS] = (char)(i+1);			// Otherwise, mark those index with the same
        hashT[charT] = (char)(i+1);			// arbitrary value. I chose a simple (i+1) to
    }										// to mark both the hash with the same value.
    return true;							// Everything worked out, return true;
}

Reverse LinkedList

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Recursive
public ListNode reverseList(ListNode head) {	// Very tricky. Refer to the demo below
    if (head == null || head.next == null)
        return head;
    ListNode node = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return node;
}

//Iterative
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null)
        return head;						// No point in reversing empty or 1-sized list
    ListNode curr = head, prev = null;
    ListNode nextNode;
    while (curr != null){					// While we haven't reached the tail
        nextNode = curr.next;				// Store the next node
        curr.next = prev;					// Current's next becomes it's previous
        prev = curr;						// Advance previous to current.
        curr = nextNode;					// Make current the actual next node
    }
    return prev;							// Current is at null, so it's previous is the
}											// new head.

reverse Linked list

Contains Duplicate

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public boolean containsDuplicate(int[] nums) {
    if (nums.length < 2)
        return false;							// There can't be any duplicates.
    HashSet<Integer> store = new HashSet<>();	// Store unique values.
    for (int n: nums){
        if (!store.add(n))						// Add func returns true if n was'nt present,
            return true;						// false if duplicate. Therefore if it was a
    }											// duplicate, return true.
    return false;								// No duplicates, so return false
}

Contains Duplicate II

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public boolean containsNearbyDuplicate(int[] nums, int k) {
    if (nums.length < 2)
        return false;
    int left = 0, right = 0;
    HashSet<Integer> store = new HashSet<>();	// Use a rotating window of size k
    while (right < nums.length){				// While we haven't processed everything
        if (store.contains(nums[right]))		// If our current window contains duplicate
            return true;
        store.add(nums[right]);					// No duplicates in the window
        right++;								// Increase right to visit the new element
        if (right - left > k){					// If window becomes > k
            store.remove(nums[left]);			// remove the number on the left side of
            left++;								// the window and increase the left counter
        }										// for new window from the next index
    }
    return false;								// No duplicates found in any window.
}

Implement Stack Using Queues

 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
class MyStack {
    Deque<Integer> stack;
    /** Initialize your data structure here. */
    public MyStack() {
        stack = new ArrayDeque<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        stack.add(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return stack.removeLast();
    }

    /** Get the top element. */
    public int top() {
        return stack.peekLast();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return stack.isEmpty();
    }
}

Invert Binary Tree

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public TreeNode invertTree(TreeNode root) {
    if (root == null)
        return null;
    TreeNode temp = root.left;		// Swap the left and right nodes
    root.left = root.right;
    root.right = temp;
    invertTree(root.left);			// Then swap the subsequent trees of those nodes.
    invertTree(root.right);
    return root;					// Return the original root.
}

Fibonacci Number

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Iterative
public int fib(int N) {
    if (N < 2)						// fib(0) = 0; fib(1) = 1
        return N;
    int f0 = 0, f1 = 1, fn = 0;
    for (int i = 2; i <= N; i++){
        fn = f0 + f1;				// fib(n) = fib(n-1) + fib(n-2)
        f0 = f1;					// f0 becomes f1
        f1 = fn;					// f1 becomes fn
    }
    return f1;
}

// Dynamic Programming
private int fibDP(int N){
    if (N < 2)
        return N;
    int[] dp = new int[N+1];		// To store intermediate result
    dp[1] = 1;						// fib(0) = 0; fib(1) = 1
    for (int i = 2; i <= N; i++)
        dp[i] = dp[i-1]+dp[i-2];	// fib(i) = fib(i-1) + fib(i-2)
    return dp[N];					// Return the last number in the array
}

kth Largest Element

  1. The minheap algorithm has $O(n lg n) $ complexity and $O(1)$ space. The idea here is that we use a minheap to keep only the k greatest elements. If size becomes more than k, we remove the smallest element at the top of the heap. Thereby, at the end, our kth largest element will be at the top.
  2. QuickSelect Algorithm performs in $O(n)$ best case, $O(n^2)$ worst case when the pivot chosen is always the largest, so we use a random pivot.
 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// MinHeap Algorithm
public int kthLargest(int[] nums, int k){
    PriorityQueue<Integer> q = new PriorityQueue<>((n1,n2) -> n1 - n2);	// Initialize minheap
    for (int n: nums){
        q.add(n);				// Add number one by one
        if (q.size() > k)		// If size is greater than k
            q.poll();			// Remove the topmost element
    }
    return q.poll();			// The topmost element is our answer
}

// QuickSelect Algorithm - Hoare's Partition Scheme

private int[] arr;

public int kthLargest(int[] nums, int k){
	arr = nums;
	return quickselect(0, nums.length-1, nums.length-k);// kth largest is (n-k)th largest
}

private int quickselect(int left, int right, int k){
	if (left == right)					// Array contains only 1 element, that's the answer
  		return arr[left];
	Random rand = new Random();				// Choose a random pivot between left and right
	int pivotIndex = left + rand.nextInt(right-left);	// but not left
	pivotIndex = partition(left, right, pivotIndex);	// Partition, and find it's correct index
	if (k == pivotIndex)					// That index is equal to kth statistic
  		return arr[pivotIndex];
	else if (k < pivotIndex)			// If it's less than the index, our ans lies in the
  		return quickselect(left, pivotIndex-1, k);	// left side
	else
  		return quickselect(pivotIndex+1, right, k);	// Otherwise, it's on the right side.
}

private int partition(int left, int right, int pivotIndex){
	int pivot = arr[pivotIndex];			// Partition element
	swap(pivotIndex, right);				// Move that element to the end
	int wall = left - 1;					// wall is initially before everything
	for (int i = left; i < right; i++){
  		if (arr[i] < pivot)				// If the current element is < than the pivot, then
    		swap(i, ++wall);			// we need to swap it with the element next to wall.
	}
	swap(right, ++wall);					// Lastly, swap the element at wall and the end.
	return wall;
}

private void swap(int i, int j){
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

Power Of Two

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public boolean isPowerOfTwo(int n) {
    if (n < 1)
        return false;		// n < 0 cannot be powers of 2
    while (n > 2){
        if (n % 2 != 0)		// If n is odd, it can't be a power of 2.
            return false;
        n = n / 2;			// It is a multiple of 2, so divide it by 2.
    }
    return true;			// n came out to be 1 which is a power of 2, so return true.
}

Valid Sudoku

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
private char[][] board;
public boolean isValidSudoku(char[][] board){
this.board = board;
return rowCheck() && colCheck() && boxCheck();	// Check row first, then column and at
}												// last, boxes because they are time
                                                // consuming.
  
private boolean onePassCheck(){
  HashSet<Integer>[] rows = new HashSet[9];		// 1 HashSet for each row
  HashSet<Integer>[] columns = new HashSet[9];	// 1 HashSet for each column
  HashSet<Integer>[] boxes = new HashSet[9];	// 1 HashSet for each box.

  for (int i = 0; i < 9; i++){
      rows[i] = new HashSet<>();
      columns[i] = new HashSet<>();
      boxes[i] = new HashSet<>();
  }

  for (int i = 0; i < 9; i++){
      for (int j = 0; j < 9; j++){
          int n = (int)(board[i][j]);
          if (n != -2){							// -2 = '.'		
              int boxIndex = (i/3) * 3 + j/3;	// Calculate which box we are in.
              if (!rows[i].add(n) || !columns[j].add(n) || !boxes[boxIndex].add(n))
                  return false;					// If the row set or the column set or the
          }										// box set contains that val, return false.
      }
  }

  return true;
}

private boolean rowCheck(){						// Horizontal check
    boolean[] arr;
    for (char[] row: board){
      arr = new boolean[9];
      for (char c: row){
        int val = c-'0';
        if (val != -2){								// val = -2 means '.' in the board
          if (arr[val-1])							// If val already seen, invalid sudoku
            return false;
          arr[val-1] = true;						// else, Mark that index as seen.
        }
      }
    }
    return true;
  }

  private boolean colCheck(){						// Vertical Check.
    boolean[] arr;
    for (int col = 0; col < board.length; col++){
      arr = new boolean[9];
      for (int row = 0; row < board[0].length; row++){
        int val = board[row][col]-'0';
        if (val != -2){
          if (arr[val-1])
            return false;
          arr[val-1] = true;
        }
      }
    }
    return true;
  }

  private boolean boxCheck(){					// For the 9 sub boxes, let the single
    for (int i = 0; i < 9; i+=3){				// box checker check it's validity.
      for (int j = 0; j < 9; j+=3)				// If any of the subbox was invalid,
        if (!singleBoxCheck(i,j))				// we abort and return false.
          return false;
    }
    return true;
  }

  private boolean singleBoxCheck(int topRightRow, int topRightCol){
    boolean[] arr = new boolean[9];
    for (int i = 0; i < 3; i++){				// Each sub box has 3 rows and 3 columns
      for (int j = 0; j < 3; j++){
        int val = board[topRightRow+i][topRightCol+j]-'0';	// This gives us the value at 
        if (val != -2){							// each cell in the sub box and we fill the
          if (arr[val-1])						// arr with all values that are seen.
            return false;						// If seen twice, return false;
          arr[val-1] = true;
        }
      }
    }
    return true;
  }
}

Implement Queue Using Stack

 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
/*
Since we reverse stack1 into stack2, stack2 is basically our queue, so if stack2 isn't empty, then the topmost element is what we need when we pop or peek. If it is empty, then again fill it with whatever's there is stack1, and it again becomes the correct queue.
*/
Stack<Integer> stack1;
Stack<Integer> stack2;

public MyQueue() {
    stack1 = new Stack<>();
    stack2 = new Stack<>();
}

public void push(int x) {
    stack1.push(x);			// Push onto stack1
}

public int pop() {
    peek();					// First call the peek function, to make sure stack 2 isn't
    return stack2.pop();	// empty. Then, the topmost element of stack2 is what we want
}

/** Get the front element. */
public int peek() {
    if (stack2.isEmpty()){			
        while (!stack1.isEmpty())
            stack2.push(stack1.pop());
    }
    return stack2.peek();	// stack2 is basically the queue, so return whatever's on the top
}

/** Returns whether the queue is empty. */
public boolean empty() {
    return stack1.isEmpty() && stack2.isEmpty();
}

Palindrome LinkedList

 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
36
public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null)		// Size 0 or 1 list, must be unique.
        return true;
    if (head.next.next == null)					// Size 2 list, compare the head and tail
        return head.val == head.next.val;		// values

    ListNode middleNode = head;					// Standard Rabbit-Tortoise pointers.
    ListNode fastPointer = head;				// Fast pointer jumps twice so by the time
												// it reaches the end of the list, middlenode
    ListNode curr = head;						// is at the middle of the linkedlist.
    ListNode prev = null;
    ListNode nextNode;							// These three nodes are for reversing the 
												// first half of the list
    while (fastPointer != null && fastPointer.next != null){
        middleNode = middleNode.next;			// Advance middle once, fastpointer twice
        fastPointer = fastPointer.next.next;

        nextNode = curr.next;					// Reverse the curr node, but first store the
        curr.next = prev;						// next newNode. By doing this, we would have
        prev = curr;							// reversed exactly half of the list because
        curr = nextNode;						// fastpointer advacnes at double the speed.
    }

    if (fastPointer != null)					// If faspointer isn't null, then we have an
        middleNode = middleNode.next;			// odd length list, so advance middle once,
												// List looks like 1->2->3->2->1 instead of
    while (middleNode != null){					// 1->2->3->3->2->1
        if (middleNode.val != prev.val)			// While middle isn't null, check middlenode
            return false;						// val and prev val. Prev is basically the
        middleNode = middleNode.next;			// the point where the list reverses.
        prev = prev.next;						// Advance middle and next.
    }
    return true;								// Values matched, so return true.
}												// Reversed list looks like this:
												// 1<-2<-3<-prev middle->3->2->1 in even len
												// 1<-2<-prev middle->2->1 in odd lengths.

Delete Node in a Linked List

1
2
3
4
public void deleteNode(ListNode node) {
    node.val = node.next.val;		// Node's value becomes its next node's value
    node.next = node.next.next;  	// Node's next is it's next's next.
}

Is Anagram

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length())			// Can't be anagram if size aren't the same
        return false;
    int[] store = new int[26];				// Acts like a hashmap
    for (int i = 0; i < s.length(); i++)	// Increment the count by 1 in the store for the
        store[s.charAt(i)-'a']++;			// index = position of char in the alphabet
    for (int i = 0; i < t.length(); i++){	// Loop throught the second string, decrement
        if (--store[t.charAt(i)-'a'] < 0)	// count of each character in store by 1, but if
            return false;					// it goes below 0, then it means that character
    }										// occurred more than it did in s. So false.
    return true;							// Everything matched, so return true.
}

Binary Tree Paths

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
List<String> paths = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
    if (root == null)					// No paths
        return paths;
    String rootval = root.val + "";		// Converting int to string.
    traverse(root, rootval);
    return paths;
}

private void traverse(TreeNode root, String s){
    if (root.left == null && root.right == null)		// It's a leaf, and you found a path
        paths.add(s);									// so add it to the list
    if (root.left != null)								// Left side is traversable, so
        traverse(root.left, s + "->" + root.left.val);	// visit it and record its value.
    if (root.right != null)								// Same as above, but for right side.
        traverse(root.right, s + "->" + root.right.val);
}

Add Digits

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private int constantTime(int n){
    if (n < 10)
        return n;			// Already a single digit
    int result = n % 9;
    if (result == 0)		// If perfectly divisible by 9, then sum will be 9.
        return 9;
    return result;			// Otherwise, the result is going to be n % 9.
}

private int iterative(int num){
    while (num > 9){				// While number isn't between 2-9
        num = sumOfDigits(num);		// make num = sum of it's digits.
    }
    return num;
}

private int sumOfDigits(int n){		// Standard method to add the digits of a number.
    int sum = 0;
    while (n != 0){
        sum += n % 10;				// Extract the last digit, add it to sum.
        n /= 10;					// Divide the num by 10.
    }
    return sum;
}

Largest Perimeter Triangle

1
2
3
4
5
6
7
8
public int largestPerimeter(int[] A) {
    Arrays.sort(A);							// Sort so the largest sides are at the end.
    for (int i = A.length-3; i >= 0; --i)	// Triangle inequality Theorem : a + b > c
        if (A[i] + A[i+1] > A[i+2])			// If sum of last two is greater than the last
            return A[i] + A[i+1] + A[i+2];	// we found out max perimeter, otherwise
    return 0;								// decrease i by i, then check the next three
}											// triplets
											// In the end if nothing works out, we return 0.

Ugly Number

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public boolean isUgly(int num) {
    if (num < 1)
        return false;		// Negative numbers are automatically non ugly
    while (num % 2 == 0)	// Keep dividing number by 2 till it is divisible
        num /= 2;
    while (num % 3 == 0)	// Keep dividing by 3
        num /= 3;
    while (num % 5 == 0)	// and 5
        num /= 5;
    return num == 1;		// If num isn't 1, that means that there are other prime factors
}							// except 2,3 and 5.

Missing Number

1
2
3
4
5
6
7
public int missingNumber(int[] nums) {			// Since it's given that the array contains
    int nsum = (nums.length*(nums.length+1))/2;	// all numbers from 0-n, we use the formula
    int arraySum = nums[0];						// to compute sum of n numbers.
    for (int i = 1; i < nums.length; i++)		// Then we loop through the array to compute
        arraySum += nums[i];					// the sum of the array.
    return nsum - arraySum;						// Subtract the array sum from the required
}												// sum, and that gives us the missing number

Is Bad Version

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public int firstBadVersion(int n) {		// Basic Binary Search Algorithm
    int low = 1, high = n;
    int mid;
    while (low < high){
        mid = low + (high - low)/2;		// high - low to prefent integer overflow.
        if (isBadVersion(mid))			// if the model at mid was bad version, then we
            high = mid;					// could possibly have a bad version before it
        else
            low = mid+1;				// If it wasn't, then our first bad version lies
    }									// beyond the middle element.
    return low;
}

Move Zeroes

 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
/*
The general idea is that we know the end of the array is going to contain zeroes. So first, iterate over the array, if you find any non-zero value, copy it down to the front of the array. Then we you are done, length of the array minus the last index where you copied the non-zero element is the number of zeroes you need to fill in. So iterate from that last non-zero index to the end of the array and fill in zeroes.
*/
public void moveZeroes(int[] nums) {
    int lastNonZeroIndex = 0;
    for (int i = 0; i < nums.length; i++)
        if (nums[i] != 0)
            nums[lastNonZeroIndex++] = nums[i];
    for (int i = lastNonZeroIndex; i < nums.length; i++)
        nums[i] = 0;
}

/*
This solution is an extension of the above, but a better one because we only swap elements when needed and do not do any unnecessary writes. Start from the beginning of the array, maintain the last position of non-zero value you saw, and the current element. If you see a non-zero value, swap the current value with the index just after the last non-zero index you have, and then increment the non-zero index by 1 because you just found a new non-zero value. This helps us prepare for the next non-zero value we find and copy it at this index+1. By doing so, we are basically partitioning the array into non-zeroes and zero values.
*/
public void moveZeroes(int[] nums) {
    for (int lastNonZeroIndex = 0, i = 0; i < nums.length; i++){
        if (nums[i] != 0)
            swap(nums, i , lastNonZeroIndex++);
    }
}

private void swap(int[] a, int i, int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

Word Pattern

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public boolean wordPattern(String pattern, String str) {
    String[] words = str.split(" ");		// Split str into words
    if (pattern.length() != words.length)	// If length of pattern and words mismatch
        return false;						// then pattern do not match
    HashMap<Character, String> patternStore = new HashMap<>();	// Map pattern char to word
    HashMap<String, Character> wordMap = new HashMap<>();		// Map word to pattern char
    for (int i = 0; i < words.length; i++){
        char c = pattern.charAt(i);					// Get the char
        patternStore.putIfAbsent(c, words[i]);		// Put it in patternStore if absent
        if (!patternStore.get(c).equals(words[i]))	// If it was already there and it doesn't
            return false;							// map to words[i], we have a violation
        wordMap.putIfAbsent(words[i], c);			// Now check the other way around. If
        if (wordMap.get(words[i]) != c)				// words is absent in the map, map it to
            return false;							// the char. If present, then fetch it's
    }												// mapping and check if both match to c.
    return true;							// No violation, so return true
}

Can Win Nim

1
2
3
public boolean canWinNim(int n) {
    return n % 4 != 0;			// You can always win the game if n is not divisible by 4.
}

Power Of Three

1
2
3
4
5
6
7
public boolean isPowerOfThree(int n) {
    if (n < 1)				// If negative, it can't be a power of 3.
        return false;
    while (n % 3 == 0)		// While n is divisible by 3, keep dividing it.
        n /= 3;
    return n == 1;			// In the end, if it was a power of 3, then n should be 1.
}

Power of Four

1
2
3
4
5
6
7
/*
You can also use the iterative method that I have used in Power of Two and Power of Three problems. I just wanted to try a different approach here. This is a constant time function.
*/
public boolean isPowerOfFour(int num) {
    double pow = Math.log(num)/Math.log(4);	// Calculate x in 4^x = num using logs.
    return pow == (int)pow;					// Making sure that x is an integer and not a
}											// fractional exponent.

Reverse String

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
1 Liner solution. Basically, create a StringBuilder of the string, the builder already has a reverse method, so reverse it and then return it's toString.
*/

public String reverseString(String s) {
    return new StringBuilder(s).reverse().toString();
}

/*
Golfing aside, here is how one is expected to solve it in an interview.
*/

public String reverseString(String s) {
	char[] array = s.toCharArray();		// Create a char array of the string
	int len = array.length;				// length of the array
	for (int i = 0; i < len/2; i++){	// We only need to iterate over half the array.
		char temp = array[i];			// Swap the 0th index element with (len-1)th,
		array[i] = array[len-i-1];		// 1st index element with (len-2)th, until you get
		array[len-i-1] = temp;			// to the middle element.
	}
	return new String(array);			// Return a new string with the reversed array.
}

Implement strStr()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/*
The basic idea here is that you only need to iterate haystack length - needle length, and then check the substring of size = needle length in haystack from each index. If you are successfully able to match each character of the needle in the corresponding substring in haystack, return the index you start from. 
*/
public int strStr(String haystack, String needle) {
    if (needle.length() > haystack.length())	// Needle length can't be > than haystack
        return -1;
    int hl = haystack.length();
    int nl = needle.length();
    if (nl == 0)								// Empty strings are always a match starting
        return 0;								// from 0.
    for (int i = 0; i <= hl-nl; i++){			// Iterate haystack length - needle length.
        for (int j = 0; j < nl && haystack.charAt(i+j) == needle.charAt(j); ++j)}
            if (j == nl-1)						// We are checking how far from i can we
                return i;						// match. If i matched with j, increment j
        }										// and then match the character i+1 to j.
    }											// If that matches, increment j and match i+2
    return -1;									// j == n-1 checked wether or not if we were
}												// able to match the full needle string, if
												// yes, then i is our index
												// in the end, nothing matched, so return -1

Reverse Vowels of a String

 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
36
37
38
39
40
public String reverseVowels(String s) {
    if (s.length() < 2)
        return s;					// No need to reverse a string of length 0 or 1
    char[] str = s.toCharArray();	// Get the char array

    int left = 0;
    int right = str.length-1;

    while (left < right){
        while (left < right && !isVowel(str[left]))		// While left is pointing to a
            left++;										// consonant, increment it/
        while (left < right && !isVowel(str[right]))	// While right is pointing to a
            right--;									// consonant, decrement it.

        char temp = str[left];							// Left and right are now pointing
        str[left] = str[right];							// to vowels, so swap it.
        str[right] = temp;								// And then increment left and
        left++;											// decrement right to process the
        right--;										// inner string
    }
    return new String(str);			// Return a string from the reveresed array.
}

private boolean isVowel(char c){	// Function to check if a character is a vowel.
    switch (c) {
        case 'a':
        case 'e':
        case 'i':
        case 'o':
        case 'u':
        case 'A':
        case 'E':
        case 'I':
        case 'O':
        case 'U':
            return true;
        default:
            return false;
    }
}

Intersection of two arrays

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<Integer>();		// Record all unique values in set 1
    for (int i: nums1)
        set1.add(i);
    Set<Integer> intersect = new HashSet<>();		// We will use it to record intersection
    for (int i: nums2)								// For each value in nums2 array
        if (set1.contains(i))						// If set1 contains it, we found an
            intersect.add(i);						// intersecting element, so add it.
    int[] res = new int[intersect.size()];			// We will now convert the set to an
    int i = 0;										// array and then return the array.
    for (int n: intersect)
        res[i++] = n;
    return res;
}

Is Perfect Square

 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
/**
The basic idea here is to close in on the square root using binary search algorithm. 
I handle 4 seperately because it's root is the only one where 4/3 < it's square root. 
All other numbers square root is greater than its value/3.
So we create a lowerBound of 1 and an upperBound of num/3. Then if the middle value's square
overshoots, we make upperBound = mid-1, otherwise increment lowerBound to mid+1. This way, we
close on the square root from both sides, and if the middle values is the square root, it's
square will yield num.
*/
public boolean isPerfectSquare(int num) {
    if (num < 2 || num == 4)
        return true;
    long lowerBound = 1;
    long upperBound = num/3;
    long mid;
    long square;
    while (lowerBound <= upperBound){
        mid = lowerBound + (upperBound-lowerBound)/2;
        square = mid*mid;
        if (square == num)
            return true;
        if (square > num)
            upperBound = mid-1;
        else
            lowerBound = mid+1;
    }
    return false;
}

Sum of Two Integers

I cannot explain it better than this post.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public int getSum(int a, int b) {
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    int sum = a ^ b;
    int carry = a & b;
    if (carry == 0)
        return sum;
    return getSum(sum, carry << 1);
}

Guess Number Higher or Lower

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public int guessNumber(int n) {				// Standard binary search algorithm
    int low = 1, high = n, result = -2;		// Arbitrary result, but not 0
    int mid = 0;
    while (result != 0){
        mid = low + (high-low)/2;			// Check the mid.
        result = guess(mid);				// Check if our guess is correct
        if (result == -1)					// If result == -1, then we overshot
            high = mid-1;					// So we can discard all values > mid
        else if (result == 1)				// If result == 1, we undershot
            low = mid+1;					// Need to discard all the values < mid
    }
    return mid;								// Result == 0, so return the mid.
}

Ransom Note

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public boolean canConstruct(String ransomNote, String magazine) {
    int[] store = new int[26];
    for (char c: magazine.toCharArray())		// First, fill the store with available
        store[c-'a']++;							// characters from the magazine
    for (char c: ransomNote.toCharArray())		// Then, scan through the note, decrement
        if (--store[c-'a'] < 0)					// each char's index by 1 because we used
            return false;						// it. If it's frequency drops below 0,
    return true;								// then it means that we need more chars
}												// than available. In the end, return
												// true if everything worked out.

First Unique Character in a String

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public int firstUniqChar(String s) {
    int[] freq = new int[26];			// Preprocess freq array to maintain freq of each
    char[] chars = s.toCharArray();		// character in the string s
    for (char c: chars)
        ++freq[c-'a'];
    for (int i = 0; i < chars.length; i++)	// Make a second pass through the chars of the
        if (freq[chars[i]-'a'] == 1)		// string in order, and if any of the char's
            return i;						// frequency is 1, that's our unique char
    return -1;								// Otherwise, no unique character
}

Find the Difference

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
The general idea here is same as the problem where we are required to find a unique int
in an array containing duplicates except one. We use the xor operator between each character
of the string s and t, and the ones that are duplicate will xor to give 0. XOR of any element
with 0 is the element itself, and XOR of two same elements gives 0. This way, since string s
and t basically has pairs of repeating characters except one, the unique element will XOR
with 0 and give us it's ASCII code. The only thing we need to take care of is to now shift it
up by 26, so we add 'a' and convert it to char.
*/
public char findTheDifference(String s, String t) {
    int xor = 0;
    for (char c: s.toCharArray())
        xor ^= c-'a';
    for (char c: t.toCharArray())
        xor ^= c-'a';
    return (char)(xor+'a');
}

Nth Digit

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
/**
Notice that # of digits between 0-9 is 1*9, 10-99 is 2*90, 100-999 is 3*900. If we generalize
it, it is exactly equal to 9 * (num of digits in the number) * 10^{# of digits - 1}.
*/
public int findNthDigit(int n) {
    if (n < 10)
        return n;
    int pow = 1;				// First we need to figure out how many digits there are
    long upperBound = 9;		// in the number.
    while (n > upperBound){
        n -= upperBound;		// If n is a two digit number, subtract the 9 single digit
        ++pow;					// numbers, if 3 digit, subtract the first 189 digits.
        upperBound = (long)Math.pow(10, pow-1) * pow * 9;
    }							// pow allows us to track how many digits there are in num.

    int num = (int)Math.pow(10,pow-1) + (n-1)/pow;		// Calculate which number we want
    int position = pow - 1 - (n-1) % pow;				// Calculate which index we want
    for (int i = 0; i < position; i++)					// Divide num that many times
        num /= 10;
    return num % 10;									// num % 10 gives us that digit.
}

Sum of Left Leaves

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public int sumOfLeftLeaves(TreeNode root) {
    if (root == null)		// Empty tree, therefore total is 0.
        return 0;
    int sum = 0;			// Initialize sum.
    // Look ahead and check. If left is not null but left is a leaf, then sum is the value of the left leaf.
    // But if left is null or left is an inner node, then we need to explore it, so sum is whatever the subtree from the left node returns.
    if (root.left != null && root.left.left == null && root.left.right == null)
        sum = root.left.val;
    else
        sum = sumOfLeftLeaves(root.left);
    // We computed the sum of the left side. Now we need to traverse the right side and fetch
    // the sum, so total sum is sum of the left side as computed above + sum returned by
    // traversing the right side.
    return sum + sumOfLeftLeaves(root.right);
}

Longest Palindrome

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int longestPalindrome(String s) {
    int[] freq = new int[128];		// To record the frequency of each char
    for (char c: s.toCharArray())
        freq[c]++;					// Increment count by 1 for each character observed
    int len = 0;					// length of the longest palindrome
    boolean isOdd = false;			// Check if our palindrome length is odd
    for (int i = 0; i < 128; i++){	// Go through each character's index
        if (freq[i] != 0){			// Only if it has been observed atleast once
            int val = freq[i];		// Store it's frequency
            int used;				// Record how many of it's occurrences we will use
            if (val % 2 == 0)		// If a perfect multiple of 2, we will use all
                used = val;
            else{
                used = val-1;		// If odd occurrences, then the max we can use to form a
                isOdd = true;		// valid palindrome is val-1. It also tells us that the
            }						// palindrome is going to be of odd length.
            len += used;			// Finally, increment length by the number of chars used
        }
    }
    if (isOdd)						// If length is odd, we can always insert any single
        return len+1;				// character in the middle to keep the palindrome valid.
    return len;						// If the length is even, then we can't do anything.
}

Fizz Buzz

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public List<String> fizzBuzz(int n) {
    List<String> nums = new ArrayList<String>();
    for (int i = 1; i <= n; ++i){				// Loop from 1 to n
        if (i % 15 == 0)						// If i divisible by 15, add "FizzBuzz"
            nums.add("FizzBuzz");
        else if (i % 5 == 0)					// i's not a multiple of 15, check if it's a
            nums.add("Buzz");					// multiple of 5. If so, add "Buzz"
        else if (i % 3 == 0)					// i's not a multiple of 5, check if it's a
            nums.add("Fizz");					// multiple of 3, if so, add "Fizz"
        else
            nums.add(i+"");						// Otherwise, just add the String type of the
    }											// number
    return nums;
}

Third maximum Number

 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
public int thirdMax(int[] nums) {
    if (nums.length == 0)		// Empty array
        return 0;
    if (nums.length == 1)		// Size 1 array
        return nums[0];
    if (nums.length == 2)		// Size 2 array, check between 0th element or 1st element
        return nums[0] > nums[1] ? nums[0] : nums[1];
    long firstMax = Long.MIN_VALUE;		// Lowest values for all three
    long secondMax = Long.MIN_VALUE;
    long thirdMax = Long.MIN_VALUE;
    for (int i: nums){					// For each number in the array
        if (i > firstMax){				// If num > than the largest, then old largest
            thirdMax = secondMax;		// becomes second largest and second largest becomes
            secondMax = firstMax;		// first largest, then update the largest.
            firstMax = i;
        }
        else if (i > secondMax && i != firstMax){	// If num > second and num is not is the
            thirdMax = secondMax;					// same as first, first largets becomes
            secondMax = i;							// second largest and update the second
        }
        else if (i > thirdMax && i != secondMax && i != firstMax) // // If num > third, we
            	thirdMax = i;						// need to check that it is not the same
    }												// as the first and second largest.
    if (thirdMax == Long.MIN_VALUE)					// This check allows us to make sure that
        return (int)firstMax;						// we do indeed have a third max and is
    return (int)thirdMax;							// not what we initialized initially.
}

Add Two Strings

 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
public String addStrings(String num1, String num2) {
    if (num1.equals("0"))
        return num2;
    if (num2.equals("0"))
        return num1;
    
    /** We use a char array to maintain the digit at each index. We want the array to be of
    the size of the largest string + 1 to handle carry bit if any at the end. We start
    adding each digit of the string from the end, and place it in it's correct index at the
    end of the sum array. This way, we avoid reversing it and return the answer in constant
    time. Take care to convert the digit you compute by adding '0'. Lastly, if the carry bit
    is 1, we need to make the 0th index as 1, and return the string by using the sum array.
    If it's not 1, then the sum array has a leading 0 which we don't want. So we use Java's
    String constructor that takes in the char array, startingIndex in that array and the
    number of elements of that array we want. So if the carry isn't 1, we technically want
    everything from index 1 and # of elements = sum.length - 1 because we discard 0 index.
    */
    char[] sum = new char[1 + Math.max(num1.length(), num2.length())];
    int index = sum.length-1, idx1 = num1.length()-1, idx2 = num2.length()-1, carry = 0, total = 0;
    int n1, n2;
    while (idx1 >= 0 || idx2 >= 0){
        n1 = idx1 < 0 ? 0 : num1.charAt(idx1--)-'0';
        n2 = idx2 < 0 ? 0 : num2.charAt(idx2--)-'0';
        total = n1 + n2 + carry;
        carry = total/10;
        sum[index--] = (char)(total % 10 + '0');
    }
    if (carry == 1){
        sum[0] = '1';
        return new String(sum);
    }
    return new String(sum, 1, sum.length-1);
}

Construct Quad Tree

 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
private int[][] grid;					// Store it once, instead of passing it over & over.
public Node construct(int[][] _grid) {
    grid = _grid;
    return helper(0,0,grid.length);		// Ask helper to build the tree.
}

private Node helper(int top, int left, int len){
    if (len <= 0)						// Base case: if empty grid or if we are done
        return null;					// checking the full grid, return null
    int key = grid[top][left];			// Get the topleft value, and start checking the box
    for (int i = 0; i < len; ++i){		// of len*len. If at any point, the value doesn't
        for (int j = 0; j < len; ++j){	// match the key, we have found a breakpoint from
            if (grid[top+i][left+j] != key){	// where we need to break the grid into four
                int offset = len/2;		// grids, each of len = len/