Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

public class Solution {
    public boolean isPalindrome(String s) {
        if(s == null || s.trim().length() == 0){
            return true;
        }
        int i = 0;
        int j = s.length() - 1;
        while(i < j){
            while(i  i && !isAlphanumeric(s.charAt(j))){
                j--;
            }
            if(i >= j) {
                return true;
            }else {
                if (Character.toLowerCase(s.charAt(i)) == Character.toLowerCase(s.charAt(j))) {
                    i++;
                    j--;
                }else {
                    return false;
                }
                
            }
        }
        return true;
        
    }
    private boolean isAlphanumeric(char c){
        return (c >= 'a' && c = 'A' && c = '0' && c <= '9');
    }
}

Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, 
then the reverse of 1000000003 overflows. How should you handle such cases?

Throw an exception? Good, but what if throwing an exception is not an option? 
You would then have to re-design the function (ie, add an extra parameter).

public class Solution {
    public int reverse(int x) {
        int negative = (x  0){
            result = result * 10 + (x%10);
            x = x/10;
        }
        return result * negative;
    }
}

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

public class Solution {
    public int removeDuplicates(int[] A) {
        for (int i = 0, j = i + 1; i < A.length && j = 2) {
                    A[j] = Integer.MAX_VALUE;
                }
                j++;
            }
            else {
                i = j;
                j = i + 1;
            }
        }
        for (int i = 0, j = i + 1; i < A.length && j < A.length;){
            if(j < i){
                j = i + 1;
            }
            if (A[i] == Integer.MAX_VALUE){
                while(j < A.length && A[j] == Integer.MAX_VALUE){
                    j++;
                }
                if (j < A.length && A[j] != Integer.MAX_VALUE) {
                    A[i++] = A[j];
                    A[j] = Integer.MAX_VALUE;
                } else {
                    return i;
                }
            } else {
                i++;
            }
        }
        return A.length;
        
    }
}

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root 
node down to the farthest leaf node.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        int left = 0;
        if(root.left != null){
            left = maxDepth(root.left);
        }
        int right = 0;
        if(root.right != null){
            right = maxDepth(root.right);
        }
        return 1 + (left > right ? left : right);
    }
}

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each 
element appear only once and return the new length.

Do not allocate extra space for another array, you must do this 
in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

public class Solution {
    public static int removeDuplicates(int[] A) {
        int length = A.length;
        if(length <= 1) return length;
        int removed = 0;
        for (int i = 0, j = 1; i < length - 1 && j < length;){
            if(j <= i){
                j = i + 1;
            }
            if(A[i] == A[j]){
                A[j++] = Integer.MAX_VALUE;
                removed++;
            }
            else {
                i++;
            }
        }
        for (int i = 0, j = 0; i < length - removed; i++){
            if(j <= i){
                j = i + 1;
            }
            if(A[i] == Integer.MAX_VALUE){
                while(j < length && A[j] == Integer.MAX_VALUE){
                    j++;
                }
                if(j < length){
                    A[i] = A[j];
                    A[j] = Integer.MAX_VALUE;
                }
            }
        }
        return length - removed;
    }
}

n^2

public class Solution {
    public int removeDuplicates(int[] A) {
        int length = A.length;
        for (int i = 0; i < length -1; i++){
            if(A[i] == A[i+1]){
                int step = 0;
                for(int j = i + 1; j < length; j++){
                    if(A[i] == A[j]){
                        step++;
                    }else {
                        A[j-step] = A[j];
                    }
                }
                length -=step;
            }
        }
        return length;
    }
}

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

public class Solution {
    public int removeElement(int[] A, int elem) {
        int length = A.length;
        for(int i = 0; i < length; i++){
            if(A[i] == elem){
                if(i < length - 1)
                    A[i--] = A[--length];
                else
                    length--;
            }
        }
        return length;
    }
}

3Sum

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

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

public class Solution {
    public ArrayList<ArrayList> threeSum(int[] num) {
        ArrayList<ArrayList> resultSets = new ArrayList<ArrayList>();
        Arrays.sort(num);
        for(int i = 0; i  num[i-1]) {
                int sum = -num[i];
                int start = i + 1;
                int end = num.length - 1;
                while(start < end){
                    if(num[start] + num[end] == sum){
                        ArrayList match = new ArrayList();
                        match.add(num[i]);
                        match.add(num[start]);
                        match.add(num[end]);
                        resultSets.add(match);
                        start++;
                        end--;
                        while(start < end && num[start] == num[start-1]){
                            start++;
                        }
                        while(start < end && num[end] == num[end+1]){
                            end--;
                        }
                    }else if (num[start] + num[end] < sum) {
                        start++;
                    }else {
                        end--;
                    }
                }
                
            }
            
        }
        return resultSets;
    }
}

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For 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.
Try to do this in one pass.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) return head;
        ListNode t1 = head;
        int length = 0;
        while(t1 != null){
            length++;
            t1 = t1.next;
        }
        if (length - n < 0) return head;
        if (length - n == 0) return head.next;
        ListNode t2 = head.next;
        t1 = head;
        for(int index = 1; index < length - n; index++){
            t1 = t1.next;
            t2 = t2.next;
        }
        t1.next = t2.next;
        t2.next = null;
        t2 = null;
        return head;
    }
}

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths
where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList> pathSum(TreeNode root, int sum) {
        ArrayList path = new ArrayList();
        ArrayList<ArrayList> result = new ArrayList<ArrayList>();
        hasPathSum(root, sum, path, -1, result);
        return result;
    }

    private void hasPathSum(TreeNode root, int sum, ArrayList a, 
                           int index, ArrayList<ArrayList> result){
        if(root == null) return;
        a.add(root.val);
        index++;
        if (root.left == null && root.right == null){
            if(root.val == sum) {
                result.add(new ArrayList(a));
            }
            
        }
        if(root.left!=null){
            hasPathSum(root.left, sum - root.val, a, index, result);
        }
        if(root.right!=null){
            hasPathSum(root.right, sum - root.val, a, index, result);
        }
        a.remove(index--);
    }
}

Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path 
such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        if(root.left == null && root.right == null) {
            return root.val == sum;
        }
        boolean left = false;
        if(root.left != null){
            left = hasPathSum(root.left, sum - root.val);
        }
        boolean right = false;
        if(root.right != null){
            right = hasPathSum(root.right, sum - root.val);
        }
        return left || right;
        
    }
    
}