Binary Tree Inorder Traversal (Java)

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

	/*
	Given a binary tree, return the inorder traversal of its nodes' values.
	For example:
	Given binary tree {1,#,2,3},
	1
	\
	2
	/
	3
	return [1,3,2].
	Note: Recursive solution is trivial, could you do it iteratively?
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	// recursive
	public class Solution {
	public List<Integer> inorderTraversal(TreeNode root) {
	ArrayList<Integer> result = new ArrayList<Integer> ();
	if (root == null){
	return result;
	}
	traverse(root, result);
	return result;
	}
	private void traverse(TreeNode root, ArrayList<Integer> result){
	if (root==null){
	return;
	}
	traverse(root.left, result);
	result.add(root.val);
	traverse(root.right, result);
	}
	}
	//iterative solution
	public class Solution {
	public List<Integer> inorderTraversal(TreeNode root) {
	ArrayList<Integer> result= new ArrayList<Integer>();
	if (root == null){
	return result;
	}
	Stack<TreeNode> stack = new Stack<TreeNode> ();
	while (root!=null){
	stack.push(root);
	root=root.left;
	}
	while(!stack.isEmpty()){
	TreeNode current = stack.pop();
	result.add(current.val);
	if (current.right != null){
	root=current.right;
	while(root!=null){
	stack.push(root);
	root=root.left;
	}
	}
	}
	return result;
	}
	}

view raw BinaryTreeInorderTraversal.java hosted with ❤ by GitHub

Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution: DP

maxProfit[i]=maxProfit[i-1]+prices[i]-prices[i-1] if prices[i]>prices[i-1]

maxProfit[i]=maxProfit[i-1] if prices[i]<=prices[i-1]

	/*
	Say you have an array for which the ith element is the price of a given stock on day i.
	Design an algorithm to find the maximum profit. You may complete as many transactions
	as you like (ie, buy one and sell one share of the stock multiple times). However,
	you may not engage in multiple transactions at the same time
	(ie, you must sell the stock before you buy again).
	*/
	public class Solution {
	public int maxProfit(int[] prices) {
	if (prices==null || prices.length<=1){
	return 0;
	}
	// used to record max profit can get until each day
	int[] maxProfit=new int[prices.length];
	maxProfit[0]=0;
	for (int i=1; i<prices.length; i++){
	if (prices[i]>prices[i-1]){
	// price go up, max profit is max profit get by yesterday plus new profit
	maxProfit[i]=prices[i]-prices[i-1]+maxProfit[i-1];
	}
	else{
	// price go down, max profit can get by today should be equal to yesterday.
	maxProfit[i]=maxProfit[i-1];
	}
	}
	return maxProfit[maxProfit.length-1];
	}
	}

view raw BestTimeToBuyandSellStockII.java hosted with ❤ by GitHub

Generate Parentheses (Java)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"




Solution: Greedy and Recursive

Take advantage of the feature of parentheses, left side and right side must match each other,  in other words, if there a left side parenthese,  whatever position it is, there must be a right side parenthese to match it.

	/*
	Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
	For example, given n = 3, a solution set is:
	"((()))", "(()())", "(())()", "()(())", "()()()"
	*/
	public class Solution {
	public List<String> generateParenthesis(int n) {
	List<String> result=new ArrayList<String> ();
	if (n<1){
	return result;
	}
	int leftNum=n;
	int rightNum=n;
	StringBuffer current=new StringBuffer();
	buildResult(leftNum, rightNum, current, result);
	return result;
	}
	private void buildResult(int leftNum, int rightNum, StringBuffer current, List<String> result){
	// if both sides number of parenthese equal to 0, then we got an valid result
	if (leftNum==0 && rightNum==0){
	result.add(current.toString());
	return;
	}
	// if number of left Parenthese bigger than 0, then add one left parenthese and
	// keep builResult from there
	if (leftNum>0){
	current.append('(');
	buildResult(leftNum-1, rightNum, current, result);
	current.deleteCharAt(current.length()-1);
	}
	// if number of right parenthese bigger than left, then add one right parenthese and
	// builResult from there
	if (rightNum>leftNum){
	current.append(')');
	buildResult(leftNum, rightNum-1, current, result);
	current.deleteCharAt(current.length()-1);
	}
	}
	}

view raw GenerateParentheses.java hosted with ❤ by GitHub

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution: DP

ways[n]=ways[n-1]+ways[n-2];

No matter what n is,  it must be reached  from n-1 or n-2 , then use array to  record unique ways from 0 to end 

	/*
	You are climbing a stair case. It takes n steps to reach to the top.
	Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
	*/
	//DP Solution
	public class Solution {
	public int climbStairs(int n) {
	if (n<0){
	return 0;
	}
	// record unique ways for each n
	int [] unique_ways=new int[n+1];
	// start point which contains only one situation
	unique_ways[0]=1;
	// can only move 1 step , so ways is only 1
	unique_ways[1]=1;
	for (int i=2; i<n+1; i++){
	unique_ways[i]=unique_ways[i-1]+unique_ways[i-2];
	}
	return unique_ways[n];
	}
	}

view raw climbingStars.java hosted with ❤ by GitHub

Best Time to Buy and Sell Stock (Java)

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution:
loop through entire list  and  catch min_price and the position of this this price, when current reached price's position after min_price's position then do calculate difference and up max_profit

	/*
	Say you have an array for which the ith element is the price of a given stock on day i.
	If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
	*/
	public class Solution {
	public int maxProfit(int[] prices) {
	if (prices==null || prices.length==0){
	return 0;
	}
	int min_price=Integer.MAX_VALUE;
	int min_position=0;
	int max_profit=0;
	for (int i=0;i<prices.length; i++){
	if (prices[i]<min_price){
	min_price=prices[i];
	min_position=i;
	}
	if (i>min_position){
	max_profit=Math.max(max_profit, prices[i]-min_price);
	}
	}
	return max_profit;
	}
	}

view raw Best TimetoBuyandSellStock.java hosted with ❤ by GitHub

Unique Paths Java

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?

Solution:DP 

Ways to destination point is equal to ways to up neighbor of destination point and left neighbor of destination point 

then we can generalize 

ways[m][n]=ways[m-1][n] + ways[m][n-1]

	/*
	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?
	*/
	// 1D DP
	public class Solution {
	public int uniquePaths(int m, int n) {
	if (m<0||n<0){
	return 0;
	}
	if (m==0 || n==0 ){
	return 1;
	}
	int[] arr=new int[n];
	arr[0]=1;
	for (int i=0; i<m; i++){
	for (int j=1; j<n; j++){
	arr[j]=arr[j]+arr[j-1];
	}
	}
	return arr[n-1];
	}
	}
	// 2D DP
	public class Solution {
	public int uniquePaths(int m, int n) {
	if (m<0||n<0){
	return 0;
	}
	if (m==0 || n==0 ){
	return 1;
	}
	int[][] matrix=new int[m][n];
	for (int i=0; i<m; i++){
	matrix[i][0]=1;
	}
	for (int i=0; i<n; i++){
	matrix[0][i]=1;
	}
	for (int i=1; i<m; i++){
	for (int j=1; j<n; j++){
	matrix[i][j]=matrix[i-1][j]+matrix[i][j-1];
	}
	}
	return matrix[m-1][n-1];
	}
	}

view raw UniquePath.java hosted with ❤ by GitHub

Binary Tree Postorder Traversal (Java)

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution;

For iterative solution, we know postal order is visit children before parent so  a stack could be apply here as a helper structure. Then, we can ' push left child from root until left most leaf into stack. then start pop node  from the stack, however, if the current node which going to be pop out has right node we should start push all left nodes of the right child until to leaf. But the trick point is how to tell if the mid need to be pop out  , We can use a child node to catch every popped out  node, then if the mid's right node equal to child node which mean this mid's right node has been visited, it is a good time to pop out the mid one .

	/*
	Given a binary tree, return the postorder traversal of its nodes' values.
	For example:
	Given binary tree {1,#,2,3},
	1
	\
	2
	/
	3
	return [3,2,1].
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	// iterative solution 9/14/2014
	public class Solution {
	public List<Integer> postorderTraversal(TreeNode root) {
	ArrayList<Integer> result = new ArrayList<Integer>();
	if (root == null){
	return result;
	}
	Stack<TreeNode> stack =new Stack<TreeNode> ();
	LinkedList<TreeNode> visitedList= new LinkedList<TreeNode> ();
	while(root!=null){
	stack.push(root);
	root=root.left;
	}
	while(!stack.isEmpty()){
	TreeNode current = stack.peek();
	if (current.right == null || visitedList.contains(current)){
	result.add(current.val);
	stack.pop();
	if (visitedList.contains(current)){
	visitedList.remove(current);
	}
	}
	else{
	visitedList.add(current);
	root=current.right;
	while (root!=null){
	stack.push(root);
	root=root.left;
	}
	}
	}
	return result;
	}
	}
	// Iterative Solution
	public class Solution {
	public List<Integer> postorderTraversal(TreeNode root) {
	List<Integer> result=new ArrayList<Integer>();
	if (root==null){
	return result;
	}
	Stack<TreeNode> stack=new Stack<TreeNode>();
	TreeNode runner=root;
	while (runner!=null){
	stack.push(runner);
	runner=runner.left;
	}
	// child node used to record if mid node's child has been visited inorder to tell if need to pop out
	//the mid node
	TreeNode child=null;
	while (!stack.isEmpty()){
	TreeNode current=stack.peek();
	if (current.right==null || current.right==child){
	result.add(stack.pop().val);
	// catch the child node, inorder mid node could check if its child already be visited
	child=current;
	}
	else{
	current=current.right;
	while (current!=null){
	stack.push(current);
	current=current.left;
	}
	}
	}
	return result;
	}
	}
	public class Solution {
	public List<Integer> postorderTraversal(TreeNode root) {
	List<Integer> result=new ArrayList<Integer> ();
	if (root==null){
	return result;
	}
	buildResult(root, result);
	return result;
	}
	private void buildResult(TreeNode root, List<Integer> result){
	if (root==null){
	return;
	}
	buildResult(root.left, result);
	buildResult(root.right, result);
	result.add(root.val);
	}
	}

view raw BinaryTreePostorderTrave.java hosted with ❤ by GitHub

Permutations (Java)

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

	/*
	Given a collection of numbers, return all possible permutations.
	For example,
	[1,2,3] have the following permutations:
	[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
	*/
	// Best Time O(n!)
	// space efficence solution
	public class Solution {
	public ArrayList<ArrayList<Integer>> permute(int[] num) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (num==null || num.length==0){
	return result;
	}
	// record is currenct num already be used
	boolean[] used=new boolean[num.length];
	ArrayList<Integer> current=new ArrayList<Integer>();
	int index=0;
	buildResult(num, index, current,used, result);
	return result;
	}
	public void buildResult(int[] num, int index, ArrayList<Integer> current, boolean[] used, ArrayList<ArrayList<Integer>> result){
	if (index==num.length){
	result.add(new ArrayList<Integer>(current));
	return;
	}
	for (int i=0; i<num.length;i++){
	if (!used[i]){
	current.add(num[i]);
	used[i]=true;
	buildResult(num, index+1, current, used, result);
	used[i]=false;
	current.remove(current.size()-1);
	}
	}
	}
	}
	// same time complexity with above but cost more space
	public class Solution {
	public ArrayList<ArrayList<Integer>> permute(int[] num) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (num==null || num.length==0){
	return result;
	}
	for(int i=0; i<num.length; i++){
	result=buildResult(num[i], result );
	}
	return result;
	}
	private ArrayList<ArrayList<Integer>> buildResult(int num, ArrayList<ArrayList<Integer>> result){
	if (result.isEmpty()){
	ArrayList<Integer> temp=new ArrayList<Integer>();
	temp.add(num);
	result.add(temp);
	return result;
	}
	ArrayList<ArrayList<Integer>> newResult=new ArrayList<ArrayList<Integer>> ();
	for (ArrayList<Integer> al: result){
	for (int i=0; i<=al.size(); i++){
	ArrayList<Integer> temp=new ArrayList<Integer>(al);
	temp.add(i, num);
	newResult.add(temp);
	}
	}
	return newResult;
	}
	}

view raw Permutations.java hosted with ❤ by GitHub

Minimum Path Sum (Java)

 

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

 

Apply DFS first failed on time limitation, then adopted DP with 2 dimension matrix passed OJ, finally refector code to use 1 dimension rotational array

	// Failed on time limitation, faster solution below
	public class Solution {
	public int minPathSum(int[][] grid) {
	if (grid==null || grid.length==0){
	return 0;
	}
	int[] minPath={Integer.MAX_VALUE};
	int currentX=0;
	int currentY=0;
	int lastValue=0;
	calMinPath(grid, currentX, currentY, lastValue,minPath);
	return minPath[0];
	}
	private void calMinPath(int[][] grid, int currentX, int currentY, int lastValue, int[] minPath){
	if (currentX>=grid[0].length || currentY>=grid.length){
	return;
	}
	if (currentX==grid[0].length-1 && currentY==grid.length-1){
	if (minPath[0]>lastValue+grid[currentY][currentX]){
	minPath[0]=lastValue+grid[currentY][currentX];
	}
	return;
	}
	calMinPath(grid, currentX+1, currentY, lastValue+grid[currentY][currentX], minPath);
	calMinPath(grid, currentX, currentY+1, lastValue+grid[currentY][currentX], minPath);
	}
	}
	// 2 Dimention DP Solution passed OJ
	public class Solution {
	public int minPathSum(int[][] grid) {
	if (grid==null || grid.length==0){
	return 0;
	}
	int[][] minCounter=new int[grid.length][grid[0].length];
	minCounter[0][0]=grid[0][0];
	// build first column
	for (int i=1; i<grid.length; i++){
	minCounter[i][0]=grid[i][0]+minCounter[i-1][0];
	}
	// build first row
	for (int i=1; i<grid[0].length; i++){
	minCounter[0][i]=grid[0][i]+minCounter[0][i-1];
	}
	//build minCounter
	for (int i=1; i<grid.length; i++){
	for (int j=1; j<grid[0].length; j++){
	minCounter[i][j]=Math.min(minCounter[i-1][j], minCounter[i][j-1])+grid[i][j];
	}
	}
	return minCounter[grid.length-1][grid[0].length-1];
	}
	}
	// 1 dimentional rotation array
	public class Solution {
	public int minPathSum(int[][] grid) {
	if (grid==null || grid.length==0){
	return 0;
	}
	int[] steps=new int[grid[0].length];
	// initialize the steps array
	steps[0]=grid[0][0];
	for (int col=1; col<grid[0].length; col++){
	steps[col]=steps[col-1]+grid[0][col];
	}
	// start from row 1, calculate the min path
	for (int row=1; row<grid.length; row++){
	steps[0]=steps[0]+grid[row][0];
	for (int col=1; col<grid[0].length; col++){
	// steps[col] can be regard as the up neighbor of current point in 2D matrix
	// steps[col-1] can be regard as the left neighbor of current point in 2D matrix
	steps[col]=Math.min(steps[col], steps[col-1])+grid[row][col];
	}
	}
	return steps[steps.length-1];
	}
	}

view raw MinimumPathSum.java hosted with ❤ by GitHub

Search a 2D Matrix (Java + Python)

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]
]

For an  O (rows * cols) solution is too simple to meet the interviewer’s expectation. So what is the better solution should be? Binary search should be a good tool when I face search problem, however, how BS could be apply  in matrix?   if we regard 0 as start point, total_cols*total_rows-1 as the end point to look the matrix as a array then we can apply BS. However, how could we convert the position to row_NO and col_NO?  We  know row_NO * total_cols+col_NO=position, So in programming  row_NO=postion/total_cols, col_NO=postion%total_cols. then we can adapt this feature in our program  to apply binary search to get O(log(cols+rows)) search

	/*
	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.
	*/
	public class Solution {
	public boolean searchMatrix(int[][] matrix, int target) {
	if (matrix==null || matrix.length==0){
	return false;
	}
	int start=0;
	int end=matrix.length*matrix[0].length-1;
	while (start<=end){
	int mid=start+(end-start)/2;
	int candidate=matrix[mid/matrix[0].length][mid%matrix[0].length];
	if (candidate==target){
	return true;
	}
	else if (candidate<target){
	start=mid+1;
	}
	else{
	end=mid-1;
	}
	}
	return false;
	}
	}

view raw SearchA2DMatrix.java hosted with ❤ by GitHub

	"""
	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.
	"""
	class Solution:
	# @param matrix, a list of lists of integers
	# @param target, an integer
	# @return a boolean
	def searchMatrix(self, matrix, target):
	if matrix==None or len(matrix)==0:
	return False
	start=0
	end=len(matrix)*len(matrix[0])-1
	while (start<=end):
	mid=start+(end-start)/2
	if matrix[mid/len(matrix[0])][mid%len(matrix[0])]==target:
	return True
	elif matrix[mid/len(matrix[0])][mid%len(matrix[0])]<target:
	start=mid+1
	else:
	end=mid-1
	return False

view raw SearchA2DMattix.py hosted with ❤ by GitHub

Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

	"""
	Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
	Note: You may not slant the container.
	"""
	class Solution:
	# @return an integer
	def maxArea(self, height):
	if height==None or len(height)<2:
	return 0
	left=0
	right=len(height)-1
	maxArea=0
	while left<right:
	area=min(height[left], height[right])*(right-left)
	if maxArea<area:
	maxArea=area
	if height[left]<height[right]:
	left+=1
	else:
	right-=1
	return maxArea

view raw ContainerWithMostWater.py hosted with ❤ by GitHub

	/*
	Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
	Note: You may not slant the container.
	*/
	public class Solution {
	public int maxArea(int[] height) {
	if (height==null || height.length<2){
	return 0;
	}
	int maxArea=0;
	int left=0;
	int right=height.length-1;
	// two pointers scan from two sides to middle
	while (left <right){
	int area=Math.min(height[left], height[right])*Math.abs(left-right);
	if (maxArea<area){
	maxArea=area;
	}
	// because the area is decide by the shorter edge
	// so only way to increase the area is to increase the
	// shorter edge
	if (height[left]<height[right]){
	left++;
	}
	else{
	right--;
	}
	}
	return maxArea;
	}
	}

view raw ContainerWithMostWater.java hosted with ❤ by GitHub

Remove Duplicates from Sorted Array II (Python + Java)

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

	/*
	Follow up for "Remove Duplicates":
	What if duplicates are allowed at most twice?
	For example,
	Given sorted array A = [1,1,1,2,2,3],
	Your function should return length = 5, and A is now [1,1,2,2,3].
	*/
	public class Solution {
	public int removeDuplicates(int[] A) {
	if (A==null){
	return 0;
	}
	if (A.length<3){
	return A.length;
	}
	int temp=A[1];
	int len=1;
	for(int i=2; i<A.length; i++){
	if (A[i]!=A[i-2]){
	A[len++]=temp;
	temp=A[i];
	}
	}
	A[len++]=temp;
	return len;
	}
	}

view raw RemoveDuplicatesfromSortedArrayII.java hosted with ❤ by GitHub

	"""
	Follow up for "Remove Duplicates":
	What if duplicates are allowed at most twice?
	For example,
	Given sorted array A = [1,1,1,2,2,3],
	Your function should return length = 5, and A is now [1,1,2,2,3].
	"""
	class Solution:
	# @param A a list of integers
	# @return an integer
	def removeDuplicates(self, A):
	if len(A)<3:
	return len(A)
	temp=A[1]
	length=1
	for i in range (2, len(A)):
	if A[i]!=A[i-2]:
	A[length]=temp
	length+=1
	temp=A[i]
	A[length]=temp
	length+=1
	return length

view raw RemoveDuplicatesfromSortedArrayII.py hosted with ❤ by GitHub

Spiral Matrix II ( Java + Python)

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

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

	"""
	Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
	For example,
	Given n = 3,
	You should return the following matrix:
	[
	[ 1, 2, 3 ],
	[ 8, 9, 4 ],
	[ 7, 6, 5 ]
	]
	"""
	class Solution:
	# @return a list of lists of integer
	def generateMatrix(self, n):
	if n<=0:
	return []
	# row[:] mean shallow copy each row in [[0]*n]*n
	# we cannot not use row replace row[:] here
	matrix=[row[:] for row in [[0]*n]*n]
	row_st=0
	row_ed=n-1
	col_st=0
	col_ed=n-1
	current=1
	while (True):
	if current>n*n:
	break
	for c in range (col_st, col_ed+1):
	matrix[row_st][c]=current
	current+=1
	row_st+=1
	for r in range (row_st, row_ed+1):
	matrix[r][col_ed]=current
	current+=1
	col_ed-=1
	for c in range (col_ed, col_st-1, -1):
	matrix[row_ed][c]=current
	current+=1
	row_ed-=1
	for r in range (row_ed, row_st-1, -1):
	matrix[r][col_st]=current
	current+=1
	col_st+=1
	return matrix

view raw SpiralMatrixII.py hosted with ❤ by GitHub

	Given an integer n, generate a square matrix filled with elements from 1 to n2 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) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (n<=0){
	return new int[0][0];
	}
	int [][] matrix=new int[n][n];
	int beginX=0;
	int endX=n-1;
	int beginY=0;
	int endY=n-1;
	int current=1;
	while (current<=n*n){
	for (int col=beginX; col<=endX; col++){
	matrix[beginY][col]=current++;
	}
	beginY++;
	for (int row=beginY; row<=endY; row++){
	matrix[row][endX]=current++;
	}
	endX--;
	for (int col=endX; col>=beginX; col--){
	matrix[endY][col]=current++;
	}
	endY--;
	for (int row=endY; row>=beginY; row--){
	matrix[row][beginX]=current++;
	}
	beginX++;
	}
	return matrix;
	}
	}

view raw Spiral Matrix II.java hosted with ❤ by GitHub

Set Matrix Zeros (Java and Python)

Set Matrix Zeroes

 Total Accepted: 10610 Total Submissions: 35135My Submissions

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

	# without extra space
	class Solution:
	# @param matrix, a list of lists of integers
	# RETURN NOTHING, MODIFY matrix IN PLACE.
	def setZeroes(self, matrix):
	if matrix==None or len(matrix)==0:
	return
	# use first col and row as buffer to hold a flag to check if accordinate col or row should be 0
	# before do that, declare two flag used to check if first col and row need be change to 0 at the end
	first_row_to_zero=False
	first_col_to_zero=False
	# check the if first row and first col need to be changed to 0 at end
	if matrix[0][0]==0:
	first_row_to_zero=True
	first_col_to_zero=True
	else:
	if 0 in matrix[0]:
	first_row_to_zero=True
	if len([matrix[x][0] for x in range(0, len(matrix)) if matrix[x][0]==0])>0:
	first_col_to_zero=True
	# if find a cell with 0 then set accordinate first row and col to set as a flag
	for i in range(1, len(matrix)):
	for j in range(1, len(matrix[0])):
	if matrix[i][j]==0:
	matrix[0][j]=0
	matrix[i][0]=0
	# base on the all the flag in first row and col set 0 to the cell
	for i in range (1, len(matrix)):
	for j in range(1, len(matrix[0])):
	if matrix[0][j]==0 or matrix[i][0]==0:
	matrix[i][j]=0
	# use pre-marked flag to decide if first row and col need to be changed to 0
	if first_row_to_zero:
	for i in range(0, len(matrix[0])):
	matrix[0][i]=0
	if first_col_to_zero:
	for i in range (0, len(matrix)):
	matrix[i][0]=0
	# with O(rows+cols) extra space
	class Solution:
	# @param matrix, a list of lists of integers
	# RETURN NOTHING, MODIFY matrix IN PLACE.
	def setZeroes(self, matrix):
	if matrix==None or len(matrix)==0:
	return
	cols=[False]*len(matrix[0])
	rows=[False]*len(matrix)
	for col in range(len(matrix[0])):
	for row in range(len(matrix)):
	if matrix[row][col]==0:
	cols[col]=True
	rows[row]=True
	for col in range(len(matrix[0])):
	for row in range(len(matrix)):
	if cols[col] or rows[row]:
	matrix[row][col]=0

view raw SetMatrixZeroes.py hosted with ❤ by GitHub

	public class Solution {
	public void setZeroes(int[][] matrix) {
	if (matrix==null||matrix.length==0){
	return;
	}
	boolean[] rows=new boolean[matrix.length];
	boolean[] cols=new boolean[matrix[0].length];
	for (int row=0; row<matrix.length; row++){
	for (int col=0; col<matrix[0].length; col++){
	if (matrix[row][col]==0){
	rows[row]=true;
	cols[col]=true;
	}
	}
	}
	for (int i=0; i<matrix.length; i++){
	for (int j=0; j<matrix[0].length; j++){
	if (rows[i]||cols[j]){
	matrix[i][j]=0;
	}
	}
	}
	}
	}

view raw SetMatrixZeros.java hosted with ❤ by GitHub

Pascal's Triangle II Java+Python

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

	class Solution:
	# @return a list of integers
	def getRow(self, rowIndex):
	if rowIndex<0:
	return None
	result=[0]*(rowIndex+1)
	result[0]=1
	for i in range(1,len(result)):
	result[i]=1
	for j in range(i-1, 0, -1):
	result[j]=result[j]+result[j-1]
	return result

view raw Pascal's TriangleII.py hosted with ❤ by GitHub

	/*
	Given an index k, return the kth row of the Pascal's triangle.
	For example, given k = 3,
	Return [1,3,3,1].
	Note:
	Could you optimize your algorithm to use only O(k) extra space?
	*/
	//6/2014
	public class Solution {
	public List<Integer> getRow(int rowIndex) {
	if (rowIndex<0){
	return null;
	}
	LinkedList<Integer> current=new LinkedList<Integer>();
	LinkedList<Integer> next=new LinkedList<Integer>();
	current.add(1);
	int start=0;
	while (start<rowIndex){
	current.addFirst(0);
	current.add(0);
	calculateNext(current, next);
	LinkedList<Integer> temp=next;
	next=current;
	current=temp;
	start++;
	}
	return current;
	}
	private void calculateNext(LinkedList<Integer> current, LinkedList<Integer> next){
	if (current==null){
	return;
	}
	while (current.size()>1){
	int num1=current.pop();
	int num2=current.peek();
	next.add(num1+num2);
	}
	current.clear();
	}
	}
	// 3/2014
	public class Solution {
	/*
	[
	[1],
	[1,1],
	[1,2,1],
	[1,3,3,1],
	[1,4,6,4,1]
	]
	*/
	/*
	[1,0,0,0]
	[1,1,0,0]
	[1,2,1,0]
	[1,3,3,1]
	pN=pCValue+pCLeftValue;
	*/
	public ArrayList<Integer> getRow(int rowIndex) {
	if (rowIndex<0){
	return null;
	}
	ArrayList<Integer> current=new ArrayList<Integer>();
	ArrayList<Integer> next=new ArrayList<Integer>();
	current.add(1);
	int level=0;
	while (level<rowIndex){
	level++;
	next.add(1);
	for (int i=1; i<current.size(); i++){
	next.add(current.get(i)+current.get(i-1));
	}
	next.add(1);
	current=next;
	next=new ArrayList<Integer>();
	}
	return current;
	}
	}
	// 1/2014
	public class Solution {
	public ArrayList<Integer> getRow(int rowIndex) {
	if (rowIndex<0){
	return null;
	}
	ArrayList<Integer> result=new ArrayList<Integer>(rowIndex+1);
	for (int i=0; i<=rowIndex; i++){
	result.add(0);
	}
	result.set(0, 1);
	for (int i=1; i<=rowIndex; i++){
	result.set(i, 1);
	for (int j=i-1; j>0; j--){
	result.set(j, result.get(j)+result.get(j-1));
	}
	}
	return result;
	}
	}

view raw Pascal'sTriangleII.java hosted with ❤ by GitHub

Path Sum (Java and Python)

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

	Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
	For example:
	Given the below binary tree and sum = 22,
	5
	/ \
	4 8
	/ / \
	11 13 4
	/ \ \
	7 2 1
	return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
	Definition for a binary tree node
	# class TreeNode:
	# def __init__(self, x):
	# self.val = x
	# self.left = None
	# self.right = None
	class Solution:
	# @param root, a tree node
	# @param sum, an integer
	# @return a boolean
	def hasPathSum(self, root, sum):
	if root==None:
	return False
	if root.val==sum and root.left==None and root.right==None:
	return True
	return self.hasPathSum(root.left, sum-root.val)or self.hasPathSum(root.right, sum-root.val)

view raw PathSum.py hosted with ❤ by GitHub

	Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
	For example:
	Given the below binary tree and sum = 22,
	5
	/ \
	4 8
	/ / \
	11 13 4
	/ \ \
	7 2 1
	return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public boolean hasPathSum(TreeNode root, int sum) {
	if (root==null){
	return false;
	}
	if (root.val==sum && root.left==null && root.right==null){
	return true;
	}
	return hasPathSum(root.left, sum-root.val)||hasPathSum(root.right, sum-root.val);
	}
	}

view raw PathSum.java hosted with ❤ by GitHub

Combinations (Java)

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution: a classical DFS problem, pay attention to the format of solve this question which can be apply to many other DFS problems

	/*
	Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
	For example,
	If n = 4 and k = 2, a solution is:
	[
	[2,4],
	[3,4],
	[2,3],
	[1,2],
	[1,3],
	[1,4],
	]
	Have you been asked this question in an interview?
	*/
	public class Solution {
	public ArrayList<ArrayList<Integer>> combine(int n, int k) {
	if (n<=0||k<=0){
	return null;
	}
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	int st=1;
	int num=0;
	ArrayList<Integer> subResult=new ArrayList<Integer>();
	buildResult(st, num, k, n, subResult, result);
	return result;
	}
	// DFS classical format
	private void buildResult(int start, int currentNum, int k, int n, ArrayList<Integer> subResult, ArrayList<ArrayList<Integer>> result)
	{
	if (currentNum==k){
	ArrayList<Integer> temp=new ArrayList<Integer>(subResult);
	result.add(temp);
	return;
	}
	for (int i=start; i<=n; i++){
	subResult.add(i);
	buildResult(i+1, currentNum+1, k, n, subResult, result);
	subResult.remove(subResult.size()-1);
	}
	}
	}

view raw Combinations.java hosted with ❤ by GitHub

Remove Nth Node From End of List (Java)

Given a linked list, remove the nth 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 head;
	}
	ListNode remove=head;
	ListNode last=head;
	ListNode preHead=new ListNode (-1);
	preHead.next=head;
	ListNode pre=preHead;
	while (n>1){
	if (last.next==null){
	return head;
	}
	last=last.next;
	n--;
	}
	while (last.next!=null){
	last=last.next;
	pre=pre.next;
	remove=remove.next;
	}
	pre.next=remove.next;
	return preHead.next;
	}
	}

view raw RemoveNthNodeFromEndOfList .java hosted with ❤ by GitHub

Populating Next Right Pointers in Each Node II (Java and Python)

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

Solution : The main idea actually is tree level traversal, we can just use one node called current represent current level (start from root) and two other nodes which called nextLevelHead and nextLevelEnd to record next level's left child and right child and when current node is null then exchange current and nextLevelHead until nextLevelHead is also null

	/*
	Follow up for problem "Populating Next Right Pointers in Each Node".
	What if the given tree could be any binary tree? Would your previous solution still work?
	Note:
	You may only use constant extra space.
	For example,
	Given the following binary tree,
	1
	/ \
	2 3
	/ \ \
	4 5 7
	After calling your function, the tree should look like:
	1 -> NULL
	/ \
	2 -> 3 -> NULL
	/ \ \
	4-> 5 -> 7 -> NULL
	*/
	/**
	* Definition for binary tree with next pointer.
	* public class TreeLinkNode {
	* int val;
	* TreeLinkNode left, right, next;
	* TreeLinkNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public void connect(TreeLinkNode root) {
	if (root==null){
	return;
	}
	TreeLinkNode current=root;
	TreeLinkNode nextLevelHead=null;
	TreeLinkNode nextLevelEnd=null;
	while (current!=null){
	if (current.left!=null){
	if (nextLevelHead==null){
	nextLevelHead=current.left;
	nextLevelEnd=nextLevelHead;
	}
	else{
	nextLevelEnd.next=current.left;
	nextLevelEnd=nextLevelEnd.next;
	}
	}
	if (current.right!=null){
	if (nextLevelHead==null){
	nextLevelHead=current.right;
	nextLevelEnd=nextLevelHead;
	}
	else{
	nextLevelEnd.next=current.right;
	nextLevelEnd=nextLevelEnd.next;
	}
	}
	current=current.next;
	if (current==null){
	current=nextLevelHead;
	nextLevelHead=null;
	nextLevelEnd=null;
	}
	}
	}
	}

view raw PopulatingNextRightPointersInEachNodeII.java hosted with ❤ by GitHub

	"""
	Follow up for problem "Populating Next Right Pointers in Each Node".
	What if the given tree could be any binary tree? Would your previous solution still work?
	Note:
	You may only use constant extra space.
	For example,
	Given the following binary tree,
	1
	/ \
	2 3
	/ \ \
	4 5 7
	After calling your function, the tree should look like:
	1 -> NULL
	/ \
	2 -> 3 -> NULL
	/ \ \
	4-> 5 -> 7 -> NULL
	"""
	# Definition for a binary tree node
	# class TreeNode:
	# def __init__(self, x):
	# self.val = x
	# self.left = None
	# self.right = None
	# self.next = None
	class Solution:
	# @param root, a tree node
	# @return nothing
	def connect(self, root):
	if not root:
	return
	current=root
	nextLevelHead=None
	nextLevelEnd=None
	while (current):
	if (current.left):
	if nextLevelHead:
	nextLevelEnd.next=current.left
	nextLevelEnd=nextLevelEnd.next
	else:
	nextLevelHead=current.left
	nextLevelEnd=nextLevelHead
	if (current.right):
	if nextLevelHead:
	nextLevelEnd.next=current.right
	nextLevelEnd=nextLevelEnd.next
	else:
	nextLevelHead=current.right
	nextLevelEnd=nextLevelHead
	current=current.next
	if (not current):
	current=nextLevelHead
	nextLevelHead=None
	nextLevelEnd=None

view raw PopulatingNext RightPointersInEachNodeII.py hosted with ❤ by GitHub

Palindrome Number (Java and Python)

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem

	/*
	Determine whether an integer is a palindrome. Do this without extra space.
	click to show spoilers.
	Some hints:
	Could negative integers be palindromes? (ie, -1)
	If you are thinking of converting the integer to string, note the restriction of using extra space.
	You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
	There is a more generic way of solving this problem.
	*/
	// without consider about overflow
	public boolean isPalindrome(int x) {
	if (x<0){
	return false;
	}
	int current=0;
	int y=x;
	while (y!=0){
	current=current*10+(y%10);
	y=y/10;
	}
	return current==x;
	}
	// considered overflow
	public class Solution {
	public boolean isPalindrome(int x){
	if (x<0){
	return false;
	}
	int divider=1;
	while (x/divider>=10){
	divider*=10;
	}
	while (x!=0){
	int right=x%10;
	int left=x/divider;
	if (right!=left){
	return false;
	}
	x%=divider;
	x/=10;
	divider/=100;
	}
	return true;
	}

view raw PalindromeNumber.java hosted with ❤ by GitHub

	"""
	Determine whether an integer is a palindrome. Do this without extra space.
	click to show spoilers.
	Some hints:
	Could negative integers be palindromes? (ie, -1)
	If you are thinking of converting the integer to string, note the restriction of using extra space.
	You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
	There is a more generic way of solving this problem.
	"""
	class Solution:
	# @return a boolean
	def isPalindrome(self, x):
	if x<0:
	return False
	divider=1
	while(x/divider>=10):
	divider*=10
	while(x!=0):
	left=x/divider
	right=x%10
	if left!=right:
	return False
	x%=divider
	x/=10
	divider/=100
	return True

view raw PalindromeNumber.py hosted with ❤ by GitHub

Sum Root to Leaf Numbers(Java and Python)

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

When I met this question, I intuitively come out that recursion may be a good way to solve this problem. For a recursive solution, the base case is extremely important and it is always the key point to solve a question.

Depend on my experience, for a tree question, the root==null is always a base case, another base case in this question is decided when the node is a leaf node. Then we know that we can use root.left==null && root.right==null to represent this situation and it also should be a base case here. Once I found the base cases, we can just apply the DFS to track each path from root to leaf and update the sum variable. The reason I use an array to hold the same value is because Java can only passed by value. For example, 

in a=1; void calculate(int a){ a=a+1; } System.out.println(a); // the result is still 1 , not 2 In order to track sum value of each calculation and not return the value of sum, we should use a collection or a wrapper class to hold it  

So I use an array here to hold this sum value. If you anybody has another way to solve this problem, please leave a comment for me.

	/*
	Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
	An example is the root-to-leaf path 1->2->3 which represents the number 123.
	Find the total sum of all root-to-leaf numbers.
	For example,
	1
	/ \
	2 3
	The root-to-leaf path 1->2 represents the number 12.
	The root-to-leaf path 1->3 represents the number 13.
	Return the sum = 12 + 13 = 25.
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	/*
	When I met this question, I intuitively come out that recursion may be a good way to solve this problem.
	For a recurive solution, the base case is extremly important and it is always the key point to solve a question
	Depend on my experience, for a tree quesiton, the root==null is always a base case, another base case in this question
	is decide when the node is a leaf node. Then we know that we can use root.left==null && root.right==null to represent this
	situation and it also should be a base case here.
	Once I found the base cases, we can just apply the DFS to track each path from root to leaf and update the sum
	variable.
	the reason I use a array to hold the sum value is becasue Java can only pass by value. for example
	int a=1;
	void calculate(int a){
	a=a+1;
	}
	System.out.println(a); // the result is still 1 , not 2
	So,in order to track sum value of each calculation and not return the value of sum, we should use a collection
	or a wrapper class to hold it
	So I use a arry here to hold this sum value here
	if you any boday has other way to solve this problem please leave a comments for me.
	*/
	public class Solution {
	public int sumNumbers(TreeNode root) {
	if (root==null){
	return 0;
	}
	int[] sum={0};
	int current=0;
	getSum(root,current, sum);
	return sum[0];
	}
	public void getSum(TreeNode root, int current, int[] sum){
	if (root==null){
	return;
	}
	current=current*10+root.val;
	if (root.left==null && root.right==null){
	sum[0]=sum[0]+current;
	return;
	}
	getSum(root.left, current, sum);
	getSum(root.right, current, sum);
	}
	}

view raw SumRootTOLeafNum.java hosted with ❤ by GitHub

	"""
	Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
	An example is the root-to-leaf path 1->2->3 which represents the number 123.
	Find the total sum of all root-to-leaf numbers.
	For example,
	1
	/ \
	2 3
	The root-to-leaf path 1->2 represents the number 12.
	The root-to-leaf path 1->3 represents the number 13.
	Return the sum = 12 + 13 = 25.
	"""
	# Definition for a binary tree node
	# class TreeNode:
	# def __init__(self, x):
	# self.val = x
	# self.left = None
	# self.right = None
	class Solution:
	# @param root, a tree node
	# @return an integer
	def sumNumbers(self, root):
	if not root:
	return 0
	current=0
	sum=[0]
	self.calSum(root, current, sum)
	return sum[0]
	def calSum(self, root, current, sum):
	if not root:
	return
	current=current*10+root.val
	if not root.left and not root.right:
	sum[0]+=current
	return
	self.calSum(root.left, current, sum)
	self.calSum(root.right,current, sum)

view raw SumRootToLeafNumbers.py hosted with ❤ by GitHub

Minimum Depth of Binary Tree (Python and Java)

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	//new solution write at 3/5/2014
	public class Solution {
	public int minDepth(TreeNode root) {
	if (root==null){
	return 0;
	}
	if (root.left==null && root.right==null){
	return 1;
	}
	if (root.left!=null && root.right!=null){
	return 1+Math.min(minDepth(root.left), minDepth(root.right));
	}
	if (root.left==null){
	return 1+minDepth(root.right);
	}
	return 1+minDepth(root.left);
	}
	}
	"Be care of that is the current root is empty the already added depth should -1 and return "
	"Time Complexity is O(n)"
	public class Solution {
	public int minDepth(TreeNode root) {
	if (root == null){
	return 0;
	}
	else if (root.left==null && root.right==null){
	return 1;
	}
	return minDepthHelper(root, 1);
	}
	public int minDepthHelper(TreeNode root, int depth){
	if (root==null){
	// if the current root is null, then the depth should -1 and return;
	return depth-1;
	}
	int left=minDepthHelper(root.left, depth+1);
	int right=minDepthHelper(root.right, depth+1);
	// if left ==depth mean the left node is null, so return the right
	if (left==depth){
	return right;
	}
	// if rigth==depth mean the right node is null, so return left
	if (right==depth){
	return left;
	}
	return Math.min(left,right);
	}
	}

view raw Minimum Depth of Binary Tree.java hosted with ❤ by GitHub

	"""
	Given a binary tree, find its minimum depth.
	The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
	"""
	# Definition for a binary tree node
	# class TreeNode:
	# def __init__(self, x):
	# self.val = x
	# self.left = None
	# self.right = None
	# Solution 1
	class Solution:
	def minDepth(self, root):
	if root==None:
	return 0
	if root.left==None and root.right==None:
	return 1
	depth=1
	return self.getMinDepth(root, depth)
	def getMinDepth(self, root, depth):
	if root==None:
	return depth-1
	leftDepth=self.getMinDepth(root.left, depth+1)
	rightDepth=self.getMinDepth(root.right, depth+1)
	# left side depth equal to current depth mean left side is None, so just rightDepth
	if leftDepth==depth:
	return rightDepth
	# same reason with above
	if rightDepth==depth:
	return leftDepth
	# not None for both side, we return the smalles one
	return min(leftDepth, rightDepth)
	# Solution 2
	class Solution:
	# @param root, a tree node
	# @return an integer
	def minDepth(self, root):
	if root==None:
	return 0
	if root.left==None and root.right==None:
	return 1
	if root.left!=None and root.right!=None:
	return min(self.minDepth(root.left), self.minDepth(root.right))+1
	if root.left!=None:
	return self.minDepth(root.left)+1
	return self.minDepth(root.right)+1

view raw MinimumDepthofBinaryTree.py hosted with ❤ by GitHub

Search in Rotated Sorted Array (Java+Python)

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

       

Search a item in sorted array we should think about binary search. Cause the given array has been rotated unknow times, so binary search can not be apply directly here.

       

Throgh observation we can see, no matter how a sorted array be rotated, there is

 always one side is sorted.

       

So we can pick the middle item at first and compare it with given array's leftMost and rightMost items to check which side is sorted, for given example 4, 5 , 6, 7 , 0 , 1, 2

mid is 7, leftMost is 4, rightMost is 2, because of 4<7 so we can know left side is sorted.

       

Depend on the conclusion we got above, if the given target is between 4->7, such as 6, we can just seach left side for it, otherwise we search the right side.

       

A trick situation is when duplicate exist in the array, discard the requriement of this quesiton, my         solution will also cover duplicate exist situation. 

If duplicate exist, then leftMost or rightMost item may equal to middle item, if only one of them equal to mid such as A[leftMost]==A[mid] then from leftMost to Mid should have same value. then we can only search the right side from mid to right most. If both A[rightMost] and A[leftMost] equal to A[Mid] we have to search both sides.

	"This question usually asked in an interview with two step ."
	"1, Assume the num in the array is unique"
	"2, if the num is not unique how to implement and how the complexity will going?"
	"for unique array, it is relative simple in logic, but don’t happy so earlier,"
	"this detail implementation is not easy to handle cause of the boundary case".
	"First, when looked a question about search an item in an sorted array, you first idea is apply binary search,"
	"for this question, our basic strategy is also binary search, but cause of this sorted array has been rotated,"
	"so We have to check it the num we are search is in specific range(left half or right half),"
	"because it is a sorted array before rotated,so there must a half be sorted although the array has been rotated,"
	"then we check if the num we are looing is possible in the sorted half, if it is, then search it, else,"
	"search another side."
	"the time complexity is O(lgn), because it is just a binary search with check the sorted range,"
	"the check sorted range can be did just by compare the start point and the mid point"
	public class Solution {
	public int search(int[] A, int target) {
	int begin=0;
	int end=A.length-1;
	return searchHelper(A, begin,end,target);
	}
	public int searchHelper(int[] A, int begin, int end, int target){
	if (begin>end) return -1;
	if (begin==end) {
	if (target==A[begin]){
	return begin;
	}
	else {
	return -1;
	}
	}
	int mid=(begin+end)/2;
	if (A[mid]==target) return mid;
	if(A[begin]<A[mid]){
	if (A[begin]<=target && target<A[mid]){
	return searchHelper(A,begin, mid, target);
	}
	else{
	return searchHelper(A, mid, end, target);
	}
	}
	else if (A[mid]<A[begin]){
	if (A[mid]<target && target<=A[end]){
	return searchHelper(A,mid,end, target );
	}
	else{
	return searchHelper(A, begin, mid, target);
	}
	}
	else{
	return searchHelper(A,mid+1, end, target);
	}
	}
	}
	"Then let's talk the the situation that if the array contain duplicate items"
	"In this situation, the only difference is the left point equal to mid point, under this situation , "
	"if mid point not equal to right, then we can just search the mid -> right range, or we have to search both side, "
	"example(2,2,4,6,8 and 2,2,2,4,7,8,2,2)"
	"because of the potential situation to search both side, so the time complexity is O(n) in worst case."
	public class Solution {
	public int search(int[] A, int target) {
	if(A==null ||A.length==0){
	return -1;
	}
	int st=0;
	int ed=A.length-1;
	return search(A, st, ed, target);
	}
	public int search(int[] A, int st, int ed, int target){
	if (st>ed){
	return -1;
	}
	int mid=st+(ed-st)/2;
	if (A[mid]==target){
	return mid;
	}
	if (A[st]<A[mid]){
	if (target>=A[st] && target<A[mid] ){
	return search(A, st, mid-1, target);
	}
	return search(A, mid+1, ed, target);
	}
	else if (A[st]>A[mid]){
	if (A[mid]<target && target<=A[ed]){
	return search(A, mid+1, ed, target);
	}
	return search(A, st, mid-1, target);
	}
	else{
	if (A[mid]!=A[ed]){
	return search(A, mid+1, ed, target);
	}
	else{
	int result=search(A, st, mid-1, target);
	if (result!=-1){
	return result;
	}
	return search(A, mid+1, ed, target);
	}
	}
	}
	}

view raw SearchInRotatedSortedArray.java hosted with ❤ by GitHub

	class Solution:
	# @param A, a list of integers
	# @param target, an integer to be searched
	# @return an integer
	def search(self, A, target):
	if A==None or len(A)==0:
	return -1;
	st=0;
	ed=len(A)-1
	return self.searchHelper(A, target, st, ed)
	def searchHelper(self, A, target, st, ed):
	if st>ed:
	return -1
	mid=(st+ed)/2
	if A[mid]==target:
	return mid
	if A[st]<A[mid]:
	if A[st]<=target<A[mid]:
	return self.searchHelper(A, target, st, mid-1)
	return self.searchHelper(A, target, mid+1, ed)
	elif A[st]>A[mid]:
	if A[mid]<target<=A[ed]:
	return self.searchHelper(A, target, mid+1, ed)
	return self.searchHelper(A, target, st, mid-1)
	else:
	if A[mid]!=A[ed]:
	return self.searchHelper(A, target, mid+1, ed)
	result=self.searchHelper(A, target, st, mid-1)
	if result!=-1:
	return result
	return self.searchHelper(A, target, mid+1, ed)

view raw SearchInRotatedSortedArray.py hosted with ❤ by GitHub

Trapping Rain Water (Java + Python)

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!

Solution: DP 

 To calculate the total volume is to calculate volumes can hold at each position.

 To calculate how many volumes can hold at each position is to calculate it's right bound height  and right bound height 

Current position can hold water only at the situation when the low side among both sides higher than the height at current position

If so,  use the lower one minus current height as height to multiply the width 1 is how many volumes can hold at current position

How to calculate the height of both sides for each position? We can apply DP theory to record  highest height bound can get from left to current and highest height bound can get from right to current  

HigehstLeftSideHeight so far from giving example, should be  0,1,1,2,2,2,2,3,3,3,3,3

HighestRightSideHeight so far for given example is 1,2,2,2,3,3,3,3,3,3,3,3

Then loop through giving array for each position to calculate how many volumes can hold there and update the total volume it can hold

	/*
	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.
	// To calculate the total volume is to calculate volume can hold at
	// each position.
	// To calculate how many volume can hold at each position is to calculate it's right bound height
	// and right bound height
	//Current position can hold water only at situation when the lowest side among both sides higher than the height at current position
	//if so, use the lower one minues current height as height to multily the width 1 is how many volume can hold at current position
	// How to calculate the height of both sides for each position? we can apply DP theory
	// to record hightest height bound can get from left to current and highest height bound can get from right to current
	// HigehstLeftSideHeight so far for given example should be
	// 0,1,1,2,2,2,2,3,3,3,3,3
	// HighestRightSideHeight so far for given example is
	// 1,2,2,2,3,3,3,3,3,3,3,3
	// then loop through given array for each posiiton calculate how many volume can hold there and update the total voluem it can hold
	*/
	public class Solution {
	public int trap(int[] A) {
	if (A==null ||A.length==0){
	return 0;
	}
	int[] highestLeftSoFar=new int[A.length];
	int[] highestRightSoFar=new int[A.length];
	// left->right
	for (int i=0; i<highestLeftSoFar.length; i++){
	highestLeftSoFar[i]=i==0?A[i]:Math.max(A[i], highestLeftSoFar[i-1]);
	}
	// right -> left
	for (int i=A.length-1; i>=0; i--){
	highestRightSoFar[i]=i==A.length-1?A[i]:Math.max(A[i], highestRightSoFar[i+1]);
	}
	int totalVolume=0;
	for (int i=0; i<A.length; i++){
	int height=Math.min(highestLeftSoFar[i], highestRightSoFar[i]);
	if (height>A[i]){
	height=height-A[i];
	totalVolume+=height*1;
	}
	}
	return totalVolume;
	}
	}

view raw TrappingRainWater.java hosted with ❤ by GitHub

	"""
	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!
	"""
	class Solution:
	# @param A, a list of integers
	# @return an integer
	def trap(self, A):
	if not A:
	return 0
	highestLeftSoFar=[]
	highestRightSoFar=[]
	for i in range(len(A)):
	highestLeftSoFar.append(A[i] if i==0 else max(A[i], highestLeftSoFar[-1]))
	for i in range(len(A)-1, -1, -1):
	highestRightSoFar.insert(0,A[i] if i==len(A)-1 else max(A[i], highestRightSoFar[0]))
	totalVolume=0;
	for i, currentHeight in enumerate(A):
	minSideHeight=min(highestLeftSoFar[i], highestRightSoFar[i])
	if minSideHeight>currentHeight:
	totalVolume+=(minSideHeight-currentHeight)*1
	return totalVolume

view raw TrappingRainWater.py hosted with ❤ by GitHub

Valid Parentheses ( Java + Python)

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.

	/*
	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.
	*/
	public class Solution {
	public boolean isValid(String s) {
	if (s==null || s.length()==0){
	return true;
	}
	Stack<Character> checker=new Stack<Character>();
	int i=0;
	while (i<s.length()){
	if (s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{'){
	checker.push(s.charAt(i));
	i++;
	}
	else if (s.charAt(i)==')' || s.charAt(i)==']' || s.charAt(i)=='}'){
	if (checker.isEmpty()){
	return false;
	}
	else{
	char temp=checker.peek();
	if (isPair(temp, s.charAt(i))){
	checker.pop();
	i++;
	}
	else{
	return false;
	}
	}
	}
	else{
	return false;
	}
	}
	if (checker.isEmpty() ){
	return true;
	}
	return false;
	}
	// check is given two chars are pair
	private boolean isPair(char c1, char c2){
	String validChars="()[]{}";
	int indexC1=validChars.indexOf(c1);
	int indexC2=validChars.indexOf(c2);
	if (indexC1<0||indexC2<0){
	return false;
	}
	if (indexC1+1==indexC2){
	return true;
	}
	return false;
	}
	}

view raw ValidParentheses.java hosted with ❤ by GitHub

	"""
	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.
	"""
	# rewrite at 3/2/2014
	class Solution:
	# @return a boolean
	def isValid(self, s):
	if s==None or len(s)==0:
	return True
	stack=[]
	dict={'}':'{', ']':'[',')':'('}
	for c in s:
	if c=='(' or c=='[' or c=='{':
	stack.append(c)
	elif dict[c]:
	if len(stack)==0:
	return False
	else:
	last=stack[-1]
	if dict[c]!=last:
	return False
	else:
	stack.pop()
	else:
	return False
	return len(stack)==0

view raw ValidParentheses.py hosted with ❤ by GitHub

Longest Common Prefix (Java)

Leetcode

Write a function to find the longest common prefix string amongst an array of strings.

	/*
	Write a function to find the longest common prefix string amongst an array of strings.
	*/
	// rewrite at 2/28/2014
	public class Solution {
	public String longestCommonPrefix(String[] strs) {
	if (strs==null||strs.length==0){
	return "";
	}
	if (strs.length==1){
	return strs[0];
	}
	String str=strs[0];
	for (int i=0; i<str.length(); i++){
	char c=str.charAt(i);
	for (int j=1; j<strs.length; j++){
	if (strs[j].length()==i || strs[j].charAt(i)!=c){
	return str.substring(0, i);
	}
	}
	}
	return str;
	}
	}
	// old version
	public class Solution {
	public String longestCommonPrefix(String[] strs)
	{
	if (strs.length==0) return “”;
	int index=0;
	while (index<strs[0].length())
	{
	char c=strs[0].charAt(index);
	for (int i=1; i<strs.length;i++)
	{
	// Don’t forget to also check if index out of range of other str in strs beside strs[0]
	if (index==strs[0].length()||index==strs[i].length()||strs[i].charAt(index)!=c)
	{
	return strs[0].substring(0,index);
	}
	}
	index++;
	}
	return strs[0];
	}
	}

view raw Longest common prefix.java hosted with ❤ by GitHub

Anagrams (Java)

LeetCode

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

	/*
	Given an array of strings, return all groups of strings that are anagrams.
	Note: All inputs will be in lower-case.
	*/
	public class Solution {
	public ArrayList<String> anagrams(String[] strs) {
	ArrayList<String> result=new ArrayList<String>();
	if (strs==null||strs.length==0){
	return result;
	}
	HashMap<String,ArrayList<String>> hm=new HashMap<String, ArrayList<String>>();
	for (String s:strs){
	char[] temp=s.toCharArray();
	Arrays.sort(temp);
	String tempStr=new String(temp);
	if (hm.containsKey(tempStr)){
	hm.get(tempStr).add(s);
	}
	else{
	ArrayList<String> tempList=new ArrayList<String>();
	tempList.add(s);
	hm.put(tempStr, tempList);
	}
	}
	for (ArrayList<String> list: hm.values()){
	if (list.size()>1){
	for (String str:list){
	result.add(str);
	}
	}
	}
	return result;
	}
	}

view raw Anagrams.java hosted with ❤ by GitHub

Valid Sudoku (Java)

LeetCode

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.

Solution: Helpe table

Declare 9 boolean array with length 9  separately for rows, columns and blocks and hold them in ArrayList. Because the number range of sudoku is 1-9, so each number in each row, col and block should be unique, then we can go through every position of given board, check if the number has been

Found in current row,current column  and current block. If so, return false;

*** Be careful about the index of block in blockChecker

	/*
	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 ValidSudoku {
	public boolean isValidSudoku(char[][] board) {
	if (board==null|| board.length!=9 || board[0].length!=9){
	return false;
	}
	// initialize the Checkers
	ArrayList<boolean[]> rowChecker=new ArrayList<boolean[]>();
	ArrayList<boolean[]> colChecker=new ArrayList<boolean[]>();
	ArrayList<boolean[]> blockChecker=new ArrayList<boolean[]>();
	for (int i=0; i<9; i++){
	rowChecker.add(new boolean[9]);
	colChecker.add(new boolean[9]);
	blockChecker.add(new boolean[9]);
	}
	for (int i=0; i<9; i++){
	for (int j=0; j<9; j++){
	if (board[i][j]=='.'){
	continue;
	}
	// current value, there should be a positin represented of c at each checkers
	// pay attention to the indice of block checker
	int c= board[i][j]-'1' ;
	if (rowChecker.get(j)[c]==true || colChecker.get(i)[c]==true || blockChecker.get(i/3*3+j/3)[c]==true){
	return false;
	}
	else{
	rowChecker.get(j)[c]=true;
	colChecker.get(i)[c]=true;
	blockChecker.get(i/3*3+j/3)[c]=true;
	}
	}
	}
	return true;
	}
	}

view raw ValidSudoku.java hosted with ❤ by GitHub

Path Sum II (Java)

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Solution:  DFS

Apply DFS check every possible combination, record result if meet requirement

	Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
	For example:
	Given the below binary tree and sum = 22,
	5
	/ \
	4 8
	/ / \
	11 13 4
	/ \ / \
	7 2 5 1
	return
	[
	[5,4,11,2],
	[5,8,4,5]
	]
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	// code rewrite 2/21
	public class Solution {
	public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (root==null){
	return result;
	}
	ArrayList<Integer> current=new ArrayList<Integer>();
	buildResult(root, sum, current, result);
	return result;
	}
	private void buildResult(TreeNode root,int sum, ArrayList<Integer> current, ArrayList<ArrayList<Integer>> result){
	if (root==null){
	return;
	}
	int currentVal=root.val;
	current.add(currentVal);
	if (root.left==null && root.right==null){
	if (sum-currentVal==0){
	ArrayList<Integer> temp=new ArrayList<Integer> (current);
	result.add(temp);
	}
	}
	buildResult(root.left, sum-currentVal, current, result);
	buildResult(root.right, sum-currentVal, current, result);
	current.remove(current.size()-1);
	}
	}
	public class Solution {
	public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList <Integer> current=new ArrayList<Integer>();
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	pathSumHelper(root, sum, current, result);
	return result;
	}
	public void pathSumHelper
	(TreeNode root, int sum, ArrayList<Integer> current, ArrayList<ArrayList<Integer>> result)
	{
	if (root==null){
	return;
	}
	current.add(root.val);
	int current_sum=sum-root.val;
	if (current_sum==0&& root.left==null && root.right==null){
	ArrayList<Integer> temp=new ArrayList<Integer>();
	for(int i:current){
	temp.add(i);
	}
	result.add(temp);
	}
	pathSumHelper(root.left, current_sum, current, result);
	pathSumHelper(root.right, current_sum, current, result);
	current.remove(current.size()-1);
	}
	}

view raw Path Sum II.java hosted with ❤ by GitHub

Subsets (Java)

Leetcode

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution: DFS

For  subset of a given set, it must contain a [],
So we can initialize a result with [[]] as start point.  For example, given set [1,2,3]
We can build the result from [[]]-> [[],[1]]->[[],[1],[2],[1,2]]->[[],[1],[2], [1,2], [3], [1,3], [2,3], [1, 2,3]]

	/*
	Given a set of distinct integers, S, return all possible subsets.
	Note:
	Elements in a subset must be in non-descending order.
	The solution set must not contain duplicate subsets.
	For example,
	If S = [1,2,3], a solution is:
	[
	[3],
	[1],
	[2],
	[1,2,3],
	[1,3],
	[2,3],
	[1,2],
	[]
	]
	*/
	public class Solution {
	public ArrayList<ArrayList<Integer>> subsets(int[] S) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (S==null|| S.length==0){
	return result;
	}
	Arrays.sort(S);
	// start point to build all the subsets
	ArrayList<Integer> temp=new ArrayList<Integer>();
	result.add(temp);
	for (int i=0; i<S.length; i++){
	insert(S[i], result);
	}
	return result;
	}
	private void insert(int i, ArrayList<ArrayList<Integer>> result){
	ArrayList<ArrayList<Integer>> tempResult=new ArrayList<ArrayList<Integer>> ();
	for (ArrayList<Integer> current: result){
	ArrayList<Integer> temp=new ArrayList<Integer> (current);
	temp.add(i);
	tempResult.add(temp);
	}
	result.addAll(tempResult);
	}
	}

view raw Subsets.java hosted with ❤ by GitHub