Hi!

I have this really difficult homework assignment. I don't want answers, just perhaps a point in the right direction...I gave this a lot of thought and still nothing :(

I need to find what's called a "sink" in a matrix of all 1s or 0s.

A "sink" is when the Kth row is all 0s and the Kth column is all 1s (aside of mat[k][k] which is 0.

For example:

Mat:

1 0 1 1 0

0 1 1 0 1

0 0 0 0 0

1 0 1 1 1

0 1 1 0 0

This matrix has a "sink" because row 2 is all 0s and column 2 is all 1s (aside from Mat[2][2] which is 0)

Now here's the tricky part:

The algorithm must be of complexity of Big O(n) and not Big O(n²)...

Can some one point me in the right direction here?