Leetcode - Unique Paths

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.

Solution #1: (Recursive, O(n^2), Time Limit Exceeded...)

// recursive
public class Solution {
    public int uniquePaths(int m, int n) {
        return backtrack(0, 0, m, n);
    }
    
    private int backtrack(int row, int col, int m, int n) {
        // to the target
        if(row == m - 1 && col == n - 1)
            return 1;
        // out of range
        if(row > m - 1 || col > n - 1)
            return 0;
            
        // move down + move right
        return backtrack(row + 1, col, m, n) + backtrack(row, col + 1, m, n);
    }
}

Solution #2: loop, O(n^2) space & time

// loop, similar as min path sum, O(n^2) time & space
public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] res = new int[m][n];
        
        // init left
        for(int i = 0; i < m; i++) {
            res[i][0] = 1;
        }
        // init top
        for(int j = 0; j < n; j++) {
            res[0][j] = 1;
        }
        
        // add values
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                res[i][j] = res[i - 1][j] + res[i][j - 1];
            }
        }
        
        return res[m - 1][n - 1];
    }
}

Solution #3: loop, O(n^2) time, O(n) space

// loop, similar as min path sum, O(n^2) time, O(n) space
public class Solution {
    public int uniquePaths(int m, int n) {
        int[] res = new int[n];
        
        // init array
        for(int j = 0; j < n; j++) {
            res[j] = 1;
        }
        
        // add values
        for(int i = 1; i < m; i++) {
            // reset the head to 1 (simulate the next row head)
            // similar to set all left most elements in a 2D array to 1
            res[0] = 1;
            for(int j = 1; j < n; j++) {
                res[j] = res[j - 1] + res[j];
            }
        }
        
        return res[n - 1];
    }
}

Many thanks to:
http://cuijing.org/interview/leetcode/summary-of-dynamic-programming-in-leetcode.html
&
http://yucoding.blogspot.com/2013/04/leetcode-question-116-unique-path-i.html

Leetcode - Minimum Path Sum

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Solution #1:

// DP, O(n^2) time, O(n^2) space
public class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        
        int[][] res = new int[row][col];
        // init
        res[0][0] = grid[0][0];
        
        // left
        for(int i = 1; i < row; i++) {
            res[i][0] = res[i - 1][0] + grid[i][0];
        }
        // top
        for(int j = 1; j < col; j++) {
            res[0][j] = res[0][j - 1] + grid[0][j];
        }
        
        // rest elements
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < col; j++) {
                res[i][j] = grid[i][j] + Math.min(res[i - 1][j], res[i][j - 1]);
            }
        }
        
        return res[row - 1][col - 1];
    }
}

Solution #2:

// DP, O(n^2) time, O(n) space
public class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        
        int[] res = new int[col];
        // init
        Arrays.fill(res, Integer.MAX_VALUE);
        res[0] = 0;
        
        // rest elements
        for(int i = 0; i < row; i++) {
            // init the 0th sum = old 0th element + the new 0th element
            // just init the 0th column every time dynamically
            res[0] = res[0] + grid[i][0];
            
            // loop through each element of each row
            for(int j = 1; j < col; j++) {
                res[j] = grid[i][j] + Math.min(res[j], res[j - 1]);
            }
        }
        
        return res[col - 1];
    }
}

Many thanks to: http://fisherlei.blogspot.com/2012/12/leetcode-minimum-path-sum.html

Leetcode - Maximum Subarray

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

click to show more practice.

More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 1. Solution #1, O(n)
Just simply loop from left to right and return the max val.

// O(n)
public class Solution {
    public int maxSubArray(int[] A) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        for(int i = 0; i < A.length; i++) {
            sum += A[i];
            maxSum = Math.max(maxSum, sum);
            // re-set sum when < 0 (no need to keep neg value)
            if(sum < 0) sum = 0;
        }
        return maxSum;
    }
}

2. Solution #2, Divide and conquer, O(n) also?
The max range can be in the left half, or in the right half, or across the mid of the array, so we just divide it to tree parts and recursive until we get the max value of each part, and then get the largest value.

// Devide and Conquer
public class Solution {
    public int maxSubArray(int[] A) {
        int maxSum = Integer.MIN_VALUE;
        return findMaxSub(A, 0, A.length - 1, maxSum);
    }
    
    // recursive to find max sum 
    // may appear on the left or right part, or across mid(from left to right)
    public int findMaxSub(int[] A, int left, int right, int maxSum) {
        if(left > right)    return Integer.MIN_VALUE;
        
        // get max sub sum from both left and right cases
        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 of this range (case: across mid)
        // so need to expend to both left and right using mid as center
        // mid -> left
        int sum = 0, midLeftMax = 0;
        for(int i = mid - 1; i >= left; i--) {
            sum += A[i];
            if(sum > midLeftMax)    midLeftMax = sum;
        }
        // mid -> right
        int midRightMax = 0; sum = 0;
        for(int i = mid + 1; i <= right; i++) {
            sum += A[i];
            if(sum > midRightMax)    midRightMax = sum;
        }
        
        // get the max value from the left, right and across mid
        maxSum = Math.max(maxSum, midLeftMax + midRightMax + A[mid]);
        
        return maxSum;
    }
}

Thanks to : http://fisherlei.blogspot.com/2012/12/leetcode-maximum-subarray.html

Leetcode - Rotate Image

Rotate Image

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?

public class Solution {
    public void rotate(int[][] matrix) {
        if(matrix == null)  return;
        int n = matrix.length;
        // n * n matrix
        //int w = matrix[0].length;
        if(n < 2) return;
        
        // rule: i = j'; j = n-1 - i';
        // that is: i' = n-1 -j; j' = i;
        // loop through 1/4 of the matrix
        // a | b
        // c | d
        // four parts
        // Math.ceil : returns the smallest integer >= a number.
        for(int i = 0; i < n/2; i++) {
            for(int j = 0; j < Math.ceil(((double)n)/2.0); j++) {
                int tmp = matrix[i][j];
                
                // c -> a
                matrix[i][j] = matrix[n-1 - j][i];
                // d -> c
                matrix[n-1 - j][i] = matrix[n-1 - i][n-1 - j];
                // b -> d
                matrix[n-1 - i][n-1 - j] = matrix[j][n-1 - i];
                // a -> b (tmp -> b)
                matrix[j][n-1 - i] = tmp;
            }
        }
    }
}

LeetCode - Sort Colors

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.

click to show follow up.

Follow up:
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?

Solution #1: (two-pass counting sort as the follow up says)

public class Solution {
    public void sortColors(int[] A) {
        if(A == null || A.length == 0 || A.length == 1)  return;
        
        int red = 0, white = 0, blue = 0;
        for(int i = 0; i < A.length; i++) {
            if(A[i] == 0)       red++;
            else if(A[i] == 1)  white++;
            else                blue++;
        }
        
        for(int i = 0; i < red; i++) 
            A[i] = 0;
        for(int i = red; i < red + white; i++)
            A[i] = 1;
        for(int i = red + white; i < A.length; i++)
            A[i] = 2;
    }
}

Solution #2: (one-pass solution)

public class Solution {
    public void sortColors(int[] A) {
        if(A == null || A.length == 0 || A.length == 1)  return;
        
        // one-pass solution
        int red = 0, blue = A.length - 1, tmp, i = 0;
        // stop looping when current >= blue
        while(i <= blue) {
            // if color is red, move to the front
            if(A[i] == 0) {
                // when cur > red, switch
                if(i > red) {
                    tmp = A[red];
                    A[red] = A[i];
                    A[i] = tmp;
                    red++;
                }
                // when cur <= red, no need to switch, just move both to next
                else {
                    i++;
                    red++;
                }
            }
            // if color is blue, move to the end
            else if(A[i] == 2) {
                // when cur < blue, switch
                if(i < blue) {
                    tmp = A[blue];
                    A[blue] = A[i];
                    A[i] = tmp;
                    blue--;
                }
                // when cur >= blue, end the loop
                else {
                    return;
                }
            }
            // if color is white, skip
            else {
                i++;
            }
        }
    }
}

Thanks to http://blog.unieagle.net/2012/10/23/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Asort-colors/

Leetcode - Candy

Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

public class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        if(len == 0 || len == 1)    return len;
        
        // start with every child already has one candy
        int min = len;
        int[] candies = new int[len];
        
        // scan from head + 1 to tail, compare each child with their next neighbos's rating
        int cur = 0;
        for(int i = 1; i < len; i++) {
            if(ratings[i - 1] < ratings[i])
                cur++;
            else
                cur = 0;
            candies[i] = cur;
        }
        
        // scan from tail - 1 to head, do the same process as above loop
        cur = 0;
        for(int i = len - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1])
                cur++;
            else
                cur = 0;
            // no need to store another candies array again, just compare each node and store the max 
            // (why max: candy num of this position should match with both left and right neighbors)
            min += Math.max(candies[i], cur);
        }
        
        // add the candy num of the tail position, since the loop for add a sum didn't cover that position
        min += candies[len - 1];
        
        return min;
    }
}

Many thanks to : http://blog.csdn.net/violet_program/article/details/12233949 

Leetcode - Merge Two Sorted Lists

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.

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null || l2 == null)    return l1 == null ? l2 : l1;
        
        // init
        ListNode head;
        if(l1.val < l2.val) {
            head = new ListNode(l1.val);
            l1 = l1.next;
        }
        else {
            head = new ListNode(l2.val);
            l2 = l2.next;
        }
        ListNode node = head;
        
        // loop
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                node.next = new ListNode(l1.val);
                node = node.next;
                l1 = l1.next;
            }
            else {
                node.next = new ListNode(l2.val);
                node = node.next;
                l2 = l2.next;
            }
        }
        
        while(l1 != null) {
            node.next = new ListNode(l1.val);
            node = node.next;
            l1 = l1.next;
        }
        
        while(l2 != null) {
            node.next = new ListNode(l2.val);
            node = node.next;
            l2 = l2.next;
        }
        
        return head;
    }
}

Leetcode - Remove Duplicates from Sorted List

Remove Duplicates from Sorted List

 

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)   return head;
        
        ListNode node = head;
        
        while(node != null) {
            ListNode tmp = node.next;
            while(tmp != null && node.val == tmp.val) {
                tmp = tmp.next;
            }
            node.next = tmp;
            node = node.next;
        }
        
        return head;
    }
}

Leetcode - Maximum Depth of Binary Tree

Wait to hear back from an onsite interview. May God Bless me!

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.

Solution:
1. Recursive:

/**
 * 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;
        
        return getDepth(root, 1);
    }
    
    public int getDepth(TreeNode node, int depth) {
        int left = depth, right = depth;
        if(node.left != null) left = getDepth(node.left, depth + 1);
        if(node.right != null) right = getDepth(node.right, depth + 1);
        
        return left > right ? left : right;
    }
}

2. Non-recursive:

/**
 * 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;
        
        // Non-recursive, use level order triversal
        ArrayList<TreeNode> q = new ArrayList<TreeNode>();
        q.add(root);
        int depth = 0;
        
        while(!q.isEmpty()) {
            ArrayList<TreeNode> next = new ArrayList<TreeNode>();
            for(TreeNode node : q) {
                if(node.left != null)   next.add(node.left);
                if(node.right != null)  next.add(node.right);
            }
            q = new ArrayList<TreeNode>(next);
            depth++;
        }
        
        return depth;
    }
}

! ? Leetcode - Recover Binary Search Tree

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

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

OJ's Binary Tree Serialization: The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode prev;
    
    public void recoverTree(TreeNode root) {
        if(root == null)    return;
        
        ArrayList<TreeNode> wrongList = new ArrayList<TreeNode>();
        prev = null;
        inOrder(root, wrongList);
        
        int tmp = wrongList.get(0).val;
        wrongList.get(0).val = wrongList.get(wrongList.size() - 1).val;
        wrongList.get(wrongList.size() - 1).val = tmp;

    }
    
    public void inOrder(TreeNode node, ArrayList<TreeNode> wrongList) {
        if(node == null)    return;
        
        inOrder(node.left, wrongList);
        
        // if found
        if(prev != null && prev.val > node.val) {
            if(!(wrongList.contains(prev))) wrongList.add(prev);
            if(!(wrongList.contains(node))) wrongList.add(node);
        }
        prev = node;
        
        inOrder(node.right, wrongList);
    }
}

Reference:
1. http://jane4532.blogspot.com/2013/07/recover-binary-search-treeleetcode.html
2. https://gist.github.com/guolinaileen/5125340

Leetcode - Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

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

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if(num == null || num.length == 0) return null;
        
        int start = 0, end = num.length - 1;

        TreeNode root = buildTree(num, start, end);
        
        return root;
    }
    
    public TreeNode buildTree(int[] num, int start, int end) {
        if(start > end) return null;
        
        int mid = (start + end) / 2;
        
        // build left sub tree
        TreeNode left = buildTree(num, start, mid - 1);
        // build root of the subtree
        TreeNode node = new TreeNode(num[mid]);
        node.left = left;
        // build right sub tree
        node.right = buildTree(num, mid + 1, end);
        
        return node;
    }
}

Leetcode - Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    static ListNode head;
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null)    return null;
        this.head = head;
        
        // get list length
        int len = 0;
        ListNode ln = head;
        while(ln != null){
            len++;
            ln = ln.next;
        }   
        
        return sortedListToBST(0, len - 1);
    }
    
    // build bottom-to-top
    public TreeNode sortedListToBST(int start, int end) {
        // if finished (root)
        if(start > end) return null;
        
        // get mid val
        int mid = (start + end) / 2;
        
        // build left sub tree
        TreeNode left = sortedListToBST(start, mid - 1);
        // build root node
        TreeNode root = new TreeNode(head.val);
        root.left = left;
        // move to next node to build right sub tree
        head = head.next;
        root.right = sortedListToBST(mid + 1, end);
        
        return root;
    }
}

Reference: http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

Java - implements vs. extends

extends is for extending a class.

implements is for implementing an interface

Example:

implements:

public interface ExampleInterface{
    public void do();
    public String doThis(int number);
 }

 public class sub implements ExampleInterface{
     public void do(){
       //specify what must happen
     }

     public String doThis(int number){
       //specfiy what must happen
     }
 }

extends:

public class SuperClass{
    public int getNb(){
         //specify what must happen
        return 1;
     }

     public int getNb2(){
         //specify what must happen
        return 2;
     }
 }

 public class SubClass extends SuperClass{
      //you can override the implementation
      @Override
      public int getNb2(){
        return 3;
     }
 }

result:

Subclass s = new SubClass();
  s.getNb(); //returns 1
  s.getNb2(); //returns 3

  SuperClass sup = new SuperClass();
  sup.getNb(); //returns 1
  sup.getNb2(); //returns 2

Reference: http://stackoverflow.com/questions/10839131/implement-vs-extends-when-to-use-whats-the-difference

Leetcode - Merge Intervals

Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<Interval>();
        
        if(intervals == null) return intervals;
        int len = intervals.size();
        if(len == 0 || len == 1)    return intervals;
        
        // sort the input by start value
        Collections.sort(intervals, new IntervalComparator());
        
        Interval a = intervals.get(0);
        for(int i = 1; i < len; i++) {
            Interval b = intervals.get(i);
            // if mergeable, merge a and b.
            if(a.end >= b.start) {
                a = new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end));
            }
            // if not mergeable, move to the next, reset the a node.
            else {
                res.add(a);
                a = b;
            }
        }
        res.add(a);
        return res;
        
    }
}

class IntervalComparator implements Comparator<interval>
{
    public int compare(Interval a, Interval b) {
        return a.start - b.start;
    }
}

About Array, ArrayList, LinkedList

Array:

1. Fixed length data structure, cannot change length once created

2. Cannot user Generics.

3. All kinds of Array provideslength variable which denotes length of Arra, array.length to get length

4. Allow both primitives and Objects. (int[], Object[])

5. You can simply use assignment operator to store element into Array. (int[] i = new int[10]; int[1] = 1;)

6. Must provide size when init.

ArrayList:

1. Dynamic length, however, re-size is slow (create a new array and copying content from old to new)

2. Allows to use Generics to ensure type safe.

3. All kinds of Array provideslength variable which denotes length of Arra, arraylist.size() to get size

4. Only allow Objects but not primitives. (ArrayList)

5. Java provides add() method to insert element into ArrayList.

6. Do not need to provide size when init.


--------------------------------------------------
ArrayList:
1. Index based data-structure. O(1) for search, get(index).

2. Add element, O(1) if doesn't trigger re-size of the array. O(log(n)) if re-size.

3. O(n) for remove and insert, need to re-arrange all elements.

4. Less memory overhead, because ArrayList each index only holds actual object (data).


LinkedList:

1. O(n) for search(get) element.

2. O(1) for add element.

3. For insert or remove element, still need O(n) to travers to that pointer (can traverse from either direction based upon proximity)

4. More memory overhead, because LinkedList each node holds both data and address of next and previous node.

Leetcode - Word Search

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

public class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || board[0].length == 0)
            return false;
            
        boolean res = false;
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(board[i][j] == word.charAt(0)) {
                    char[][] tmp = board;
                    tmp[i][j] = 0;
                    if(ifFound(tmp, i, j, word, 1)) return true;
                }
            }
        }
        
        return res;
    }
    
    public boolean ifFound(char[][] b, int i, int j, String s, int idx) {
        boolean res = false;
        if(idx == s.length()) return true;
        
        char c = s.charAt(idx);
        // top
        if(i- 1 >= 0 && b[i - 1][j] == c) {
            if(idx == s.length() - 1) return true;
            
            char[][] tmp = b;
            tmp[i - 1][j] = 0;
            if(ifFound(tmp, i - 1, j, s, idx + 1))  return true;
        }
        // bottom
        if(i + 1 < b.length && b[i + 1][j] == c) {
            if(idx == s.length() - 1) return true;
            
            char[][] tmp = b;
            tmp[i + 1][j] = 0;
            if(ifFound(tmp, i + 1, j, s, idx + 1))    return true;
        }
        // left
        if(j - 1 >= 0 && b[i][j - 1] == c) {
            if(idx == s.length() - 1) return true;
            
            char[][] tmp = b;
            tmp[i][j - 1] = 0;
            if(ifFound(tmp, i, j - 1, s, idx + 1))    return true;
        }
        // right
        if(j + 1 < b[0].length && b[i][j + 1] == c) {
            if(idx == s.length() - 1) return true;
            
            char[][] tmp = b;
            tmp[i][j + 1] = 0;
            if(ifFound(tmp, i, j + 1, s, idx + 1))    return true;
        }
        
        return res;
    }
}

Leetcode - Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL 

 /**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null)    return;
        
        ArrayList<TreeLinkNode> q = new ArrayList<TreeLinkNode>();
        
        q.add(root);
        
        while(!q.isEmpty()) {
            ArrayList<TreeLinkNode> next = new ArrayList<TreeLinkNode>();
            
            for(int i = 0; i < q.size(); i++) {
                TreeLinkNode node = q.get(i);
                if(node.left != null)   next.add(node.left);
                if(node.right != null)  next.add(node.right);
                
                if(i == q.size() - 1)   node.next = null;
                else    node.next = q.get(i + 1);
            }
            
            q = new ArrayList<TreeLinkNode>(next);
        }
    }
}

Leetcode - Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int res = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        if(root == null)    return 0;
        
        res = Integer.MIN_VALUE;
        
        getMaxSum(root);
        
        return res;
    }
    
    public int getMaxSum(TreeNode node) {
        if(node == null)    return 0;
        
        int left = getMaxSum(node.left);
        int right = getMaxSum(node.right);
        
        int thisSum = node.val;
        
        if(left > 0)    thisSum += left;
        if(right > 0)   thisSum += right;
        
        res = Math.max(res, thisSum);
        
        // only need return the largest subtree with this node val
        return node.val + Math.max(0, Math.max(left, right));
    }
}

First Post

solve one issue per day