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:
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?

10 Years
Discussion Span
Last Post by invisal

What is n in this case? The number of elements in the matrix, or the width or height of the matrix? Edit: or is it the number of 1's in the matrix plus the width? That would be reasonable, depending on the graph/matrix representation.

Edit: see reply below.


Never mind, you can do it in O(n) time where you have an n by n matrix. Given any two candidates i and j, you can eliminate one of them by looking at the (i,j) entry. That's a huge hint.


Yeah. A sink exists when the kth row and column have certain properties, for some value of K where 1 <= k <= n. Let's call each number from 1 to n a "candidate" to be the value of k that is the sink.

int k=0, i=0, c=0;

    while (k < SIZE) {
        if (mat[k][i] == 1) {
            i = 0;

        if (i == SIZE-1) break;

Is this a Big O(n)?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.