Spiral Matrix, Spiral Matrix II, Search a 2D Matrix, Search a 2D Matrix II, Set Matrix Zeroes, Pascal's Triangle, Pascal's Triangle II // Cici's Blog

Spiral Matrix

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

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

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

Recursive Solution

Similar to the previous solution

Subproblem is [m-2, n-2]
Corner case 1 : m/n<=0, even number of rows and columns all processed, just return
Corner case 2 : if m&&n=1, only one number is left, just add that cell
Corner case 3 : if m||n=1, only add the last (x,y) by passing in m=1, n=1

public static ArrayList<Integer> spiralOrder(int[][] matrix) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0) return new ArrayList<Integer>();
        return spiralOrder(matrix,0,0,matrix.length,matrix[0].length);
    }
    
   public static ArrayList<Integer> spiralOrder(int [][] matrix, int x, int y, int m, int n){
       ArrayList<Integer> res = new ArrayList<Integer>();
       if(m<=0||n<=0) return res;//corner case
       if(m==1&&n==1) {//菜心儿
           res.add(matrix[x][y]);
           return res;
       }
       for(int i=0;i<n-1;i++){//start from (x,y), go right until n-1
           res.add(matrix[x][y++]);
       }
       for(int i=0;i<m-1;i++){//start from (x,y), go down until m-1
           res.add(matrix[x++][y]);
       }
       if(m>1){//if >=2 rows left 
           for(int i=0;i<n-1;i++){//start from (x,y), go left until n-1
               res.add(matrix[x][y--]);
           }
       }
       if(n>1){//if >=2 columns left
           for(int i=0;i<m-1;i++){//start from (x,y), go up until m-1
               res.add(matrix[x--][y]);
           }
       }
       if(m==1||n==1)//一条线儿
           res.addAll(spiralOrder(matrix,x,y,1,1));
       else    
           res.addAll(spiralOrder(matrix,x+1,y+1,m-2,n-2));
       return res;
   }

Spiral Matrix II

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

Solution

public static int[][] generateMatrix(int n) {
		int[][] res=new int[n][n];
		if(n==0) return res;
		generateMatrix(n,0,0,1,res);
		return res;
	}
	public static void generateMatrix(int n, int x, int y, int num, int [][] res){
		if(n<=0) return;//corner case
		if(n==1) {//菜心儿
			res[x][y]=num++;
			return;
		}
		for(int i=0;i<n-1;i++){//start from (x,y), go right until n-1
			res[x][y++]=num++;
		}
		for(int i=0;i<n-1;i++){//start from (x,y), go down until n-1
			res[x++][y]=num++;
		}
		for(int i=0;i<n-1;i++){//start from (x,y), go left until n-1
			res[x][y--]=num++;
		}
		for(int i=0;i<n-1;i++){//start from (x,y), go up until n-1
			res[x--][y]=num++;
		}
		generateMatrix(n-2,x+1,y+1,num,res);
	}

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:

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

Given target = 3, return true.

Solution

public boolean searchMatrix(int[][] a, int target) {
     int row=0;
     while(row<a.length){
         int l=0,r=a[row].length-1;
         while(l<=r){
             int mid=(l+r)/2;
             if(target<a[row][mid]){
                 r=mid-1;
             }
             else if(target>a[row][mid]){
                 l=mid+1;
             }
             else return true;
         }
         row++;
     }
     return false;
 }

Search a 2D Matrix II

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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.

solution

Start from the top-right corner, and use O(m+n) to search for the result

public boolean searchMatrix(int[][] a, int target) {
    int row=0, col=a[0].length-1;
    while(row<a.length && col>=0){
    	if(target > a[row][col]) row++;
    	else if(target < a[row][col]) col--;
    	else return true;
    }
    return false;
}

Set Matrix Zeroes

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?

Inplace Solution O(1) space

public static void setZeroes(int[][] a) {
       boolean rhavezero=false;
       boolean chavezero=false;
       
       for(int i=0;i<a[0].length;i++){
           if(a[0][i]==0) {rhavezero=true; break;}
       }
       for(int i=0;i<a.length;i++){
           if(a[i][0]==0) {chavezero=true; break;}
       }
       for(int i=1;i<a.length;i++){//start from 1, to avoid a[0][0]=0 case to destroy two index rows
           for(int j=1;j<a[0].length;j++){
               if(a[i][j]==0){
                   a[i][0]=0;
                   a[0][j]=0;
               }
           }
       }
       for(int i=1;i<a[0].length;i++){
           if(a[0][i]==0){
               for(int j=1;j<a.length;j++){
                   a[j][i]=0;
               }
           }
       }
       for(int i=1;i<a.length;i++){
           if(a[i][0]==0){
               for(int j=1;j<a[0].length;j++){
                   a[i][j]=0;
               }
           }
       }
       if(rhavezero){
            for(int i=0;i<a[0].length;i++){ a[0][i]=0;}
       }
       if(chavezero){
            for(int i=0;i<a.length;i++){ a[i][0]=0;}
       }
    }

Pascal’s Triangle

Given numRows, generate the first numRows of Pascal’s triangle.
For example, given numRows = 5,
Return

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

Solution

Corner case row=1
Start from row=2, get previous list and sum up pairs [0,row-3], add 1 in two side

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> res=new ArrayList<List<Integer>>();
    if(numRows<=0) return res;
    List<Integer> rowone=new ArrayList<Integer>();
    rowone.add(1);
    res.add(rowone);
    if(numRows==1) return res;
    int row=2;
    while(row<=numRows){
        List<Integer> tmp=new ArrayList<Integer>();
        tmp.add(1); //first 
        for(int i=0;i<row-2;i++){
            tmp.add(res.get(row-2).get(i) + res.get(row-2).get(i+1));
        }
        tmp.add(1); //last
        res.add(tmp);
        row++;
    }
    return res;
}

Pascal’s Triangle II

My Submissions Question Solution
Total Accepted: 51519 Total Submissions: 174765 Difficulty: Easy
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?

Solution

Use two lists to store current and previous layer

public List<Integer> getRow(int rowIndex) {
     List<Integer> pre=new ArrayList<Integer>();
     pre.add(1);
     if(rowIndex==0) return pre;
     int row=1;
     while(row<=rowIndex){
         List<Integer> cur=new ArrayList<Integer>();
         cur.add(1); //first 
         for(int i=0;i<pre.size()-1;i++){
             cur.add(pre.get(i) + pre.get(i+1));
         }
         cur.add(1); //last
         pre=cur;
         row++;
     }
     return pre;
 }