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