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