# homework at complexity

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

1. ### NoamNew Member

Joined:
Jun 4, 2010
Messages:
2
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 && (mat[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?