# Leetcode: Generate Parentheses

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

For example, given n = 3, a solution set is:

`"((()))", "(()())", "(())()", "()(())", "()()()"`

```public class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<String>();
if(n>0){
generateParenthesis("", n, n, result);
}
return result;
}

public void generateParenthesis(String prefix, int left, int right, List<String> result){
if(left>right){
return;
}
if(left==0){
for(int i=0;i<right;i++){
prefix+=")";
}
return;
}
if(left<right){
generateParenthesis(prefix+")", left, right-1, result);
}
generateParenthesis(prefix+"(", left-1, right, result);
}
}```

Note: The key point of this problem is when generating parentheses, the number of left parentheses being used so far is always larger than the number of right parentheses. In the algorithm. left and right means # of parentheses not being used so far.

Share

# Leetcode: Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Version 1. Initialize first row and first column separately

```    public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
int[][] f = new int[m][n];
//initialize the first column
for (int i = 0; i < m; i++) {
f[i][0] = 1;
}
//initialize the first row
for (int j = 0; j < n; j++) {
f[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}```

Version 2. Put initialization in the 2 for loop.

```public class Solution {
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
int[][] pathMap = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
pathMap[i][j] = 1;
} else if (pathMap[i][j] == 0) {
pathMap[i][j] = pathMap[i - 1][j] + pathMap[i][j - 1];
}
}
}
return pathMap[m - 1][n - 1];
}
}```

# Leetcode: Pascal’s Triangle

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

```[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]```
```public class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> pascalTriangle = new ArrayList<List<Integer>>();
List<Integer> currLevel = new ArrayList<Integer>();
while(numRows>0){
currLevel = generateNextLevel(currLevel);
numRows--;
}
return pascalTriangle;
}

public List<Integer> generateNextLevel(List<Integer> currLevel){
List<Integer> nextLevel = new ArrayList<Integer>();
if(currLevel.size()!=0){
for(int runner=0; runner<currLevel.size()-1; runner++){
}
}
return nextLevel;
}
}```

Note: for each row, pretend there is always one 0 at each side of the row. So the triangle would look like following, so when calculating next level, just need to sum each adjacent integers in the current level.

```[
0[1]0,
0[1,1]0,
0[1,2,1]0,
0[1,3,3,1]0,
0[1,4,6,4,1]0
]```

# Leetcode: Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

```public class Solution {
public int[] plusOne(int[] digits) {
if(digits==null||digits.length==0){
return digits;
}
int index = digits.length-1;
int carry = 1;
int sum;
while(index>=0 && carry==1){
sum = digits[index]+carry;
digits[index] = sum%10;
carry = sum/10;
index--;
}
if(carry==1){
int[] newDigits = new int[digits.length+1];
newDigits[0]=carry;
for(int i=0;i<digits.length;i++){
newDigits[i+1] = digits[i];
}
return newDigits;
}
return digits;

}
}```

Note: use a while loop here so that we don’t need to go through the entire array if it’s not necessary. It starts from the last index of the array and go backwards. If carry==1, then it will keep going, otherwise it will stop. After the traversing is done, it checks if the first digit==0 and handle that case.

# Leetcode: Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

Could you come up with an one-pass algorithm using only constant space?

One pass version:

```public class Solution {
public void sortColors(int[] A) {
int red = 0;
int blue = A.length-1;
int runner = 0;
while(runner<=blue){
switch(A[runner]){
case 0:
swap(A, red, runner);
red++;
runner++;
break;
case 1:
runner++;
break;
case 2:
swap(A, blue, runner);
blue--;
break;
}
}
}

public void swap(int[] A, int a, int b){
int temp = A[a];
A[a] = A[b];
A[b] = temp;
}
}```

# Leetcode: Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and respectively.

```public class Solution {
public void merge(int A[], int m, int B[], int n) {
int index = m+n-1;
while(index>=0 && m>0 && n>0){
if(A[m-1]>=B[n-1]){
A[index]=A[m-1];
m--;
}else{
A[index]=B[n-1];
n--;
}
index--;
}
if(n>0){
for(int i=0;i<n;i++){
A[i]=B[i];
}
}
}
}```

# Leetcode: Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

```    1
/ \
2   2
/ \ / \
3  4 4  3
```

But the following is not:

```    1
/ \
2   2
\   \
3    3
```

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what `"{1,#,2,3}"` means? > read more on how binary tree is serialized on OJ.

Recursive:

```public class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return isSymmetric(root.left, root.right);
}

public boolean isSymmetric(TreeNode left, TreeNode right){
if(left==null&&right==null){
return true;
}
if((left==null&&right!=null)||(left!=null&right==null)){
return false;
}
return left.val==right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}
}```

Non-Recursive/Iteratively:

# Leetcode: Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

```public class Solution {
public TreeNode sortedArrayToBST(int[] num) {
return sortedArrayToBST(num, 0, num.length-1);
}

public TreeNode sortedArrayToBST(int[] num, int start, int end){
if(start>end){
return null;
}
int pivot = (start+end)/2;
TreeNode root = new TreeNode(num[pivot]);
root.left = sortedArrayToBST(num, start, pivot-1);
root.right = sortedArrayToBST(num, pivot+1, end);
return root;
}
}```

# Leetcode: Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

```public class Solution {
public boolean isBalanced(TreeNode root) {
return getRebalancedHeight(root)==-1?false:true;
}
//getHeight for each node, -1 if it is already not balanced.
public int getRebalancedHeight(TreeNode root){
if(root==null){
return 0;
}
int leftHeight = getRebalancedHeight(root.left);
int rightHeight = getRebalancedHeight(root.right);
if(leftHeight==-1||rightHeight==-1||Math.abs(leftHeight-rightHeight)>1){
return -1;
}
return Math.max(leftHeight, rightHeight)+1;
}
}
```

# Leetcode: Valid Number

Validate if a given string is numeric.

Some examples:
`"0"` => `true`
`" 0.1 "` => `true`
`"abc"` => `false`
`"1 a"` => `false`
`"2e10"` => `true`

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

```public boolean isNumber(String s) {
// Start typing your Java solution below
// DO NOT write main() function
if(s==null||s.length()==0){
return false;
}
//continuous zeros from beginning since begin is true
int cont = 0;
boolean hasDot = false;
boolean begin = false;
boolean end = false;
boolean hasSign = false;
boolean hasE = false;

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

if(c=='+'||c=='-'){
if(hasSign||begin){
return false;
}else{
hasSign = true;
}
continue;
}

if(c=='e'){
if(hasE||!begin){
return false;
}else{
return isInteger(s.substring(i+1));
//return true;
}
}

if(c=='.'){
if(hasDot||end){
return false;
}else{
hasDot = true;
}
continue;
}

if(c==' '){
if((begin ||hasSign) && !end){
end=true;
}
continue;
}

if(!(isDigit(s,i))){
return false;
}else{
if(end){
return false;
}else{
if(!begin){
begin=true;
}
}
}

}

if(!begin){
return false;
}
return true;

}
public boolean isInteger(String s){
if(s==null||s.length()==0){
return false;
}
if(s.length()==1 && isDigit(s,0)){
return true;
}
char c = s.charAt(0);
if(c=='0'){
return ifAllSpace(s.substring(1));
}
int zeors = 0;
for(int i=0;i<s.length();i++){
if(i==0){
if(c=='+'||c=='-'){
return isIntegerWithoutSign(s.substring(i+1));
}else
if(!isDigit(s,i)){
return false;
}
}else
if(!isDigit(s,i)){
if(c==' '){
return ifAllSpace(s.substring(i+1));
}else{
return false;
}
}
}
return true;
}

public boolean ifAllSpace(String s){
for(int i=0;i<s.length();i++){
if(s.charAt(i)!=' '){
return false;
}
}
return true;
}

public boolean isIntegerWithoutSign(String s){
if(s==null||s.length()==0){
return false;
}
if(s.length()==1 && isDigit(s,0)){
return true;
}
char c = s.charAt(0);
if(c=='0'){
return false;
}
for(int i=0;i<s.length();i++){
if(!isDigit(s,i)){
if(c==' '){
return ifAllSpace(s.substring(i));
}else{
return false;
}
}
}
return true;
}

public boolean isDigit(String s,int index){
char c = s.charAt(index);
if(c<(int)'0' || c>(int)'9'){
return false;
}
return true;
}```