LeetCode - Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

public class Solution {
    public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> ret = new ArrayList<String>();
        if(s==null) {
            return ret;
        }
        int[] ips = new int[4];
        helper(ret, s, 0, ips, 0);
        return ret;
    }
 
    public void helper(ArrayList<String> ret, String s, int k, int ips[], int seg) {
       if(seg==4) {
            if(k==s.length()) {
                ret.add(build(ips));
            }
            return;
        }
        if(k+1<=s.length()) {
            ips[seg] = Integer.parseInt(s.substring(k, k+1));
            helper(ret, s, k+1, ips, seg+1);
        }
        if(k+2<=s.length()) {
            ips[seg] = Integer.parseInt(s.substring(k, k+2));
            if(ips[seg]>=10) {
                helper(ret, s, k+2, ips, seg+1);
            }
        }
        if(k+3<=s.length()) {
            ips[seg] = Integer.parseInt(s.substring(k, k+3));
            if(ips[seg]<=255 && ips[seg]>=100) {
                helper(ret, s, k+3, ips, seg+1);
            }
        }
    }
 
    public String build(int ips[]) {
        StringBuilder sb = new StringBuilder();
        sb.append(ips[0]).append('.').append(ips[1]).append('.').append(ips[2]).append('.').append(ips[3]);
        return sb.toString();
    }
}

=======

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<String>();
        for (int i = 1; i < 4 && i < s.length() - 2; i++) {
            for (int j = i + 1; j < i + 4 && j < s.length() - 1; j++) {
                for (int k = j + 1; k < j + 4 && k < s.length(); k++) {
                    String s1 = s.substring(0, i);
                    String s2 = s.substring(i, j);
                    String s3 = s.substring(j, k);
                    String s4 = s.substring(k);
                    if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
                        res.add(s1 + "." + s2 + "." + s3 + "." + s4);
                    }
                }
            }
        }
        return res;
    }
   
    private boolean isValid(String s) {
        if (s.isEmpty()) {
            return false;
        }
        if (s.length() == 1 || (s.length() == 2 && Integer.parseInt(s) >= 10) || (s.length() == 3 && Integer.parseInt(s) >= 100 && Integer.parseInt(s) <= 255)) {
            return true;
        } return false;
    }
}

LeetCode - Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

public class Solution {
    public void solveSudoku(char[][] board) {
        // Start typing your Java solution below
        // DO NOT write main() function
        helper(board);
    }
    
    public boolean helper(char[][] board) {
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) {
                if(board[i][j]=='.') {
                    for(int a=1;a<=9;a++) {
                        board[i][j] = (char) ((int)'0' + a);
                        if(isValid(board, i, j) && helper(board)) {
                            return true;
                        }
                    }
                    board[i][j] = '.';
                    return false;
                }
            }
        }
        return true;
    }
    
    public boolean isValid(char[][] board, int m, int n) {
        for(int i=0;i<9;i++) {
            if(i!=m && board[i][n]==board[m][n]) {
                return false;
            }
        }
        for(int j=0;j<9;j++) {
            if(j!=n && board[m][j]==board[m][n]) {
                return false;
            }
        }
        
        for(int p=0;p<3;p++) {
            for(int q=0;q<3;q++) {
                int t = m/3*3+p;
                int s = n/3*3+q;
                if(!(t==m && s==n) && board[t][s]==board[m][n]) {
                    return false;
                }
            }
        }
        return true;
    }
} 

================


public class Solution {
    public void solveSudoku(char[][] board) {
        helper(board);
    }
    
    private boolean helper(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (check(board, i, j, c)) {
                            board[i][j] = c;
                            if (helper(board)) {
                                return true;
                            }
                        }
                    }
                    board[i][j] = '.';
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean check(char[][] board, int m, int n, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][n] == c) {
                return false;
            }
        }
        for (int j = 0; j < 9; j++) {
            if (board[m][j] == c) {
                return false;
            }
        }
        int x = m / 3;
        int y = n / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[x * 3 + i][y * 3 + j] == c) {
                    return false;
                }
            }
        }
        return true;
    }

}

=============

public class Solution {
    public void solveSudoku(char[][] board) {
        helper(board);
    }
    
    private boolean helper(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        board[i][j] = c;
                        if (check(board, i, j, c) && helper(board)) {
                            return true;
                        }
                    }
                    board[i][j] = '.';
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean check(char[][] board, int i, int j, char c) {
        for (int m = 0; m < 9; m++) {
            if (board[i][m] == c && m != j) {
                return false;
            }
            if (board[m][j] == c && m != i) {
                return false;
            }
            int cubeRow = i / 3;
            int cubeColumn = j / 3;
            int x = m / 3; 
            int y = m % 3;
            if (board[cubeRow * 3 + x][cubeColumn * 3 + y] == c && cubeRow * 3 + x != i && cubeColumn * 3 + y != j) {
                return false;
            }
        }
        return true;
    }

}

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) {
        int m = board.length;
        int n = board[0].length;
        boolean visit[][] = new boolean[m][n];
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(visit(board, visit, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }
 
    public boolean visit(char[][] board, boolean visit[][], String word, int k, int i, int j) {
        if(k==word.length()) {
            return true;
        }
        int m = board.length;
        int n = board[0].length;
        if(i<0 || i>=m || j<0 || j>=n || visit[i][j]) {
            return false;
        }
        if(word.charAt(k)==board[i][j]) {
            visit[i][j] = true;
            boolean exist = visit(board, visit, word, k+1, i+1, j) || visit(board, visit, word, k+1, i-1, j)
                || visit(board, visit, word, k+1, i, j+1) || visit(board, visit, word, k+1, i, j-1);
            visit[i][j] = false;
            return exist;
        } else {
            return false;
        }
    }
}

=======

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0 || word == null) {
            return false;
        }
        int row = board.length;
        int column = board[0].length;
        boolean[][] visited = new boolean[row][column];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (visit(board, word, visited, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }
   
    private boolean visit(char[][] board, String word, boolean[][] visited, int cur, int i, int j) {
        int row = board.length;
        int column = board[0].length;
        if (i < 0 || i >= row || j < 0 || j >= column || visited[i][j] || board[i][j] != word.charAt(cur)) {
            return false;
        }
        if (cur == word.length() -1) {
            return true;
        }
        visited[i][j] = true;
        boolean res = visit(board, word, visited, cur + 1, i + 1, j) ||
               visit(board, word, visited, cur + 1, i - 1, j) ||
               visit(board, word, visited, cur + 1, i, j + 1) ||
               visit(board, word, visited, cur + 1, i, j - 1);
        visited[i][j] = false;
        return res;
    }
}

LeetCode - Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

public class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        if(s==null) {
            return max;
        }
        int valid = 0;
        Stack<Integer> stk = new Stack<Integer>();
        for(int i=0;i<s.length();i++) {
            char c = s.charAt(i);
            if(c==')') {
                if(stk.isEmpty()) {
                    valid = i+1;
                } else {
                    stk.pop();
                    if(stk.isEmpty()) {
                        max = Math.max(max, i-valid+1);
                    } else {
                        max = Math.max(max, i-stk.peek());
                    }
                }
            } else {
                stk.push(i);
            }
        }
        return max;
    }
}

public class Solution {
    public int longestValidParentheses(String s) {
        if(s==null || s.length()==0) {
            return 0;
        }
        Stack<Integer> stk = new Stack<Integer>();
        int tag[] = new int[s.length()];
        for(int i=0;i<s.length();i++) {
            char c = s.charAt(i);
            if(c=='(') {
                stk.push(i);
            } else {
                if(!stk.isEmpty()) {
                    int j = stk.pop();
                    tag[i] = 1;
                    tag[j] = 1;
                } else {
                }
            }
        }
        int max = 0;
        int cur = 0;
        for(int i=0;i<tag.length;i++) {
            int n = tag[i];
            if(n==1) {
                cur += 1;
            } else {
                cur =0;
            }
            max = Math.max(cur, max);
        }
        return max;
    }
}

LeetCode - Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int maxLength = 0;
        int start = 0;
        for(int i=0;i<s.length();i++) {
            char c = s.charAt(i);
            Integer p = map.get(c);
            if(p==null || p.intValue()<start) {
                map.put(c, i);
                maxLength = Math.max(i-start+1, maxLength);
            } else {
                start = p.intValue()+1;
                map.put(c, i);
            }
        }
        return maxLength;
    }
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int ans = 0;
        int last = -1;
        for(int i=0;i<s.size();i++) {
            char c = s[i];
            if(hash.find(c)!=hash.end()) {
                last = max(last, hash[c]); 
            }
            ans = max(ans, i-last);
            hash[c] = i;
        }
        return ans;
    }
};

LeetCode - Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] ret = {-1, -1};
        if(A==null || A.length==0 || target<A[0] || target>A[A.length-1]) {
            return ret;
        }
        int start = 0;
        int end = A.length-1;
        while(start<=end && !(ret[0]!=-1 && ret[1]!=-1)) {
            int mid = (start+end)/2;
            if(A[mid]==target) {
                end = mid;
                start = mid;
                while(end<A.length && A[end]==A[mid]) {
                    end++;
                }
                while(start>=0 && A[start]==A[mid]) {
                    start--;
                }
                ret[0] = start + 1;
                ret[1] = end - 1;
            } else if(A[mid]<target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return ret;
    }
}

==========

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = {nums.length, -1};
        search(nums, 0, nums.length - 1, target, res);
        if (res[0] == nums.length) {
            res[0] = -1;
        }
        return res;
    }
 
    private void search(int[] nums, int s, int e, int target, int[] range) {
        if (s <= e) {
            int m = (s + e) / 2;
            if (target == nums[m]) {
                range[0] = Math.min(range[0], m);
                search(nums, s, m - 1, target, range);
                range[1] = Math.max(range[1], m);
                search(nums, m + 1, e, target, range);
            } else if (target < nums[m]) {
                search(nums, s, m - 1, target, range);
            } else {
                search(nums, m + 1, e, target, range);
            }
        }
    }
}


===========


public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = helper(nums, 0, nums.length - 1, target);
        return res;
    }
 
    private int[] helper(int[] nums, int s, int e, int target) {
        int[] res = {-1, -1};
        while (s <= e) {
            int m = (s + e) / 2;
            if (nums[m] > target) {
                e = m - 1;
            } else if (nums[m] < target) {
                s = m + 1;
            } else {
                int[] left = helper(nums, s, m - 1, target);
                res[0] = left[0] == -1 ? m : left[0];
                int[] right = helper(nums, m + 1, e, target);
                res[1] = right[1] == -1 ? m : right[1];
                break;
            }
        }
        return res;
    }
}
=====

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        return find(nums, target, 0, nums.length - 1, true, true);
    }
   
    private int[] find(int[] nums, int target, int s, int e, boolean findleft, boolean findright) {
        int[] res = {-1, -1};
        while (s <= e) {
            int m = s + (e - s) / 2;
            if (nums[m] == target) {
                res[0] = m;
                res[1] = m;
                if (findleft) {
                    int[] left = find(nums, target, s, m - 1, true, false);
                    if (left[0] != -1) res[0] = left[0];
                }
                if (findright) {
                    int[] right = find(nums, target, m + 1, e, false, true);
                    if (right[0] != -1) res[1] = right[1];
                }
                break;
            } else if (nums[m] < target) {
                s = m + 1;
            } else {
                e = m - 1;
            }
        }
        return res;
    }
}

LeetCode - 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.

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid==null) {
            return 0;
        }
        int m = obstacleGrid.length;
        if(m==0) {
            return 0;
        }
        int n = obstacleGrid[0].length;
        if(n==0) {
            return 0;
        }
        int step[][] = new int[m][n];
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                int g = obstacleGrid[i][j];
                if(g==1) {
                    step[i][j] = 0;
                } else if(i==0 && j==0) {
                    step[i][j] = 1;
                } else if(i==0) {
                    step[i][j] = step[i][j-1];
                } else if(j==0) {
                    step[i][j] = step[i-1][j];
                } else {
                    step[i][j] = step[i-1][j] + step[i][j-1];
                }
            }
        }
        return step[m-1][n-1];
    }
}

LeetCode - 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.

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) {
        if(board==null) {
            return false;
        }
        if(board.length!=9 || board[0].length!=9) {
            return false;
        }
        HashSet<Character> set = new HashSet<Character>();
        for(int i=0;i<9;i++) {
            set.clear();
            for(int j=0;j<9;j++) {
                char c = board[i][j];
                if(c=='.') {
                    continue;
                } else if(set.contains(c)) {
                    return false;
                } else {
                    set.add(c);
                }
            }
        }
        for(int j=0;j<9;j++) {
            set.clear();
            for(int i=0;i<9;i++) {
                char c = board[i][j];
                 if(c=='.') {
                    continue;
                } else if(set.contains(c)) {
                    return false;
                } else {
                    set.add(c);
                }
            }
        }
        for(int m=0;m<3;m++) {
            for(int n=0;n<3;n++) {
                set.clear();
                for(int a=0;a<3;a++) {
                    for(int b=0;b<3;b++) {
                        char c = board[m*3+a][n*3+b];
                        if(c=='.') {
                            continue;
                        } else if(set.contains(c)) {
                            return false;
                        } else {
                            set.add(c);
                        }
                    }
                }
            }
        }
        return true;
    }
}

=========
public boolean isValidSudoku(char[][] board) { for(int i = 0; i<9; i++){ HashSet<Character> rows = new HashSet<Character>(); HashSet<Character> columns = new HashSet<Character>(); HashSet<Character> cube = new HashSet<Character>(); for (int j = 0; j < 9;j++){ if(board[i][j]!='.' && !rows.add(board[i][j])) return false; if(board[j][i]!='.' && !columns.add(board[j][i])) return false; int RowIndex = 3*(i/3); int ColIndex = 3*(i%3); if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3])) return false; } } return true; }

LeetCode - 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.

Have you been asked this question in an interview?

public class Solution {

    public boolean isValid(String s) {

        if(s==null) {

            return true;

        }

        Stack<Character> stk = new Stack<Character>();

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

            char c= s.charAt(i);

            if(c=='('||c=='{'||c=='[') {

                stk.push(c);

            } else if(stk.isEmpty()) {

                return false;

            } else {

                char c2 = stk.pop();

                if(!((c==')'&&c2=='(') || (c=='}'&&c2=='{') || (c==']'&&c2=='['))) {

                    return false;

                }

            }

        }

        if(stk.isEmpty()) {

            return true;

        } else {

            return false;

        }

    }

}

LeetCode - Simplify Path

Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

public class Solution {

    public String simplifyPath(String path) {

        // Start typing your Java solution below

        // DO NOT write main() function

        Stack<String> stk = new Stack<String>();

        String tks[] = path.split("\\/");

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

            String tk = tks[i];

            if(tk.isEmpty() || tk.equals(".")) {

                continue;

            } else if(tk.equals("..")) {

                if(!stk.isEmpty()) {

                    stk.pop();

                }

            } else {

                stk.push(tk);

            }

        }

        if(stk.size()==0) {

            return "/";

        }

        String sp = "";

        while(stk.size()!=0) {

            sp = "/" + stk.pop() + sp; 

        }

        return sp;

    }

}

LeetCode - 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.

/**

 * 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 genTrees(1, n);

    }

    

    public ArrayList<TreeNode> genTrees(int a, int b) {

        ArrayList<TreeNode> trees = new ArrayList<TreeNode>();

        if(a>b) {

            trees.add(null);

        } else if(a==b) {

            trees.add(new TreeNode(a));

        } else {

            for(int i=a;i<=b;i++) {

                ArrayList<TreeNode> lefts = genTrees(a, i-1);

                ArrayList<TreeNode> rights = genTrees(i+1, b);

                for(TreeNode l : lefts) {

                    for(TreeNode r : rights) {

                        TreeNode tree = new TreeNode(i);

                        tree.left = l;

                        tree.right = r;

                        trees.add(tree);

                    }

                }

            }

        }

        return trees;

    }

}

LeetCode - 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!

public class Solution {
    public int trap(int[] A) {
        if(A==null || A.length<=2) {
            return 0;
        }
        int water = 0;
        int max = 0;
        int maxLeft[] = new int[A.length];
        int maxRight[] = new int[A.length];
        for(int i=0;i<A.length;i++) {
            maxLeft[i] = max;
            max = Math.max(max, A[i]);
        }
        max = 0;
        for(int i=A.length-1;i>=0;i--) {
            maxRight[i] = max;
            max = Math.max(max, A[i]);
        }
        for(int i=1;i<A.length-1;i++) {
            int min = Math.min(maxLeft[i], maxRight[i]);
            if(A[i]<min) {
                water += min - A[i];
            }
        }
        return water;
    }
}

=============
public class Solution {
    public int trap(int[] A) {
        int n = A.length;
        int left=0; int right=n-1;
        int res=0;
        int maxleft=0, maxright=0;
        while(left<=right){
            if(A[left]<=A[right]){
                if(A[left]>=maxleft) maxleft=A[left];
                else res+=maxleft-A[left];
                left++;
            }
            else{
                if(A[right]>=maxright) maxright= A[right];
                else res+=maxright-A[right];
                right--;
            }
        }
        return res;
    }

}

LeetCode - Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.
For example,
Given n = 3,
You should return the following matrix:

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

public class Solution {
    public int[][] generateMatrix(int n) {
        if(n<0) {
            return null;
        }
        int matrix[][] = new int[n][n];
        if(n==0) {
            return matrix;
        }
        int t = 1;
        int loop = 0;
        while(t<=n*n) {
            for(int i=loop;i<n-loop;i++) {
                matrix[loop][i] = t++;
            }
            if(t>n*n) {
                break;
            }
            for(int i=loop+1;i<n-loop-1;i++) {
                matrix[i][n-loop-1] = t++;
            }
            if(t>n*n) {
                break;
            }
            for(int i=n-loop-1;i>=loop;i--) {
                matrix[n-loop-1][i] = t++;
            }
            if(t>n*n) {
                break;
            }
            for(int i=n-loop-2;i>loop;i--) {
                matrix[i][loop] = t++;
            }
            loop++;
        }
        return matrix;
    }
}

============

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        if (n <= 0) {
            return res;
        }
        int val = 1;
        int max = n * n;
        int direction = 0;
        int i = 0;
        int j = -1;
        while (val <= max) {
            int i2 = i;
            int j2 = j;
            if (direction == 0) {
                j2 += 1;
            } else if (direction == 1) {
                i2 += 1;
            } else if (direction == 2) {
                j2 -= 1;
            } else if (direction == 3) {
                i2 -= 1;
            }
            if (i2 < 0 || i2 >= n || j2 < 0 || j2 >= n || res[i2][j2] != 0) {
                direction = (direction + 1) % 4;
            } else {
                res[i2][j2] = val++;
                i = i2;
                j = j2;
            }
        }
        return res;
    }
}

LeetCode - Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> ints = new ArrayList<Integer>();
        if(matrix==null || matrix.length==0) {
            return ints;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int loop = 0;
        while(ints.size()<m*n) {
            for(int i=loop;i<n-loop;i++) {
                ints.add(matrix[loop][i]);
            }
            if(ints.size()==m*n) {
                break;
            }
            for(int i=loop+1;i<m-loop-1;i++) {
                ints.add(matrix[i][n-loop-1]);
            }
            if(ints.size()==m*n) {
                break;
            }
            for(int i=n-loop-1;i>=loop;i--) {
                ints.add(matrix[m-loop-1][i]);
            }
            if(ints.size()==m*n) {
                break;
            }
            for(int i=m-loop-2;i>loop;i--) {
                ints.add(matrix[i][loop]);
            }
            loop++;
        }
        return ints;
    }
}

LeetCode - 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) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(matrix==null) {
            return;
        }
        int n = matrix.length;
        for(int i=0;i<n/2;i++) {
            for(int j=0;j<Math.ceil(((double)n)/2.);j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = tmp;
            }
        }
    }
}

LeetCode - Remove Nth Node From End of List

Given a linked list, remove the n^th node from the end of list and return its head.
For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null) {
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        int m = n;
        while(m-->0) {
            p2 = p2.next;
        }
        if(p2==null) {
            return head.next;
        }
        while(p2.next!=null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = p1.next.next;
        return head;
    }
}

LeetCode - 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) {
        if(intervals==null || intervals.size()==0) {
            return intervals;
        }
        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval a, Interval b) {
                if(a.start<b.start) {
                    return -1;
                } else if(a.start>b.start) {
                    return 1;
                } else {
                    return a.end - b.end;
                }
            }
        });
        ArrayList<Interval> newIns = new ArrayList<Interval>();
        Interval tmp = intervals.get(0);
        newIns.add(tmp);
        for(int i=1;i<intervals.size();i++) {
            Interval in = intervals.get(i);
            if(in.start>tmp.end) {
                newIns.add(in);
                tmp = in;
            } else if(in.end<=tmp.end) {
                continue;
            } else if(in.end>tmp.end){
                tmp.end = in.end;
            }
        }
        return newIns;
    }
}


==========

/**
 * 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 List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() == 0) {
            return intervals;
        }
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                if (i1.start == i2.start) {
                    return i1.end - i2.end;
                } else {
                    return i1.start - i2.start;
                }
            }
        }
        );
        List<Interval> res = new ArrayList<Interval>();
        Interval pre = new Interval(intervals.get(0).start, intervals.get(0).end);
        for (int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if (cur.start <= pre.end) {
                pre.end = Math.max(pre.end, cur.end);
            } else {
                res.add(pre);
                pre = new Interval(cur.start, cur.end);
            }
        }
        res.add(pre);
        return res;
    }
}

LeetCode - Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists==null || lists.size()==0) {
            return null;
        }
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>(){
            public int compare(ListNode a, ListNode b) {
                return a.val>b.val?1:(a.val==b.val?0:-1);
            }
        }
        );
        for(int i=0;i<lists.size();i++) {
            if(lists.get(i)!=null) {
                queue.add(lists.get(i));
            }
        }
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while(queue.size()!=0) {
            cur.next = queue.poll();
            if(cur.next.next!=null) {
                queue.add(cur.next.next);
            }
            cur = cur.next;
        }
        return head.next;
    }
}

LeetCode - 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.

/**

 * 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) {

        if(root==null || (root.left==null && root.right==null)) {

            return true;

        }

        return check(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

    }

    

    public boolean check(TreeNode root, int min, int max) {

        if(root==null)  {

            return true;

        }

        return root.val>min && root.val<max && check(root.left, min, root.val) && check(root.right, root.val, max);

    }

}


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode *pre = NULL;
        return check(root, pre);
    }
 
    bool check(TreeNode* node, TreeNode* &pre) {
        if(node==NULL) {
            return true;
        }
        if(!check(node->left, pre)) {
            return false;
        }
        if(pre!=NULL && pre->val>=node->val) {
            return false;
        }
        pre = node;
        return check(node->right, pre);
    }
};/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
 
    private TreeNode pre = null;
 
    public boolean isValidBST(TreeNode root) {
        pre = null;
        return check(root);
    }
 
    public boolean check(TreeNode node) {
        if(node==null) {
            return true;
        }
        if(!check(node.left)) {
            return false;
        }
        if(pre!=null && pre.val>=node.val) {
            return false;
        }
        pre = node;
        return check(node.right);
    }
}


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode node) {
        if (node == null) {
            return true;
        }
        boolean isLeftOK = isValidBST(node.left);
        if (!isLeftOK) {
            return false;
        }
        if (lastVisit != null) {
            if (lastVisit.val >= node.val) {
                return false;
            }
        }
        lastVisit = node;
        boolean isRightOK = isValidBST(node.right);
        return isRightOK;
    }
 
    private TreeNode lastVisit = null;
 
}

===========

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   
    private TreeNode pre;
   
    public boolean isValidBST(TreeNode root) {
        pre = null;
        return visit(root);
    }
   
    private boolean visit(TreeNode node) {
        if (node == null) {
            return true;
        }
        if (!visit(node.left) || (pre != null && pre.val >= node.val)) {
            return false;
        }
        pre = node;
        return visit(node.right);
    }
}

LeetCode - Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int height[][] = new int[m][n+1];
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(matrix[i][j]=='0') {
                    height[i][j] = 0;
                } else if(i==0){
                    height[i][j] = 1;
                } else {
                    height[i][j] = height[i-1][j] + 1;
                }
            }
        }
        int maxArea = 0;
        for(int r=0;r<m;r++) {
            int hei[] = height[r];
            Stack<Integer> stk = new Stack<Integer>();
            for(int i=0;i<hei.length;i++) {
                int h = hei[i];
                if(stk.isEmpty() || h>=hei[stk.peek()]) {
                    stk.push(i);
                } else {
                    int tmp = stk.pop();
                    int area = hei[tmp] * (stk.isEmpty()?i:i-stk.peek()-1);
                    if(area>maxArea) {
                        maxArea = area;
                    }
                    i--;
                }
            }
        }
        return maxArea;
    }
}

LeetCode - Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

public class Solution {
    public int sqrt(int x) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(x<0) return -1;
        if(x==0) return 0;
     
        double y = ((double)x)/2.;
        while(Math.abs(y*y-x)>0.00001){
            y=(y+x/y)/2.;
        }
        return (int) y;
    }
}

=========

public class Solution {
    public int mySqrt(int x) {
        assert(x >= 0);
        if (x <= 1) {
            return x;
        }
        int s = 1;
        int e = x;
        while (s <= e) {
            int m = (s + e) / 2;
            if (x / m >= m && x / (m + 1) < (m + 1)) {
                return m;
            } else if (x / m > m) {
                s = m + 1;
            } else {
                e = m - 1;
            }
        }
        return 1;
    }
}
=========

public class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        } else if (x == 1) {
            return 1;
        }
        int s = 1, e = x / 2;
        int res = 0;
        while (s <= e) {
            int m = s + (e - s) / 2;
            if (m <= x / m) {
                s = m + 1;
                res = m;
            } else {
                e = m - 1;
            }
        }
        return res;
    }
}