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?

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.

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.

Given any two candidates i and j

You mean like indexes?

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) {
c++;
if (mat[k][i] == 1) {
k++;
i = 0;
continue;
}

if (i == SIZE-1) break;
i++;
}``````

Is this a Big O(n)?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.