package edu.java.chap1;

import java.util.LinkedList;

/*
 * Write an algorithm such that if an element in an M*N matrix is 0, its entire row and column are set to 0.
 * 
 */

public class SetZero {
	
	public static void matrixPrint(int[][] matrix){
		System.out.println();
		for(int i =0; i < matrix.length;i++){
			for(int j = 0; j <matrix[0].length;j++){
				System.out.print(matrix[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	public static int[][] set0(int[][] arr){
		int rowL = arr[0].length;
		int columnL = arr.length;
		int[][] result = new int[columnL][rowL];
		LinkedList<Integer> list = new LinkedList<Integer>();
		
		outer:
		for(int i = 0; i<columnL; i++){
			for(int j = 0;j<rowL; j++ ){
				//System.out.println(i+" "+j);
				if(check(j,list)){
					result[i][j] = 0;
					
				}
				else if (arr[i][j] == 0){
					for(int k = 0; k<j+1;k++){
						result[i][k] = 0;
					}
					for(int k = 0;k<i+1;k++){
						result[k][j] = 0;
					}
					list.add(j);
					continue outer;
				}
				else{
					result[i][j] = arr[i][j];
				}
			}
		}
		
		return result;
	}
	
	public static boolean check(int i, LinkedList<Integer> list){
		for(int j = 0; j < list.size(); j++){
			if(i == list.get(j).intValue()){
				return true;
			}
		}
		return false;
	}
	
	public static int[][] setZero(int[][] arr){
		int[][] result = new int[arr.length][arr[0].length];
		//use two boolean[] to store the position, use O(N^2)
		return result;
	}
	
	public static void main(String[] args) {
		int[][] arr = {{1,2,3,0},{2,3,0,1},{1,2,3,4},{2,3,4,5},{0,1,2,3}};
		matrixPrint(arr);
		matrixPrint(set0(arr));
	}

}