Java / C # Complexity Problem - Array [] []

Question

I am dealing with a problem of problematic complexity through my university:

Program input: A nxn Array[][] , which is populated with either 0 or 1 .

DEFINITION: Define k as SINK if the row k all the values 0 and the column k all the values 1 (except [k][k] , which should be 0 )

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

Example:

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

The main problem with this task is that the complexity of the program should be lower than O(n^2) , I managed to solve this problem with such complexity by going along an inclined line, summing the columns of rows and columns. I did not find a way to solve this problem using O(logn) or O(n) . Also, the task does not allow the use of another array [] (due to memory complexity). Can anyone highlight this issue? thanks in advance!

Answer 1

Just to explicitly respond to harold links in OP comments: start with a list of all indices n , S = {0, 1, .., n-1} . These are our sink candidates. At every step we are going to eliminate one of them.

• Consider the first two elements of S , for example, i and j .
• Check that A[i, j] is 1.
  • If so, remove i from S (because the i-th line is not all 0s, so i cannot be our receiver)
  • If it is not, remove j from S (because the jth column is not all 1s, so j cannot be our receiver)
• If there are still two or more elements on S, return to step 1.
• When we get to the last element, say k , check if the kth row is zero and the kth column (except A[k,k] ) is all.
  • If they are, k is the receiver, and you can return it.
  • If this is not the case, there is no shell in the matrix, and you can return -1 .

At the beginning of S there are elements n , each step excludes one of them, and each step takes constant time, therefore O (n) as a whole.

You mentioned that you do not want to use the second array. If this is really strict, you can simply use two integers instead, one of which is the “survivor” from the last step, and one is how far in the sequence 0, 1, .., n-1.

I have never seen this algorithm before, and I am very impressed with its simplicity. Greetings.