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.

this is my solution:

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?

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 1 1 0 0 0 0 0 1 1 1 0 0 1 0 0 returns 1

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; }

any help?