8

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 :

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!

Improve this question
9
  • What exactly is the constraint on memory complexity? Since O(n^2) is already used, an additional O(n) should not hurt. Commented Nov 29, 2013 at 10:16
  • I have managed to solve this with O(n^2) but that is not the task's requirements. It needs to be with less than that. If you can find a way to solve this using an O(n) memory complexity (without on-time O(n^2) ) it will also be very helpful. Commented Nov 29, 2013 at 10:23
  • What is your input? 2d array of numbers? or table stored like a string? Commented Nov 29, 2013 at 10:26
  • 2D array of numbers(which are 0s or 1s) Commented Nov 29, 2013 at 10:27
  • 1
    Belongs to programmers.stackexchange.com Commented Nov 29, 2013 at 10:43

1 Answer 1

Reset to default
4

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.

Improve this answer
2
  • Seems great, thank you very much. I will go ahead and try it out ! Can you deeply explain how to solve this with two integers? Commented Nov 29, 2013 at 15:00
  • Let's call the two integers survivor and challenger. Initialize them as survivor = 0, challenger = 1. If A[survivor, challenger] == 1, then you set survivor = challenger (because survivor can't be the sink as it has a 1 in its row) and increment challenger. If A[survivor, challenger] == 0, then you just increment challenger (because challenger can't be the sink as it has a 0 in its column). When challenger == n, you're done, and the current survivor is the only possible sink, which you then verify. Commented Nov 29, 2013 at 15:24

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.