Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Solution:
1. find target row: O(m)
2. binary search that row: O(log n)
3. O(m+log n) time.
Improvement: treat it as an one dimensional array, and then use binary search

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowNum = findRow(matrix, target);
        if(rowNum >= matrix.length) return false;
        return binarySearch(matrix[rowNum], target, 0, matrix[0].length-1);
    }
    public Boolean binarySearch(int[] array, int target, int first, int last){
        if(first > last) return false;
        int mid = (first + last) / 2;
        if(array[mid] == target) return true;
        return (binarySearch(array, target, first, mid-1) || binarySearch(array, target, mid+1, last));
    }
    public int findRow(int[][] matrix, int target){
        int row = 0;
        while(!(target>=matrix[row][0] && target<=matrix[row][matrix[0].length-1])){
            row++;
            if(row >= matrix.length) break;
        }
        return row;
    }
}

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Solution:
Write out some text with different nRows on a piece of paper, then we can find out the relation between index and result row number.

public class Solution {
    public String convert(String s, int nRows) {
        int curRow = -1;
        
        // going down flag
        boolean flag = true;
        
        // its default value is "null"
        String[] strs = new String[nRows];
        Arrays.fill(strs, "");
        for(int i = 0; i < s.length(); i++){
            if(flag) 
                curRow++;
            // check a special case: ("AB", 1)
            else if (curRow > 0) 
                curRow--;
                
            if(curRow == nRows-1) 
                flag = false;
            else if(curRow == 0)
                flag = true;
                
            strs[curRow] += s.charAt(i);
        }
        
        // StringBuilder has better performance
        StringBuilder result = new StringBuilder();
        for(int i = 0; i < nRows; i++)
            result.append(strs[i]);
        return result.toString();
    }
}

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.

Solution:
Use DFS for each board position.

public class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        
        // to avoid duplicates
        boolean[][] visited = new boolean[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == word.charAt(0))
                    if(helper(board, word, 0, i, j, visited))
                        return true;
            }
        }
        return false;
    }
    
    public boolean helper(char[][] board, String word, int count, int i, int j, boolean[][] visited){
        if(count == word.length())
            return true;
        // out of boundary
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) 
            return false;
        if(visited[i][j] || board[i][j] != word.charAt(count))
            return false;
            
        visited[i][j] = true;
        
        if(helper(board, word, count+1, i-1, j, visited) || 
           helper(board, word, count+1, i+1, j, visited) ||
           helper(board, word, count+1, i, j-1, visited) ||
           helper(board, word, count+1, i, j+1, visited))
                return true;
        
        visited[i][j] = false;
        
        return false;
    }
}

Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

// bfs(queue) + dfs(HashMap> prevMap), 
 ///////////////////////////////////////////////////////////// 
///////// backtrack the paths is tricky /////////// 
//////////////////////////////////////////////////////////////

public class Solution {
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();

        // build up a tree from breath first search.
        HashMap<String, Integer> level = new HashMap<String, Integer>();
        Queue<String> queue = new LinkedList<String>();

        // a word and all its parent nodes in the bfs tree.
        HashMap<String, HashSet<String>> prevMap = new HashMap<String, HashSet<String>>();
        
        if(start == null || end == null || start.length() != end.length()) return ret;
        
        queue.add(start);
        level.put(start,1);
        prevMap.put(start, new HashSet<String>());
        
        int minLen = Integer.MAX_VALUE;
        while(!queue.isEmpty()){
            String curStr = queue.poll();
            int curLevel = level.get(curStr);
            for(int i = 0; i < curStr.length(); i++){
                char[] c = curStr.toCharArray();
                for(char j = 'a'; j <= 'z'; j++){

                    // change one letter, and check if it is in the dict
                    c[i] = j;
                    String tmp = String.valueOf(c);
                    if(tmp.equals(curStr)) continue;
                    if(dict.contains(tmp) && (!level.containsKey(tmp) 
                                           || (level.containsKey(tmp) && level.get(tmp) > curLevel))){
                        
                        if(prevMap.containsKey(tmp)){
                            prevMap.get(tmp).add(curStr);
                        }
                        else{
                            prevMap.put(tmp, new HashSet<String>());
                            prevMap.get(tmp).add(curStr);
                            queue.add(tmp);
                            level.put(tmp, curLevel+1);
                        }        
                    }
                    
                    if(tmp.equals(end)){
                        // the first reaches here would have the shortest path length.
                        if(level.get(curStr) < minLen){
                            ArrayList<String> path = new ArrayList<String>();
                            path.add(end);   // start from the second last level!!! otherwise, we will get duplicates.
                            ret.addAll(traceback(curStr, prevMap, path));    // e.g. [hot,hog,dog],[hot,dot,dog]
                            minLen = curLevel+1;                             // if we start from dog, the result will be:
                        }                                                    //[hot,hog,dog], [hot,hog,dog],[hot,dot,dog]
                        else break;
                    }
                    
                }
            }
        }
        return ret;
    }
    // different from permutation
    public ArrayList<ArrayList<String>> traceback(String end, HashMap<String, HashSet<String>> prevMap, ArrayList<String> path){
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); 
        ArrayList<String> newPath = new ArrayList<String>(path);
        newPath.add(0, end);
        if(prevMap.get(end).size() == 0){
            result.add(newPath);
            return result;
        }
        for(String tmp : prevMap.get(end)){
            result.addAll(traceback(tmp, prevMap, newPath)); 
        }
        return result;
    }
    
}

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Solution:
BFS.

public class Solution {
    public int ladderLength(String start, String end, HashSet dict) {
        if(dict.size() == 0) return 0;
        return bfs(start, end, dict);
    }
    public int bfs(String start, String end, HashSet dict){
           Queue queue = new LinkedList();
           Queue len = new LinkedList();
           queue.add(start);
           len.add(1);
           while(!queue.isEmpty()){
               String word = queue.poll();
               int length = len.poll();
               if(word.equals(end)) return length;
               for(int i = 0; i < word.length(); i++){ // for each word, check each letter at each position
                   char[] c = word.toCharArray();
                   for(int j = 'a'; j <= 'z'; j++){
                       if(j == c[i]) continue;
                       c[i] = (char)(j);
                       String str = String.valueOf(c);
                       if(dict.contains(str)){
                           queue.add(str);
                           len.add(length+1);
                           dict.remove(str);
                       }
                   }
               }
           }
           return 0;
    }
}

Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Solution:
dfs + word break 1 = Time Limit Exceeded, died at "aaaaaaaaaaaaaaaaaaaaaaaaa..." 
improvement: only save routes, start from the end.

public class Solution {
    public ArrayList wordBreak(String s, Set dict) {
        ArrayList> dp = new ArrayList>();   
        for(int i = 0; i <= s.length(); i++){
            dp.add(new ArrayList());
        }
        ArrayList ret = new ArrayList();
        for(int i = 0; i < s.length(); i++){
            if(i > 0 && dp.get(i) == null) continue; // dp.get(i).size() == 0;
            for(String tmp : dict){
                int end = i + tmp.length();
                if(end > s.length()) continue;
                String str = s.substring(i, end);
                if(str.equals(tmp)){
                    dp.get(end).add(i);
                }
            }
        }
        StringBuilder strb = new StringBuilder();
        helper(s, dp, ret, strb, s.length(), 0);
        return ret;
    }
    public void helper(String s, ArrayList> dp, ArrayList ret, StringBuilder strb, int cur, int step){
        if(cur == 0){
            ret.add(strb.toString());
            return;
        }
        
        for(int i : dp.get(cur)){
            if(step > 0) strb.insert(0, " ");
            strb.insert(0, s.substring(i, cur));
            helper(s, dp, ret, strb, i, step + 1);
            strb.delete(0, cur-i);
            if(step > 0) strb.delete(0, 1);
        }
    }
}

Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Solution:
first try: split s... 
second try: iterate dict & recursion -> Time Limit Exceeded 
third try: dp: dp[i] donates 0...i can be segmented. bottom-up. 

// bottom up!!!!!!!!!!!!!!!!!!!!!!
public class Solution {
    public boolean wordBreak(String s, Set dict) {
        int n = s.length();
        
        // dp[n] donates substring 0...n can be segmented or not
        boolean[] dp = new boolean[n];
        Arrays.fill(dp,false);
        
        for(int i = 0; i < n; i++){
            if(i > 0 && !dp[i-1])
                continue;
            for(String str : dict){
                int len = str.length();
                if ((i + len - 1) < n && s.substring(i,i+len).equals(str))
                    dp[i+len-1] = true;
            }    
        }
        
        return dp[n-1];
    }
}

Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

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

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

// case: abcdfbcd, a*bcd, we need to back track to star_s.

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char* star_p=0;
        const char* star_s=s; 
        while (*s){
            if ((*p=='?')||(*p==*s)){s++;p++;continue;}
            if (*p=='*'){star_p = p; star_s = s; p++; continue;}
            if (star_p){ p = star_p + 1; star_s++; s = star_s; continue;}
            return false;
        }
        while (*p == '*'){p++;}
        return !*p;
    }
};

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

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

Solution:
Use value range. Return false if a root value is not within the range.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);    
    }
    public boolean helper(TreeNode root, int min, int max){
        if(root == null) return true;
        if(root.val <= min || root.val >= max) return false;
        return (helper(root.left, min, root.val) && helper(root.right, root.val, max));
    }
}

Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Solution:
Trivial implementation question.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        //check rows
        for(int i = 0; i < 9; i++){
            int[] a = new int[10];
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.') continue;
                a[board[i][j] - '0']++;
                if(a[board[i][j] - '0'] > 1) return false;
            }
        }
        //check cols
        for(int j = 0; j < 9; j++){
            int[] a = new int[10];
            for(int i = 0; i < 9; i++){
                if(board[i][j] == '.') continue;
                a[board[i][j] - '0']++;
                if(a[board[i][j] - '0'] > 1) return false;
            }
        }
        //check sub-boxes
        for(int startRow = 0; startRow <= 6; startRow+=3){
            for(int startCol = 0; startCol <= 6; startCol+=3){
                int[] a = new int[10];
                for(int i = startRow; i < startRow+3; i++){
                    for(int j = startCol; j < startCol+3; j++){
                        if(board[i][j] == '.') continue;
                        a[board[i][j] - '0']++;
                        if(a[board[i][j] - '0'] > 1) return false;
                    }
                }
            }
        }
        return true;
    }
}

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Solution:
When met brackets questions, stack-based solution seems to be a good choice.

public class Solution {
    public boolean isValid(String s) {
        if(s.length() == 0 || s.length() % 2 != 0) return false;
        Stack stack = new Stack();
        for(int i = 0; i < s.length(); i++){
            int cur = getIndex(s.charAt(i));
            if(cur == getIndex('(') || cur == getIndex('[') || cur == getIndex('{')) {
                stack.push(cur);
            }
            else{
                if(stack.isEmpty()) return false;
                int out = stack.pop();
                if (cur - out != 1) return false; //doesn't match
            }
        }
        if(stack.isEmpty()) return true; 
        else return false;
    }
    public int getIndex(char c){
        char[] symbols = {'(',')','[',']','{','}'};
        for(int i = 0; i < symbols.length; i++){
            if(symbols[i] == c) return i;
        }
        return -1;
    }
}

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.

Solution:
Basic implementation question. 

public class Solution {
    public boolean isPalindrome(String s) {
        // empty string
        if(s.length() == 0)    
            return true;
        int l = 0;
        int r = s.length() - 1;
        while(l < r){
            
            // bypass non-alphanumeric characters
            while(!isChar(s.charAt(l)) && l < r) l++;
            while(!isChar(s.charAt(r)) && l < r) r--;
            
            // case: Aa and aa, 00, ...
            char x = s.charAt(l);
            char y = s.charAt(r);
            if(Math.abs(x - y) != 32 && Math.abs(x - y) != 0)
                return false;
            l++;
            r--;
        }
        return true;
    }
    public boolean isChar(char c){
        return (c >= 'a' && c <= 'z') || 
               (c >= 'A' && c <= 'Z') ||
               (c >= '0' && c <= '9');    
    }
}

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.

Solution:
This question can be solved easily using regular expression. 

public class Solution {
    
    public boolean isNumber(String s) {
        if(s.trim().isEmpty())  // trim: remove spaces at the heading and trailing
            return false;
        String regex = "[+-]?((\\d+\\.?\\d*)|(\\.\\d+))(e[+-]?\\d+)?";
        if(s.trim().matches(regex))
            return true;
        else
            return false;
    }
}

Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

Solution:
basic 2-d dynamic programming + conditions check

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int rowNum = obstacleGrid.length;
        int colNum = obstacleGrid[0].length;
        if((rowNum == 0 && colNum == 0) || (obstacleGrid[0][0] == 1)) return 0;
        int[][] result = new int[rowNum][colNum];
        for(int i = 0; i < rowNum; i++){
            for(int j = 0; j < colNum; j++){
                if(obstacleGrid[i][j] == 1) {result[i][j]=0;continue;}
                if(i == 0 && j == 0) result[i][j] = 1;
                else if(i == 0){
                    result[i][j] = obstacleGrid[i][j-1] == 0 ? result[i][j-1] : 0;
                }
                else if(j == 0){
                    result[i][j] = obstacleGrid[i-1][j] == 0 ? result[i-1][j] : 0;
                }
                else{
                    result[i][j] = 0;
                    result[i][j] +=  obstacleGrid[i][j-1] == 0 ? result[i][j-1] : 0;
                    result[i][j] +=  obstacleGrid[i-1][j] == 0 ? result[i-1][j] : 0; 
                }
            }
        }
        return result[rowNum-1][colNum-1];
    }
}

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: Very basic 2-d dynamic programming.

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

Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

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

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

Solution:
If it asks us to list all possibilities, use DFS in most cases.
DFS in the code is tricky. 

 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; left = null; right = null; }
 * }
 */
public class Solution {
    public ArrayList<treenode> generateTrees(int n) {
        return helper(1,n);
    }
    public ArrayList<treenode> helper(int begin, int end){
        ArrayList<treenode> ret = new ArrayList<treenode>();
        if(begin > end){
            ret.add(null);
            return ret;
        }
        for(int i = begin; i <= end; i++){                 // for all roots
            ArrayList<treenode> left = helper(begin, i-1); //generate left subtree
            ArrayList<treenode> right = helper(i+1, end);  //generate right subtree
            for(TreeNode l : left){
                for(TreeNode r : right){
                   TreeNode tmp = new TreeNode(i);
                   tmp.left = l;
                   tmp.right = r;
                   ret.add(tmp);
                }
            }
        }
        return ret;
    }
}

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

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

Solution:
1-d dynamic programming.

public class Solution {
    public static int numTrees(int n) { 
        int[] sum = new int[n+1];
        sum[0] = 1;
        sum[1] = 1;
        for(int i = 2; i <= n; i++){
            sum[i] = 0;
            for(int j=1; j<=i; j++){
                int leftSum = j-1;
                int rightSum = i-j;
                sum[i] += (sum[leftSum] * sum[rightSum]);
            }
        }
        return sum[n];
    }
}

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Solution:
Brute-force: use an array list to record all paths' sum, and update it level by level. 

//  bottom-up!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

public class Solution {
    public int minimumTotal(ArrayList> triangle) {
        int n = triangle.size();
        int[] total = new int[n];
        
        // assign last row elements to total
        for(int i = 0; i < n; i++)
            total[i] = triangle.get(n-1).get(i);
            
        // bottom-up left-right
        for(int i = n-2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                total[j] = triangle.get(i).get(j) + Math.min(total[j], total[j+1]);
            }
        }
        
        return total[0];
    }
}

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

// water volume for each element depends on the "tallest" bar on its left and right sides. 
public class Solution {
    public int trap(int[] A) {
        if(A.length <= 1) return 0;
        int leftMax = A[0];
        int rightMax = 0;
        int sum = 0;
        for(int i = 1; i < A.length - 1; i++){
            rightMax = 0;
            for(int j = i+1; j < A.length; j++){
                if(A[j]>rightMax) rightMax = A[j];   // search for right max
            }
            if(Math.min(leftMax, rightMax) > A[i]){
                sum += (Math.min(leftMax, rightMax) - A[i]);
            }
            if(A[i] > leftMax) leftMax = A[i];     // update left max
        }
        return sum;
    }
}

Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly Lcharacters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

click to show corner cases.

Solution:
Trivial implementation question. Need to be care of corner cases.

// case1 : last line --->append addtional spaces at the end.
// case2 : one char in a line --->append addtional spaces at the end.
// case3 : no space at the left & right most 
//    ---> assign a space before a word except the first word in a line
public class Solution {
    public ArrayList fullJustify(String[] words, int L) {
        ArrayList result = new ArrayList();
        
        // justify one line
        ArrayList curLine = new ArrayList();
        int curLen  = 0;
        int i = 0;
        while(i < words.length){
            // the current line has enough space
            if(curLen == 0 || curLen + 1 + words[i].length() <= L){
             
                // check if it is the last word in a line
                if(curLen == 0)
                    curLine.add(words[i]);
                else
                    curLine.add(" " + words[i]);
                            
                curLen += curLine.get(curLine.size()-1).length();
                
                
                // last line
                if(i == words.length -1){
                    String str = convert(curLine);
                    
                    // append spaces at the end
                    int diff = L - curLen;
                    for(int k = diff; k > 0; k--)
                        str += " ";
                    result.add(str);
                }
                
                i++;
            }
            
            // the current line can't contain the current word
            else{
                // additional space
                int diff = L - curLen;
                int l = 0;
                
                for(int k = diff; k > 0; k--){
                    
                    // only one char in a line
                    if(curLine.size() == 1){                
                        curLine.set(0, curLine.get(0) + " ");
                    }
                    else{
                        // not assign space after the last word
                        if(l == curLine.size()-1){
                            l = 0;
                        }
                
                        curLine.set(l, curLine.get(l) + " ");
                            l++;
                        }
                    }
                    result.add(convert(curLine));
                
                    // justify in a new line    
                    curLine = new ArrayList();
                    curLen = 0;
                
                }
            }
        
        return result;
    }
    
    public String convert(ArrayList strs){
        StringBuilder sb = new StringBuilder();
        for(String str : strs)
            sb.append(str);
        return sb.toString();
    }
}

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.

Solution:
Compare it level by level.
And use to stacks to represent its left and right child. 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        Stack s1 = new Stack();
        Stack s2 = new Stack();
        s1.push(root.left);
        s2.push(root.right);
        while(!s1.isEmpty() && !s2.isEmpty()){
            TreeNode tr1 = s1.pop();
            TreeNode tr2 = s2.pop();
            if((tr1 == null) && (tr2 == null)) continue;
            if((tr1 == null) || (tr2 == null)) return false;
            if(tr1.val != tr2.val) return false;
            s1.push(tr1.left);
            s1.push(tr1.right);
            s2.push(tr2.right);
            s2.push(tr2.left);
        }
        return true;
    }
}

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Solution:
Basic linked list implementation question.
Be care of null pointers.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public static ListNode swapPairs(ListNode head) {
       if(head == null) return null;
       if(head.next == null) return head;
       ListNode first = head;
       ListNode second = head.next;
       ListNode third = null;
       head = second;
       if(second.next != null){
           third = second.next;
           first.next = third.next == null ? third : third.next;
       }
       else first.next = null;
       second.next = first;
       
       ListNode currentNode = third;
       while(currentNode != null){
            first = currentNode;
            second = null;
            third = null;
            if(currentNode.next != null){ 
                second = currentNode.next;
            }
            if(second != null && second.next != null){
                third = second.next;
                first.next = third.next == null ? third : third.next;
            }
            else first.next = null;
            if(second != null){
                second.next = first;
            }
            currentNode = third;
       }
       return head;
    }
}

Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Solution:
If we think it directly, it would be complicated. A easier way is think it in an opposite way.
What nodes will not be flipped?
BFS each 'O' on the edges, mark 'O's which can be visited from edged 'O'.
Tips: use a size 2 array to represent coordinates (x,y).

////////////////////////// bfs from edged 'O', and mark its surrounding 'O's, that will not be flipped. //////////////////////////

public class Solution {
    public void solve(char[][] board) {
        int m = board.length;
        if(m == 0) return;
        int n = board[0].length;
        
        boolean[][] marked = new boolean[m][n];
        
        // find edged 'O'.
        for(int i = 0; i < m; i++)  
            for(int j = 0; j < n; j++)
                if((i == 0 || i == m-1 || j == 0 || j == n-1) && (!marked[i][j]))
                    if(board[i][j] == 'O')
                        dfs(i,j,m,n,board,marked);
                        
        for(int i = 0; i < m; i++)  
            for(int j = 0; j < n; j++)
                if(!marked[i][j])
                    board[i][j] = 'X';
    }
    
    // mark it surrounding 'O' from edges
    public void dfs(int i, int j, int m, int n, char[][] board, boolean[][] marked){
        ArrayList queue = new ArrayList();
        queue.add(new Integer[]{i, j});
        marked[i][j] = true;
        
        while(!queue.isEmpty()){
            Integer[] tmp = queue.remove(0);
            int x = tmp[0];
            int y = tmp[1];
            
            // not going to visit marked nodes to avoid infinite loops.
            if(x - 1 >= 0 && board[x-1][y] == 'O' && !marked[x-1][y]){
                queue.add(new Integer[]{x-1,y});
                marked[x-1][y] = true;
            }
            if(x + 1 <= m-1 && board[x+1][y] == 'O' && !marked[x+1][y]){
                queue.add(new Integer[]{x+1,y});
                marked[x+1][y] = true;
            }
            if(y - 1 >= 0 && board[x][y-1] == 'O' && !marked[x][y-1]){
                queue.add(new Integer[]{x,y-1});
                marked[x][y-1] = true;
            }
            if(y + 1 <= n-1 && board[x][y+1] == 'O' && !marked[x][y+1]){
                queue.add(new Integer[]{x,y+1});
                marked[x][y+1] = true;
            }
        }
    }
    
}