Java / C# - Array[][] complexity task [duplicate]

Question

I'm dealing with some problematic complexity question via my university:

Program input : A n x n Array[][] that is filled with either 0 or 1.

DEFINITION: Define k as a SINK if in the k row all the values are 0, and in the k column all the values are 1 (except [k][k] itself which needs to be 0)

Program output : Is there a k number that is a SINK? If so, returnk, else return -1.

Example :

On Arr A k=3 is a SINK, on Arr B there in no SINK, so -1 is returned.

The main problem with this task is that the complexity of the program must be below O(n^2) , I have managed to solve this with that complexity, going over the oblique line summing the rows&columns. I haven't find a way to solve this with O(logn) or O(n). Also the task prevents you from using another Array[] (Due to memory complexity). Can anyone drop any light on that matter? thanks in advance!

Answer 1

Just to make explicit the answer harold links to in the OP's comments: start yourself off with a list of all n indices, S = {0, 1, .., n-1}. These are our candidates for sinks. At each step, we're going to eliminate one of them.

1. Consider the first two elements of S, say i and j.
2. Check whether A[i, j] is 1.
   • If it is, remove i from S (because the i th row isn't all 0s, so i can't be our sink )
   • If it isn't, remove j from S (because the j th column isn't all 1s, so j can't be our sink)
3. If there're still two or more elements in S, go back to Step 1.
4. When we get to the last element, say k, check whether the k th row is all zero and the k th column (other than A[k,k]) are all ones.
   • If they are, k is a sink and you can return it.
   • If they aren't, the matrix does not have a sink and you can return -1.

There are n elements in S to begin with, each step eliminates one of them and each step takes constant time, so it's O(n) overall.

You mention you don't want to use a second array. If that really is strict, you can just use two integers instead, one representing the "survivor" from the last step and one representing how far into the sequence 0, 1, .., n-1 you are.

I've never seen this algorithm before and I'm quite impressed with it's simplicity. Cheers.