1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

homework at complexity

Discussion in 'Java' started by Noam, Jun 4, 2010.

  1. Noam

    Noam New Member

    Joined:
    Jun 4, 2010
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    hey, just got this assignment at complexity:
    input is a nXn array, filled with 0's and 1's.
    need to find "sink" - a 'k' row filled entirely with 0's, a 'k' column filled with 1's, except for (k,k) which is 0.
    the method is called using
    public int isSink(int[][] mat)
    returns 'k' is there is one, -1 if false.
    Code:
    0 [COLOR="DarkOrange"]1[/COLOR] 1 0
    [COLOR="DarkOrange"]0 0 0 0[/COLOR]
    1 [COLOR="DarkOrange"]1[/COLOR] 1 0
    0 [COLOR="DarkOrange"]1[/COLOR] 0 0
    returns 1
    
    this is my solution:
    Code:
    	public int isSink (int[][] mat) {
    		//int found = -1;
    		int i,j;
    		for (i = 0;i<mat.length;i++) {
    			boolean flag = true;
    			if (mat[i][i] == 0 && mat[i][0] == 0 && (mat[0][i] == 1 || i == 0)) {
    				for (j = 0;flag && j < mat.length;j++) {
    					if (mat[i][j] !=0)
    						flag = false;
    					else if (mat[j][i] != 1)
    						if (j!=i)
    							flag = false;
    				}
    				if (flag) return i;
    			}
    			
    		}
    		return -1;
    	}
    
    however, the teacher told us to make it with complexity of O(n), and i can't make it any less than O(n^2)
    any help?
     

Share This Page