[TOP] Solutions to LeetCode Problems

3Sum
3Sum Closest
4Sum
Add Binary
Add Two Numbers
Anagrams
Balanced Binary Tree
Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock III

Binary Tree Inorder Traversal
Binary Tree Level Order Traversal
Binary Tree Level Order Traversal II

Binary Tree Maximum Path Sum
Binary Tree Zigzag Level Order Traversal
Climbing Stairs
Combination Sum
Combination Sum II
Combinations
Construct Binary Tree from Inorder and Postorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
Container With Most Water
Convert Sorted Array to Binary Search Tree
Convert Sorted List to Binary Search Tree
Count and Say
Decode Ways
Distinct Subsequences
Divide Two Integers
Edit Distance
First Missing Positive
Flatten Binary Tree to Linked List
Generate Parentheses
Gray Code
Implement strStr()
Insert Interval
Integer to Roman
Interleaving String
Jump Game
Jump Game II
Largest Rectangle in Histogram
Length of Last Word
Letter Combinations of a Phone Number
Longest Common Prefix
Longest Consecutive Sequence
Longest Palindromic Substring
Longest Substring Without Repeating Characters
Longest Valid Parentheses
Maximal Rectangle
Maximum Depth of Binary Tree
Maximum Subarray
Median of Two Sorted Arrays
Merge Intervals
Merge k Sorted Lists
Merge Sorted Array
Merge Two Sorted Lists
Minimum Depth of Binary Tree
Minimum Path Sum
Minimum Window Substring
Multiply Strings
N-Queens
N-Queens II
Next Permutation
Palindrome Number
Partition List
Pascal's Triangle
Pascal's Triangle II
Path Sum
Path Sum II
Permutation Sequence
Permutations
Permutations II
Plus One
Populating Next Right Pointers in Each Node 
Populating Next Right Pointers in Each Node II
Recover Binary Search Tree
Regular Expression Matching
Remove Duplicates from Sorted Array
Remove Duplicates from Sorted Array II
Remove Duplicates from Sorted List
Remove Duplicates from Sorted List II
Remove Element
Remove Nth Node From End of List
Restore IP Addresses
Reverse Integer
Reverse Linked List II
Reverse Nodes in k-Group
Roman to Integer
Rotate Image
Rotate List
Same Tree
Scramble String
Search a 2D Matrix
Search for a Range
Search in Rotated Sorted Array
Search in Rotated Sorted Array II
Search Insert Position
Set Matrix Zeroes
Simplify Path
Sort Colors
Spiral Matrix
Spiral Matrix II
Sqrt(x)
String to Integer (atoi)
Subsets
Subsets II
Substring with Concatenation of All Words
Sudoku Solver
Swap Nodes in Pairs
Symmetric Tree
Text Justification
Trapping Rain Water
Triangle
Two Sum
Unique Binary Search Trees
Unique Binary Search Trees II
Unique Paths
Unique Paths II
Valid Number
Valid Palindrome
Valid Parentheses
Valid Sudoku
Validate Binary Search Tree
Wildcard Matching
Word Ladder

Word Ladder II
Word Search
ZigZag Conversion

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

Solution: to generate all unique BSTs, we should generate the root from 1 to n, and generate its left subtree from 0 to i-1 and for each left subtree, we generate the right subtree from i+1 to n recursively. Note: this is a Binary Search Tree, so that we must make sure that all nodes whose values are smaller than root must be in the left subtree of the root, and all nodes whose values are larger than root must be in the right subtree of the root.

Java语言: UniqueBinarySearchTreesII

01 public ArrayList<TreeNode> generateTrees(int n) {
02     ArrayList<Integer> num=new ArrayList<Integer>();
03     for(int i=1;i<=n;i++)
04     {
05         num.add(i);
06     }
07     return generateTree(num,0,n-1);
08 }
09 
10 public ArrayList<TreeNode> generateTree(ArrayList<Integer> num, int start, int end)
11 {
12     ArrayList<TreeNode> results=new ArrayList<TreeNode>();
13     if(start>end)
14     {
15         TreeNode n=null;          
16         results.add(n);
17         return results;
18     }
19     for(int i=start;i<=end;i++)
20     {
21         ArrayList<TreeNode> leftTrees=generateTree(num, start, i-1);
22         for(int j=0;j<leftTrees.size();j++)
23         {
24             TreeNode leftChild=leftTrees.get(j);
25             ArrayList<TreeNode> rightTrees=generateTree(num, i+1, end);
26             for(int k=0;k<rightTrees.size();k++)
27             {
28                 TreeNode rightChild=rightTrees.get(k);
29                 TreeNode root=new TreeNode(num.get(i));
30                 root.left=leftChild;
31                 root.right=rightChild;
32                 results.add(root);
33             }
34         }
35     }
36     return results;
37 }

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: treat each cell as a node of a graph, and its four cells (up, down, left, right) as neighbors. Use DFS, and use a visited array to mark if a node has been already visited. Starting a DFS from every cell of the board. If find, return true.

Java语言: WordSearch

01 public boolean exist(char[][] board, String word) {
02     int numRows=board.length;
03     int numCols=board[0].length;      
04     boolean [][]visited=new boolean[numRows][numCols];
05     for(int i=0;i<numRows;i++)
06     {
07         for(int j=0;j<numCols;j++)
08         {
09             //DFS starting from each cell
10             if(exist(board, i, j, 0, visited, word))
11                 return true;
12             //reset visited    
13             visited=new boolean[numRows][numCols];
14         }
15     }
16     return false;
17 }
18 
19 //DFS for substring starting at position i of word
20 public boolean exist(char[][] board, int row, int col, int i, boolean[][]visited, String word)
21 {
22     if(i==word.length())
23     {
24         return true;
25     }
26     if(row<0||row>=board.length||col<0 || col>=board[0].length)
27     {
28         return false;
29     }
30     if(!visited[row][col])
31     {
32         //set the current position of board as visited
33         if(board[row][col]==word.charAt(i))
34         {
35             visited[row][col]=true;
36             //DFS on its four neighbor
37             boolean case1=exist(board, row+1, col, i+1, visited, word);
38             boolean case2=exist(board, row-1, col, i+1, visited, word);
39             boolean case3=exist(board, row, col+1, i+1, visited, word);
40             boolean case4=exist(board, row, col-1, i+1, visited, word);              
41             return case1||case2||case3||case4;              
42         }          
43     }
44     return false;
45 }

Examples of Group By Query

Table: persons
id
first_name
last_name
favorite_ride_id

Table: rides
id
name

Write a query that will return the names and votes for the top 10 most popular rides in order from most to least popular.

Note: to use group by, the attributes after the select keyword must appear in the GROUP BY clause or be used in an aggregate function.
 

SELECT rid.name, cnt.votes
FROM rides AS rid
 INNER JOIN
   (
     SELECT favorite_ride_id, count(1) AS votes
     FROM persons
     GROUP BY favorite_rid_id
   ) AS cnt
       ON cnt.favorite_ride_id = rid.id
ORDER BY cnt.votes DESC;

Remove Duplicate Tuples in Database Tables

You have a database table Emp with data as follows:

EmpId FirstName LastName
1 Bob Lync
2 Sarah John
3 Bob Lync
4 John Doe
5 Stanly Jeff
6 Sarah John

With a single SQL query, how will you cleanup the database (eliminate redundant data from above table)

Solution: using group by, and we can find the first appearance of the empid of each user.

DELETE FROM emp 
WHERE empid NOT IN 
(SELECT MIN(empid)
FROM emp 
GROUP BY firstName , lastName);

Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

Solution: we can solve this problem by starting from an example. Assume n=3, we have

000 - 0

001 - 1

011 - 3

010 - 2

110 - 6

111 - 7

101 - 5

100 - 4

The actual sequence of integers is,

000 - 0

001 - 1

010 - 2

011 - 3

100 - 4

101 - 5

110 - 6

111 - 7

By comparing them we find that, the highest bit does not change. Actually, there is a magic to generate the gray code.

http://en.wikipedia.org/wiki/Gray_code

Java语言: GrayCode

01 public ArrayList<Integer> grayCode(int n) {
02     ArrayList<Integer> results=new ArrayList<Integer>();
03     int totalNum=1<<n;
04     for(int i=0;i<totalNum;i++)
05     {
06         int number=i^(i>>1);
07         results.add(number);
08     }
09     return results;
10 }

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution: make the last element of the postorder array as the root, then find the root value in the inorder array. Partition the inorder array into left and right parts. Call the buildTree function recursively. Very similar to the "Construct Binary Tree from Preorder and Inorder Traversal" problem.

Java语言: BuildTreeInorderPostorder

01 public TreeNode buildTree(int[] inorder, int[] postorder) {
02     int length=inorder.length;
03     return buildTree(inorder, 0, length-1, postorder, 0, length-1);
04 }
05 public TreeNode buildTree(int[] inorder, int start1, int end1, int []postorder, int start2, int end2)
06 {
07     if(start1>end1)
08         return null;
09     int value = postorder[end2];
10     int index = search(inorder, start1, end1, value);
11     TreeNode root = new TreeNode(value);
12     TreeNode left=buildTree(inorder, start1, index-1, postorder, start2, start2+index-start1-1);
13     TreeNode right=buildTree(inorder,index+1,end1,postorder, end2-(end1-index),end2-1);
14     root.left=left;
15     root.right=right;
16     return root;
17 }
18 
19 public int search(int[] array, int start, int end, int target)
20 {
21     for(int i=start;i<=end; i++)
22     {
23         if(array[i]==target)
24             return i;
25     }
26     return -1;
27 }

Binary Tree Maximum PathSum

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.

Solution: this answer use a post-order traversal. Note that in Java we cannot pass int variables by reference, therefore we need to pass an ArrayList object to keep and modify the current max value.

Java语言: BinaryTreeMaxPathSum

01 public int maxPathSum(TreeNode root) {
02     ArrayList<Integer> temp = new ArrayList<Integer>(1);
03     temp.add(Integer.MIN_VALUE);
04     maxSubPath(root, temp);
05     return temp.get(0);
06 }
07 
08 public int maxSubPath(TreeNode root, ArrayList<Integer> temp) {
09     if (root == null)  return 0;
10     int leftMax = Math.max(0, maxSubPath(root.left, temp));
11     int rightMax = Math.max(0, maxSubPath(root.right, temp));
12     int curr_max=temp.get(0);
13     int new_max= root.val+leftMax+rightMax;
14       //update the max path sum
15     if(new_max>curr_max)
16         temp.set(0, new_max);
17     //calculate the max sub path, 
18     //either on left branch or right branch
19     return Math.max(root.val+leftMax, root.val+rightMax);
20 }

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.

Solution: using a stack to match the '(' and ')' pairs, and use a hashtable to store these pairs. later, given a left parentheses, with the help of the hash table, you can find the furthest match ')' parentheses.

Java语言: LongestValidParentheses

01 public int longestValidParentheses(String s) {
02     //store the left parentheses
03     Stack<Integer> st=new Stack<Integer>();
04     //store the left, right pairs of parentheses
05     Hashtable<Integer, Integer> matches=new Hashtable<Integer,Integer>();
06     int length=0;
07     int max=0;
08     for(int i=0;i<s.length();i++)
09     {
10         if(s.charAt(i)=='(' )
11         {
12             st.push(i);
13         }
14         if(s.charAt(i)==')')
15         {
16             if(st.size()==0)
17             {
18                 continue;
19             }
20             else
21             {
22                 int left=st.pop();
23                 matches.put(left,i);
24             }
25         }
26     }
27   
28     for(int i=0;i<s.length();i++)
29     {
30         if(matches.containsKey(i))
31         {
32             int value=matches.get(i);
33             while(matches.containsKey(value+1))
34             {
35                 value=matches.get(value+1);
36             }
37             length=value-i+1;
38             if(length>max)
39             {
40                 max=length;
41             }
42         }
43     }
44   
45     return max;
46 }

Interleaving Strings

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Solution: using DP. This question is very similar to "Find all path", you can just imagine, taking string1 is just as going down, and taking string2 is like to going right.

Java语言: InterleavingString

01 public boolean isInterleave(String s1, String s2, String s3) {
02     int m=s1.length();
03     int n=s2.length();
04     int len=s3.length();
05     if(m+n!=len)
06         return false;
07     if(m==0)
08         return s2.equals(s3);
09     if(n==0)
10         return s1.equals(s3);
11     //DP approach, initiate a 2D array to store 
12     //the validity of the interleaving to the current point
13     boolean [][]array=new boolean[m+1][n+1];
14     for(int i=1;i<=m;i++)
15     {
16         if(s1.charAt(i-1)==s3.charAt(i-1))
17         {
18             array[i][0]=true;
19         }
20     }
21     for(int j=1;j<=n;j++)
22     {
23         if(s2.charAt(j-1)==s3.charAt(j-1))
24         {
25             array[0][j]=true;
26         }
27     }
28     for(int i=1;i<=m;i++)
29     {
30         for(int j=1;j<=n;j++)
31         {
32             //take character from s1
33             if(s1.charAt(i-1)==s3.charAt(i+j-1) && array[i-1][j]==true)
34                 array[i][j]=true;
35             //take character from s2    
36             if(s2.charAt(j-1)==s3.charAt(i+j-1) && array[i][j-1]==true)
37                 array[i][j]=true;
38         }
39     }
40     return array[m][n];
41 }