Copy List with Random Pointer LeetCode

Using hashmap is much easier to implement the code.
O(n) time complexity and O(n) space
First, get the regular linked list and put the node pair in the hashmap
Second, set each node with correct random pointer.
public RandomListNode copyRandomList(RandomListNode head) {
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode p = head;
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode q = dummy;
     
        while (p!=null) {
            q.next = new RandomListNode(p.label);
            map.put(p, q.next);
            p = p.next;
            q = q.next;
        }
        p = head;
        q = dummy;
        while (p != null) {
            q.next.random = map.get(p.random);
            p = p.next;
            q = q.next;
        }
        return dummy.next;
    }

Better solution with O(n) time complexity and O(1) space.
 public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode p = head;
        //copy the node in the list
        while (p != null) {
            RandomListNode next = p.next;
            RandomListNode copy = new RandomListNode(p.label);
            p.next = copy;
            copy.next = next;
            p = next;
        }
        //Set the random pointer correctly
        p = head;
        while (p != null) {
            p.next.random = (p.random != null) ? p.random.next : null;
            p = p.next.next;
        }
        //Reset the list to the original one
        p = head;
        RandomListNode headCopy = (p!=null) ? p.next : null;
        while (p != null) {
            RandomListNode copy = p.next;
            p.next = copy.next;
            p = p.next;
            copy.next = (p != null) ? p.next : null;
        }
        return headCopy;
     
    }

Compare Version Number LeetCode

Integer.valueOf("01") can handle conversion from string to integer.

public int compareVersion(String version1, String version2) {
        String[] version1Res = version1.split("\\.");
        String[] version2Res = version2.split("\\.");
        int idx = Math.max(version1Res.length, version2Res.length);
        int i=0;
        while (i < idx) {
            int c1 = i < version1Res.length ? Integer.valueOf(version1Res[i]):0;
            int c2 = i < version2Res.length ? Integer.valueOf(version2Res[i]):0;
            if (c1>c2) {
                return 1;
            } else if (c1<c2) {
                return -1;
            }
            i++;
        }
        return 0;
    }

Majority Element

Method 1: HashMap is always a quick solution for this kind of problems.

public int majorityElement(int[] num) {

        Map<Integer,Integer> hm = new HashMap<Integer, Integer>();

        for (int i=0; i<num.length; i++) {

            if (!hm.containsKey(num[i])) {

                hm.put(num[i], 1);

            } else {

                hm.put(num[i],hm.get(num[i])+1);

                if (hm.get(num[i]) > num.length/2) {

                    return num[i];

                }

            }

        }

        return num[0];

    }

Method 2: Bit Manipulation

It is similar to Single Number.

public int majorityElement(int[] num) {

        

        //Bit manipulation

        int[] countsPerBit = new int[32];

        int result = 0;

        for (int i=0; i<32; i++) {

            int count = 0;

            for (int j=0; j<num.length; j++) {

                if((num[j]>>i&1) ==1) {

                    count++;

                }

            }

            if (count > num.length/2) {

                result |= (1<<i);

            }

        }

        return result;

    }

Method 3: Moore Voting Algorithm

This is super cool.

public int majorityElement(int[] num) {

        

        //Moore voting algorithm

        int elem = 0;

        int count = 0;

        

        for (int i=0; i<num.length; i++) {

            if (count == 0) {

                elem = num[i];

                count = 1;

            } else {

                if (elem == num[i]) {

                    count++;

                } else {

                    count--;

                }

            }

        }

        return elem;

    }

Evaluate Reverse Polish Notation LeetCode

Use stack to contain all the values. When we get the operators, we pop up two values for operation.

It's easy. It has lots of follow up question.


public int evalRPN(String[] tokens) {
        if (tokens==null || tokens.length == 0) return 0;
        if (tokens.length == 1) return Integer.valueOf(tokens[0]);
       
        Stack<String> stack = new Stack<String>();
        String operators = "+-*/";
       
        for (int i=0; i<tokens.length; i++) {
            if (!operators.contains(tokens[i])) {
                stack.push(tokens[i]);
            } else {
                int a = Integer.valueOf(stack.pop());
                int b = Integer.valueOf(stack.pop());
               
                switch(tokens[i]) {
                    case "+" : stack.push(String.valueOf(a+b)); break;
                    case "-" : stack.push(String.valueOf(b-a)); break;
                    case "*" : stack.push(String.valueOf(a*b)); break;
                    case "/" : stack.push(String.valueOf(b/a)); break;
                }
            }
        }
        return Integer.valueOf(stack.pop());
    }

Intersection of Two LinkedList LeetCode (Important)

1. Find the length of each list
2. Scan from the same length of the short list in the longer list.

It should be O(n) time and O(1) space.
It is not easy for me :(

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
       
        //Get the length 0f List A
        int indexA = 0;
        ListNode tempA = headA;
        while (tempA != null) {
            tempA = tempA.next;
            indexA++;
        }
       
        //Get the length of List B
        int indexB = 0;
        ListNode tempB = headB;
        while (tempB != null) {
            tempB = tempB.next;
            indexB++;
        }
       
        //Two pointers
       
        ListNode longNode = (indexA > indexB) ? headA : headB;
        ListNode shortNode = (longNode == headA) ? headB : headA;
        int diff = Math.abs(indexA - indexB);
        while (diff > 0) {
            longNode = longNode.next;
            diff--;
        }
       
        while (longNode != null) {
            if (longNode.val == shortNode.val) {
                return longNode;
            }
            longNode = longNode.next;
            shortNode = shortNode.next;
        }
        return null;
    }

Search 2D Matrix LeetCode (Important)

Very good question.
It can come with lots of follow up.

Step Wise method. I prefer this method. Easy to implement and very good for a quick solution during the interview.

public boolean searchMatrix(int[][] matrix, int target) {
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        int row = 0;
        int col = matrix[0].length-1;
        if (matrix[0][0] > target || matrix[rowLen-1][colLen-1] < target) return false;
     
        while (row < rowLen && col >= 0) {
            if (matrix[row][col] > target) {
                col--;
            } else if (matrix[row][col] < target) {
                row++;
            } else {
                return true;
            }
        }
        return false;
    }

Binary Search on row and column.
public boolean searchMatrix(int[][] matrix, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int row = searchRow(matrix, 0, matrix.length, target);
        int result = Arrays.binarySearch(matrix[row], target);
        return result >= 0 ? true : false;
    }
 
    private int searchRow(int[][] matrix, int start, int end, int target) {
        int mid = (start + end)/2;
        if (start == mid) {
            return mid;
        }
        if (matrix[mid][0] <= target) {
            return searchRow(matrix, mid, end, target);
        } else {
            return searchRow(matrix, start, mid, target);
        }
    }

public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix==null || matrix.length==0 || matrix[0].length==0) return false;
        //Search the col
        int l=0;
        int r=matrix.length-1;
        while (l<=r) {
            int mid = (l+r)/2;
            if (matrix[mid][0] == target) return true;
            if (matrix[mid][0] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        int row = r;
        if (row < 0) return false;
        //Search the row
        l=0;
        r=matrix[0].length-1;
        while (l<=r) {
            int mid = (l+r)/2;
            if (matrix[row][mid] == target) return true;
            if (matrix[row][mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }

Sort Colors LeetCode

Two passes are easy to understand. Count and put all the numbers in.

public void sortColors(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (A == null || A.length == 0) return;
         int[] helper = new int[3];
         for (int i=0; i<A.length; i++) {
             helper[A[i]] ++;
         }
       
         int index = 0;
         for (int j=0; j<3; j++) {
             while (helper[j]-- > 0) {
                 A[index++] = j;
             }
         }
    }

OK. Let's make it better.
ONE Pass.
index0 and index1 are two pointer for the current location of 0 and 1.

public void sortColors(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       if (A==null||A.length==0) return;
       int ind0 = 0;
       int ind1 = 0;
       for (int i=0; i<A.length; i++) {
           if (A[i] == 0) {
               A[i] = 2;
               A[ind1++] = 1;
               A[ind0++] = 0;
           } else if (A[i] == 1) {
               A[i] = 2;
               A[ind1++] = 1;
           }
       }
    }

Find Minimum in Rotated Sorted Array II LeetCode

Always separate the array for three conditions.
Put equal condition individually.


 public int findMin(int[] num) {
        int l = 0;
        int r = num.length - 1;
        int min = num[0];
       
        while (l < r) {
            int m = (l+r)/2;
            if (num[l] < num[m]) {
                min = Math.min(num[l], min);
                l = m + 1;
            } else if (num[l] > num[m]) {
                min = Math.min(num[m], min);
                r = m - 1;
            } else {
                min = Math.min(num[m], min);
                l++;
            }
        }
        min = Math.min(num[r], min);
        min = Math.min(num[l], min);
        return min;
    }

Search in Rotated Sorted Array LeetCode II

Only One situation need to be done.
When A[L] == A[mid].

public boolean search(int[] A, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
         int L = 0;
       int R = A.length-1;
   
       while (L<=R) {
           int mid = (L+R)/2;
           if (A[mid] == target) return true;
       
           // Example: 4 5 6 7 8 9 1 2 3
           if (A[L] < A[mid]) {
               if (A[L]<=target && target < A[mid]) {
                   R = mid - 1;
               } else {
                   L = mid + 1;
               }
           }
           // Example: 8 9 1 2 3 4 5 6 7
           else if (A[L] > A[mid]) {
               if (A[mid] < target && target <= A[R]) {
                   L = mid + 1;
               } else {
                   R = mid - 1;
               }
           } else {
               L++;
           }
       }
       return false;
    }

Find Minimum in Rotate Array LeetCode

Search in Rotated sorted Array

中间值大于起始值，且起始值大于终止值

    public int findMin(int[] num) {
        int l = 0;
        int r = num.length - 1;
        int min = num[0];
        
        while (l < r) {
            int m = (l+r)/2;
            if (num[l] < num[m]) {
                min = Math.min(num[l], min);
                l = m + 1;
            } else if (num[l] > num[m]) {
                min = Math.min(num[m], min);
                r = m - 1;
            } else {
                min = Math.min(num[m], min);
                l++;
            }
        }
        min = Math.min(num[r], min);
        min = Math.min(num[l], min);
        return min;

    }

Better solution:

public int findMin(int[] num) {
        int l = 0;
        int r = num.length - 1;
        
        while (l < r) {
            int m = (l+r)/2;
//中间值大于起始值，且起始值大于终止值
            if (num[m] >= num[l] && num[l] > num[r]) {
                l = m + 1;
            } else {
                r = m;
            }
            
        }
        return num[l];

    }

Search in Rotated Sorted Array LeetCode

Binary search.
Two different cases:
3 4 5 6 7 8 9 1 2
8 9 1 2 3 4 5 6 7

Here is the solution:

public int search(int[] A, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       int L = 0;
       int R = A.length-1;
     
       while (L<=R) {
           int mid = (L+R)/2;
           if (A[mid] == target) return mid;
         
           // Example: 4 5 6 7 8 9 1 2 3
           if (A[L] <= A[mid]) {
               if (A[L]<=target && target < A[mid]) {
                   R = mid - 1;
               } else {
                   L = mid + 1;
               }
           }
           // Example: 8 9 1 2 3 4 5 6 7
           else {
               if (A[mid] < target && target <= A[R]) {
                   L = mid + 1;
               } else {
                   R = mid - 1;
               }
           }
       }
       return -1;
    }

Container with most water LeetCode

Two pointer. Same idea with TwoSum.

public int maxArea(int[] height) {
        int start = 0;
        int end = height.length - 1;
       
        int maxArea = 0;
        while (start < end) {
            maxArea = Math.max(maxArea, (end - start) * Math.min(height[start], height[end]));
            if (height[start] > height[end]) {
                end--;
            } else {
                start++;
            }
        }
        return maxArea;
    }

Clone Graph LeetCode

• A queue is used to do breath first traversal.
• a map is used to store the visited nodes. It is the map between original node and copied node.

It would be helpful if you draw a diagram and visualize the problem.

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
         if(node == null)
            return null;

        LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map =
                                   new HashMap<UndirectedGraphNode,UndirectedGraphNode>();

        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);

        queue.add(node);
        map.put(node, newNode);
       
        while (!queue.isEmpty()) {
            UndirectedGraphNode curr = queue.pop();
            List<UndirectedGraphNode> currNeighbors = curr.neighbors;
           
            for (UndirectedGraphNode ngn : currNeighbors) {
                if (!map.containsKey(ngn)) {
                    UndirectedGraphNode copy = new UndirectedGraphNode(ngn.label);
                    map.put(ngn, copy); //updating the mapping
                    map.get(curr).neighbors.add(copy); //updating the curr neighbors
                    queue.add(ngn); //updating the queue
                } else {
                    map.get(curr).neighbors.add(map.get(ngn)); //adding the node from clone graph to the curr's neighbor
                }
            }
        }
        return newNode;
    }

Remove duplicate from sorted list LeetCode

Check whether the duplicate is existing or not.
If so, prev.next = curr.next. If not, prev.next = curr;

 public ListNode deleteDuplicates(ListNode head) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (head == null) return null;
        ListNode dummy = new ListNode(-1);
        dummy.next =head;
        ListNode prev = dummy;
        ListNode curr = head;
       
        while (null != curr) {
            while (curr.next != null && prev.next.val == curr.next.val) {
                curr = curr.next;
            }
           
            if (prev.next == curr) {
                prev = curr;
            } else {
                prev.next = curr.next;
            }
            curr = curr.next;
        }
        return dummy.next;

    }

Gas Station LeetCode

Use two variables to get the index.
diff is checking whether the entire loop has enough gas for the cost.
remain is trying to find the best start location. If it is negative which means we could not start at any previously point. So we count it again from the next point.

public int canCompleteCircuit(int[] gas, int[] cost) {
        int index = -1;
        int diff = 0;
        int remain = 0;
       
        for (int i=0; i<gas.length; i++) {
            diff += gas[i] - cost[i];
            remain += gas[i] - cost[i];
            if (remain < 0) {
                index = i;
                remain = 0;
            }
        }
        return diff >= 0 ? index + 1: -1;
    }

Partition List LeetCode

Create two listnodes for each list.

 public ListNode partition(ListNode head, int x) {
        ListNode root = new ListNode(-1);
        ListNode pivot = new ListNode(x);
       
        ListNode before = root;
        ListNode after = pivot;
       
        ListNode curr = head;
       
        while (curr != null) {
            ListNode next = curr.next;
            if (curr.val < x) {
                before.next = curr;
                before = curr;
            } else {
                after.next = curr;
                after = curr;
                after.next = null;
            }
            curr = next;
        }
        before.next = pivot.next;
        return root.next;
    }

LeetCode Reverse Words in a String

After splitting, there may be some " " string in the string array.
For example "a    b", the splitting result is "a", " ", "b".

public String reverseWords(String s) {
        if (s==null ||s.length()==0) return "";
   
    //split to words by space
    String[] arr = s.trim().split(" ");
    StringBuilder sb = new StringBuilder();
    for (int i=arr.length-1; i >=0; i--) {
       if (!"".equals(arr[i])) {
    sb.append(arr[i]).append(" ");
       }
    }
    return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
    }


Also there is a alternative solution for two passes and O(1) space.
The condition is there no spaces at the beginning and the tail. Every word is separated by single space.

Algorithm.
Reverse entire sentence.
Reverse every word.

LeetCode Gray Code

第n位的格雷码由两部分构成，一部分是n-1位格雷码，再加上 1<<(n-1)和n-1位格雷码的逆序的和
public List<Integer> grayCode(int n) {
        if (n==0) {
            List<Integer> result = new ArrayList<Integer>();
            result.add(0);
            return result;
        }
       
        List<Integer> prevList = grayCode(n-1);
        int highestBit = 1 << (n-1);
        List<Integer> result = new ArrayList<Integer>(prevList);
        for (int i=prevList.size() - 1; i>=0; i--) {
            result.add(highestBit + prevList.get(i));
        }
        return result;
    }

LeetCode SubSetsII

Add one variable to add duplicate number in the lists.

public List<List<Integer>> subsetsWithDup(int[] num) {

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        result.add(new ArrayList<Integer>());

        Arrays.sort(num);

        

        int startIndex = 0;

        for (int i=0; i<num.length; i++) {

            int size = result.size();

            for (int j = startIndex; j < size; j++) {

                List<Integer> sub = new ArrayList<Integer>();

                sub.addAll(result.get(j));

                sub.add(num[i]);

                result.add(sub);

            }

            if (i<num.length-1 && num[i+1] == num[i]) {

                startIndex = size;

            } else {

                startIndex = 0;

            }

        }

        return result;

    }

Reverse Linked List II LeetCode

Find the start and end node for reversing.


public ListNode reverseBetween(ListNode head, int m, int n) {
      ListNode dummy = new ListNode(-1);
      dummy.next = head;
      ListNode temp = dummy;
     
      int index = 1;
      while (index < m) {
          temp = temp.next;
          index++;
      }
      ListNode prev = temp;
      ListNode newHead = temp.next;
      while (index <= n) {
          temp = temp.next;
          index++;
      }
      ListNode end = temp.next;
      prev.next = reverse(newHead, end);
      return dummy.next;
    }
   
    private ListNode reverse(ListNode head, ListNode end) {
        if (head == null || head.next == null) return head;
        ListNode prev = new ListNode(-1);
        prev.next = head;
        ListNode curr = head;
        while (curr.next != end) {
            ListNode temp = curr.next;
            curr.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
        return prev.next;
    }

Unique Binary Search Trees II LeetCode

Recursion could simplify the code significantly.
The returning result is all the root node of each Tree.

public List<TreeNode> generateTrees(int n) {
        return generateTrees(1,n);
    }
    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> result = new ArrayList<TreeNode>();
       
        if (start > end) {
            result.add(null);
            return result;
        }
        for (int i=start; i<=end; i++) {
            for (TreeNode left : generateTrees(start, i-1)) {
                for (TreeNode right : generateTrees(i+1, end)) {
                    TreeNode curr = new TreeNode(i);
                    curr.left = left;
                    curr.right = right;
                    result.add(curr);
                }
            }
        }
        return result;
    }

Maximum

DP
but we only need two variables to store the maxvalue and minvalue

public int maxProduct(int[] A) {
        if (A.length == 1) return A[0];
        int maxProduct = A[0];
        int currMax = A[0];
        int currMin = A[0];
       
        for (int i=1; i<A.length; i++) {
            int temp = currMax;
            currMax = Math.max(Math.max(temp*A[i], A[i]), currMin*A[i]);
            currMin = Math.min(Math.min(currMin*A[i], A[i]), temp*A[i]);
            maxProduct = Math.max(maxProduct, currMax);
        }
        return maxProduct;
    }

Word Break LeetCode

dp
dp[j] = dp[i] && dict.contains(s.substring(j,i))

public boolean wordBreak(String s, Set<String> dict) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
       
        for (int i=1; i<=s.length();i++) {
            for (int j=0; j<i; j++) {
                if (dp[j] && dict.contains(s.substring(j,i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

Construct Binary Tree from preOrder and inOrder Leetcode

Similarly, copy the solution from postOrder and inOrder.

public TreeNode buildTree(int[] preorder, int[] inorder) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(preorder == null || inorder == null) return null;
        if(preorder.length == 0 || inorder.length == 0) return null;
        return build (preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}

        public TreeNode build(int[] preorder, int start1, int end1, int[] inorder, int start2,
int end2) {
        if(start1 > end1 || start2 > end2) return null;
int current = preorder[start1];
TreeNode currRoot = new TreeNode(current);
        int k = start2;
        for(; k < inorder.length; k++)
        if(inorder[k] == current) break;
        currRoot.left = build(preorder, start1+1, start1-start2+k, inorder, start2, k-1);
        currRoot.right = build(preorder, start1-start2+k+1,end1, inorder, k+1, end2);
        return currRoot;
    }

Construct Binary Tree from Inorder and PostOrder LeetCode

The last element from postOrder is the root value.

Find the last element from inOrder, Will get the length of subTrees.

public TreeNode buildTree(int[] inorder, int[] postorder) {

        if (inorder == null || postorder == null) return null;

        if (inorder.length == 0 || postorder.length == 0) return null;

        return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);

}

private TreeNode buildTree(int[] inorder, int start1, int end1, int[] postorder, int start2, int end2) {

   if (start1 > end1 || start2 > end2) return null;

   int currentValue = postorder[end2];

   TreeNode currRoot = new TreeNode(currentValue);

   int k = start1;

   for (; k < inorder.length; k++) {

       if (inorder[k] == currentValue) break;

   }

   currRoot.left = buildTree(inorder, start1, k-1, postorder, start2, end2-end1+k-1);

   currRoot.right = buildTree(inorder, k+1, end1, postorder, end2-end1+k, end2-1);

   return currRoot;

}

Convert Sort List to Binary Search Tree LeetCode

The start position for fast and slow should be set carefully.

public TreeNode sortedListToBST(ListNode head) {

        if (head == null) return null;

        if (head.next == null) return new TreeNode(head.val);

        

        ListNode fast = head.next.next;

        ListNode slow = head;

        while (fast != null && fast.next != null) {

            fast = fast.next.next;

            slow = slow.next;

        }

        ListNode parent = slow.next;

        slow.next = null;

        TreeNode root = new TreeNode(parent.val);

        root.left = sortedListToBST(head);

        root.right = sortedListToBST(parent.next);

        

        return root;

    }

Here is a better solution. (Bottom-up)

From the CleanCodeHandbook of LeetCode.
public class Solution {
    private ListNode list;
    public TreeNode sortedListToBST(ListNode head) {
        int n = 0;
        ListNode p = head;
        while (p!=null) {
            p = p.next;
            n++;
        }
        list = head;
        return sortedListToBST(0, n-1);
    }
   
    private TreeNode sortedListToBST(int start, int end) {
        if (start > end) return null;
        int mid = (start + end)/2;
        TreeNode leftChild = sortedListToBST(start, mid-1);
        TreeNode parent = new TreeNode(list.val);
        parent.left = leftChild;
        list = list.next;
        TreeNode rightChild= sortedListToBST(mid+1, end);
        parent.right = rightChild;
        return parent;
       
    }
}

ReOrder List LeetCode

Good implementing question for LinkedList.

public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode reverseHead = slow.next;
        slow.next = null;
       
        reverseHead = reverse(reverseHead);
        ListNode curr = head;
        while (reverseHead != null) {
            ListNode temp = reverseHead.next;
            reverseHead.next = curr.next;
            curr.next = reverseHead;
            curr = reverseHead.next;
            reverseHead = temp;
        }
    }
   
    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode prev = new ListNode(-1);
        prev.next = head;
        ListNode curr = head;
        while (curr.next != null) {
            ListNode temp = curr.next;
            curr.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
        return prev.next;
    }

Binary Tree Zigzag Level Order Traversal LeetCode

Use two stacks to store the node for different directions.

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        if (root == null) return result;
        else {
            List<Integer> curr = new ArrayList<Integer>();
            curr.add(root.val);
            result.add(curr);
            if (root.left != null)
            s1.push(root.left);
            if (root.right != null)
            s1.push(root.right);
            helper(result, s1, s2);
            return result;
        }
    }
   
    private void helper(List<List<Integer>> result, Stack<TreeNode> s1, Stack<TreeNode> s2) {
        if (s1.empty() && s2.empty()) return;
        List<Integer> tempList = new ArrayList<Integer>();
        TreeNode tempNode = null;
        if (!s1.empty()) {
            while (!s1.empty()) {
                tempNode = s1.pop();
                tempList.add(tempNode.val);
                if (tempNode.right != null) {
                    s2.push(tempNode.right);
                }
                if (tempNode.left != null) {
                    s2.push(tempNode.left);
                }
            }
        } else {
            while (!s2.empty()) {
                tempNode = s2.pop();
                tempList.add(tempNode.val);
                if (tempNode.left != null) {
                    s1.push(tempNode.left);
                }
                if (tempNode.right != null) {
                    s1.push(tempNode.right);
                }
            }
        }
        result.add(tempList);
        helper(result, s1, s2);
        return;
    }

Flatten Binary Tree to LinkedList LeetCode

Recursion

public TreeNode lastNode = null;
    public void flatten(TreeNode root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
       if (root == null) return;
       if (lastNode != null) {
           lastNode.left = null;
           lastNode.right = root;
       }
     
       TreeNode left = root.left;
       TreeNode right = root.right;
       lastNode = root;
       flatten(left);
       flatten(right);
    }

Path Sum II LeetCode

public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) return result;
        if (root.left == null && root.right == null && sum == root.val) {
            List<Integer> curr = new ArrayList<Integer>();
            curr.add(root.val);
            result.add(curr);
            return result;
        }
        if (root.left != null) {
            List<List<Integer>> leftResults = pathSum(root.left, sum - root.val);
            for (int j=0; j<leftResults.size();j++) {
                List<Integer> curr = new ArrayList<Integer>();
                curr.add(root.val);
                curr.addAll(leftResults.get(j));
                result.add(curr);
            }
        }
        if (root.right != null) {
            List<List<Integer>> rightResults = pathSum(root.right, sum - root.val);
            for (int j=0; j<rightResults.size();j++) {
                List<Integer> curr = new ArrayList<Integer>();
                curr.add(root.val);
                curr.addAll(rightResults.get(j));
                result.add(curr);
            }
        }
        return result;
    }

Add Two Numbers LeetCode

Recursion method is quite simple.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return helper(l1,l2,0);
    }
    private ListNode helper(ListNode l1, ListNode l2, int carry) {
        if (l1==null && l2==null && carry == 0) return null;
        int sum = 0;
        if (l1 != null) {
            carry += l1.val;
            l1=l1.next;
        }
        if (l2 != null) {
            carry += l2.val;
            l2=l2.next;
        }
        ListNode curr = new ListNode(carry%10);
        carry = carry/10;
        curr.next = helper(l1,l2,carry);
        return curr;
    }

Triangle LeetCode

Bottom-up!
 public int minimumTotal(List<List<Integer>> triangle) {
        for(int i = triangle.size() - 2; i >= 0; i--){
            for(int j = 0; j < triangle.get(i).size(); j++){
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
            }
        }
        return triangle.get(0).get(0);
    }

Valid Sudoku LeetCode

public boolean isValidSudoku(char[][] board) {

   

   //check the column

   for (int i=0; i<board[0].length; i++) {

       boolean[] dupCheck  = new boolean[256];

       for (int j=0; j<board.length; j++) {

           if (board[j][i] != '.') {

               if (dupCheck[board[j][i]] == true) return false;

               else dupCheck[board[j][i]] = true;

           }

       }

   }

   

   //check the row

   for (int i=0; i<board.length; i++) {

       boolean[] dupCheck = new boolean[256];

       for (int j=0; j<board[0].length; j++) {

           if (board[i][j] != '.') {

              if (dupCheck[board[i][j]] == true) return false;

               else dupCheck[board[i][j]] = true;

           }

       }

   }

   

   //check the subBox

   for (int i=0; i <board.length/3; i++) {

       for (int j=0; j <board[0].length/3; j++) {

           boolean[] dupCheck = new boolean[256];

           for (int m=i*3; m<i*3+3; m++) {

               for (int n=j*3; n<j*3+3; n++) {

                   if (board[m][n] != '.') {

                       if (dupCheck[board[m][n]] == true) return false;

                       else dupCheck[board[m][n]] = true;

                   }

               }

           }

       }

   }

   

   return true;

}

Length of Last Word LeetCode

public int lengthOfLastWord(String s) {
        if (s== null || s.length()==0) return 0;
        int end = s.length()-1;
        while (end >=0 && s.charAt(end) == ' ') {
            end--;
        }
        int start = end;
        while (start >=0 && s.charAt(start) != ' ') {
            start--;
        }
        return end-start;
    }

    public int lengthOfLastWord(String s) {
        if (s==null ||s.length()==0) return 0;
        int end = s.length()-1;
        //Scan from the last character and skip all the whitespace
        while (end>=0 && Character.isWhitespace(s.charAt(end))) {
            end--;
        }
       
        //Already scan all the string return 0
        int start = end;
        while (start>=0 && !Character.isWhitespace(s.charAt(start))) {
            start--;
        }
        return end - start;
    }

Plus One LeetCode

Try to add 1 for the lowest digit and return.

There is a corner condition like 999.

So if all the digits are 0, we will create a new integer array to store the result.

public int[] plusOne(int[] digits) {

        int index = digits.length-1;

        while (index >= 0) {

            if (digits[index] != 9) {

                digits[index]++;

                return digits;

            } else {

                digits[index--] = 0;

            }

        }

        int[] result = new int[digits.length+1];

        result[0] = 1;

        for (int i=1; i<result.length; i++) {

            result[i]=0;

        }

        return result;

    }

LeetCode CountAndSay

public String countAndSay(int n) {
        if (n==0) return "";
        if (n==1) return "1";
        String lastResult = countAndSay(n-1);
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<lastResult.length();) {
            char currChar = lastResult.charAt(i);
            int count = 0;
           
            while(i<lastResult.length() && currChar == lastResult.charAt(i)) {
                count++;
                i++;
            }
            sb.append(count).append(currChar);
        }
        return sb.toString();
    }

Minimum Depth of Binary Tree LeetCode

Recursion:
public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return 1;
        }
        else if (root.left != null && root.right != null) {
            return 1+Math.min(minDepth(root.left), minDepth(root.right));
        }
        else if (root.left == null && root.right != null) {
            return 1+minDepth(root.right);
        } else {
        return 1+minDepth(root.left);
        }
    }

Non-Recursion:
Why we use this method. Sometimes the tree is not balanced. This way will save lots of time. The worst of time complexity is O(n).
public int minDepth(TreeNode root) {
        if (root == null) return 0;
     
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> intQueue = new LinkedList<Integer>();
        nodeQueue.add(root);
        intQueue.add(1);
     
        while (!nodeQueue.isEmpty()) {
            TreeNode currNode = nodeQueue.poll();
            int currDepth = intQueue.poll();
         
            if (currNode.left != null) {
                nodeQueue.add(currNode.left);
                intQueue.add(currDepth+1);
            }
            if (currNode.right != null) {
                nodeQueue.add(currNode.right);
                intQueue.add(currDepth+1);
            }
            if (currNode.right == null && currNode.left == null) {
                return currDepth;
            }
        }
        return -1;//Should never reach here.
    }

Path Sum LeetCode

Recursion:
public boolean hasPathSum(TreeNode root, int sum) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (root == null) return false;
        if (root.left == null && root.right == null && sum == root.val) {
            return true;
        } else {
            return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
        }
       
    }

Non-recursion:
public boolean hasPathSum(TreeNode root, int sum) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       if (root==null) return false;
     
       Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
       Queue<Integer> intQueue = new LinkedList<Integer>();
       nodeQueue.add(root);
       intQueue.add(root.val);
     
       while (!nodeQueue.isEmpty()) {
           TreeNode currNode = nodeQueue.poll();
           int currVal = intQueue.poll();
         
           if (currNode.left == null && currNode.right == null && sum == currVal) {
               return true;
           }
           if (currNode.left != null) {
               nodeQueue.add(currNode.left);
               intQueue.add(currVal + currNode.left.val);
           }
           if (currNode.right != null) {
               nodeQueue.add(currNode.right);
               intQueue.add(currVal + currNode.right.val);
           }
       }
       return false;
     
    }

Pascal's Triangle LeetCode

Check Pascal's Triangle


public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (numRows < 1) return result;
        if (numRows == 1) {
            List<Integer> currList = new ArrayList<Integer>();
            currList.add(1);
            result.add(currList);
            return result;
        }
       
        List<List<Integer>> lastResult = generate(numRows-1);
        result.addAll(lastResult);
        List<Integer> lastList = lastResult.get(lastResult.size() - 1);
        List<Integer> newList = new ArrayList<Integer>();
        newList.add(1);
        for (int i=0; i<lastList.size()-1; i++) {
            newList.add(lastList.get(i) + lastList.get(i+1));
        }
        newList.add(1);
        result.add(newList);
        return result;
    }

Pascal's Triangle II Leetcode

Trivial solution without considering space
 public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>();
        if (rowIndex == 0) {
            result.add(1);
            return result;
        }
       
        List<Integer> currList = getRow(rowIndex - 1);
        List<Integer> newList = new ArrayList<Integer>();
        newList.add(1);
        for (int i = 0; i < currList.size() - 1; i++) {
            newList.add(currList.get(i) + currList.get(i+1));
        }
        newList.add(1);
        return newList;
    }

Consider about the space.
Collections.nCopies(n,0) is a smart way to initialize the arraylist as zero.

public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>(Collections.nCopies(rowIndex+1,0));
       
        result.set(0,1);
        for (int i=0; i<=rowIndex; i++) {
            result.set(i,1);
            for (int j=i-1; j>0; j--) {
                result.set(j, result.get(j)+result.get(j-1));
            }
        }
        return result;
    }

Symmetric Tree LeetCode

Recursively:

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

Iteratively:

public boolean isSymmetric(TreeNode root) {
       if (root == null || root.left == null && root.right == null) return true;
     
       Queue<TreeNode> lq = new LinkedList<TreeNode>();
       Queue<TreeNode> rq = new LinkedList<TreeNode>();
       lq.add(root.left);
       rq.add(root.right);
       TreeNode leftTreeNode = null;
       TreeNode rightTreeNode = null;
     
       while (lq.isEmpty() == false && rq.isEmpty() == false) {
           leftTreeNode = lq.poll();
           rightTreeNode = rq.poll();
         
           if (leftTreeNode == null && rightTreeNode == null) {
               continue;
           }
           if ((leftTreeNode == null && rightTreeNode != null )|| (leftTreeNode != null && rightTreeNode == null)) {
               return false;
           }
           if (leftTreeNode.val != rightTreeNode.val) {
               return false;
           }
         
           lq.add(leftTreeNode.left);
           lq.add(leftTreeNode.right);
         
           rq.add(rightTreeNode.right);
           rq.add(rightTreeNode.left);
         
       }
       return (lq.isEmpty()&&rq.isEmpty());
    }

LeetCode Maximum Subarray

General solution.
public int maxSubArray(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       int runningSum = 0;
       int totalSum = A[0];
       for (int i = 0; i < A.length; i++) {
           runningSum += A[i];
           if (runningSum > 0) {
               totalSum = Math.max(runningSum, totalSum);
           } else {
               totalSum = Math.max(totalSum, A[i]);
               runningSum = 0;
           }
       }
       return totalSum;
    }

DP
Memory optimization
public int maxSubArray(int[] A) {
        int maxEndingHere = A[0], maxSoFar = A[0];
        for (int i=1; i<A.length; i++) {
            maxEndingHere = Math.max(maxEndingHere + A[i], A[i]);
            maxSoFar = Math.max(maxEndingHere, maxSoFar);
        }
        return maxSoFar;
    }


D&C
Implement the binary search everywhere.
public int maxSubArray(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       int maxSum = Integer.MIN_VALUE;
       return findMaxSub(A, 0, A.length - 1, maxSum);
    }
 
    //Recursive to find max sum
    //may appear on the left, right or crossing the mid point
    private int findMaxSub(int[] A, int left, int right, int maxSum) {
        if (left > right) return Integer.MIN_VALUE;
     
        //Get Max sub by recursive ways
        int mid = (left + right)/2;
        int leftMax = findMaxSub(A, left, mid-1, maxSum);
        int rightMax = findMaxSub(A, mid+1, right, maxSum);
        maxSum = Math.max(maxSum, Math.max(leftMax, rightMax));
     
        //GEt Max sum by crossing mid
        int lSum = 0;
        int midLeftMax = 0;
        for (int i = mid-1; i>=left; i--) {
            lSum = lSum + A[i];
            if (lSum > midLeftMax) midLeftMax = lSum;
        }
     
        int rSum = 0;
        int midRightMax = 0;
        for (int i = mid+1; i<=right; i++) {
            rSum = rSum + A[i];
            if (rSum > midRightMax) midRightMax = rSum;
        }
        maxSum = Math.max(maxSum, midLeftMax + midRightMax + A[mid]);
        return maxSum;
    }

LeetCode PostOrder Traversal

Divided each each tree node process into 3 cases (according to the traversal path we drew previously):

2.1. Previous node from current node's parent 

2.1.1. if current node has left child, process left subtree.

2.1.2. if current node has no left child but right child, process right subtree. (current child has both left child and right is the case of 2.1.1. <- keep processing the left subtree)

2.1.3. if current has no left or right child (leaf), add the value of current tree node to result set and remove this node from stack, which means this node has been processed.

2.2. Previous node from current node's left child (left subtree has been processed)

2.2.1. if there the current node has right child, process the right subtree.

2.2.2. if no right child, add value of current node into result set and remove it from stack (current node processed).

2.3. Previous node from current node's right child (both left subtree and right subtree has been processed). <- add current node into result set and remove it from stack (current node processed).

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        TreeNode prev = null;
       
        while (!stack.empty()) {
            TreeNode curr = stack.peek();
           
            //from root or parent
            if (prev == null || prev.left == curr || prev.right == curr) {
                if (curr.left != null) stack.push(curr.left);
                else if (curr.right != null) stack.push(curr.right);
                else {
                    stack.pop();
                    result.add(curr.val);
                }
            }
            //from the left child
            else if (curr.left == prev) {
                if (curr.right != null) stack.push(curr.right);
                else {
                    stack.pop();
                    result.add(curr.val);
                }
            }
            //from the right child
            else if (curr.right == prev) {
                stack.pop();
                result.add(curr.val);
            }
            prev = curr;
        }
        return result;
    }

Leetcode Climbing Stairs

One dimension DP.

public int climbStairs(int n) {
        int[] steps = new int[n+1];
        steps[0] = 1;
        steps[1] = 1;
        for (int i=2; i<=n; i++) {
            steps[i] = steps[i-1] + steps[i-2];
        }
        return steps[n];
    }

Leecode Search Insert Position

O(logn) Binary Search

 public int searchInsert(int[] A, int target) {
        if (A == null) return 0;
        return searchInsert(A,target, 0, A.length-1);
    }
    private int searchInsert(int[] A, int target, int start, int end) {
        int mid = (start+end)/2;
        if (target == A[mid]) {
            return mid;
        } else if (target < A[mid]) {
            return start < mid ? searchInsert(A, target, start, mid-1) : start;
        } else {
            return end > mid ? searchInsert(A, target, mid+1, end) : (end + 1);
        }
       
    }