Given a square marica of size n, which is filled with zeros and ones. Purpose: to find in the matrix or a line or column, which consists entirely of units. The algorithm must have the asymptotic complexity O (n).

Any ideas on how to approach the solution?

  • Means the matrix n x n ? - Harry
  • @Harry, well, if it is square, then there is no other way :) - marka_17
  • It was just said at @Vlad that the passage through all the elements gives O (n), so I was surprised and decided to clarify whether the number of elements is n ... - Harry

4 answers 4

Note that any 0 we encounter automatically knocks out of consideration the row and column at the intersection of which it is located. Therefore - we will catch not 1, we will catch 0.

Moving on the matrix. Only not by a frontal search, but by a snake:

 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7

Meeting 0, we must immediately memorize our coordinates in two arrays - "bad lines" and "bad columns", and then, finding ourselves on such lines and columns - skip them entirely. In addition, we should immediately jump forward to the wall from our previous turns, because this horizontal or vertical can be considered "bad."

Our matrix traveler, in addition to the coordinates, has a direction of movement - either horizontal or vertical. So, the pass must be done only then. when we go in the "horizontal mode" on a bad line and in the "vertical mode" on a bad column.

If our snake rested its forehead on the wall or in the previous round - hooray, we found the right column or row.

Extreme cases:

The matrix is ​​crammed with 0 - we catch it at the first pass horizontally by filling in the black list of columns.

The matrix is ​​crammed 1 - we catch it on the first pass, registering the whole line of 1

  • "The matrix is ​​crammed with 1 - we catch it on the first pass, registering a whole line of 1" - but you need to find all such lines, not just one - smellyshovel
  • @smellyshovel We need to find at least 1 line, and not all. - gbg
  • Oh, right. Misunderstood. - smellyshovel

In fact, if you go through the rows one by one and then the columns, the complexity of the algorithm will be O (n ^ 2).

But you can exclude that part from the algorithm that goes through all the columns. To do this, you just need to sum the values ​​by columns when the algorithm goes through each row. As a result, if some amount turns out to be equal to n , then the corresponding column consists of all units.

To implement this approach, you will need additional memory in the form of a one-dimensional array containing n elements.

  • Sorry, but you can read more? I just can’t get it, how do I get O (n) when I go through n^2 elements? - Harry
  • @Harry Something when I talked about matrices, I was thinking about one-dimensional arrays. I'll fix it now. :) - Vlad from Moscow
  • one
    Oh, yes, even if we go through the lines only, it’s still a solution per square. - marka_17
  • @ marka_17 So far nothing else comes to my mind. Maybe someone else will throw the idea. :) But in any case, you have to go through all the elements of the matrix. - Vlad from Moscow

Well, in O (n), in general, it is hard to believe ... But it is clear that, having met the first 0, this row and column can be thrown out of consideration, so in the matrix, where there will be few such rows / columns and the speed will be taller.

In the theoretical limit, if it is one - just O (n) (n checks for zeros on the first value + n checks, to make sure that there are all ones.

But generally, not having any additional information? can not believe it.

And where are the firewoods, roughly speaking? Hope that such an algorithm can exist?

    Of course, I apologize, but entering the source data is already O (n ^ 2), even if you think up something for O (n), it’s still a square with input, but without input, the task has no meaning. Maybe n in the task is not the order of the matrix, but the number of elements (ie, for example, the 3x3 matrix, n = 9)? Then it was more logical b.

    UPD

    Well, by the way, you can solve for O (n) if you do not take into account the input matrix. Let's get x, y arrays of length n in which will be true if the row / column is completely one. When entering the matrix, if a [i] [j] == 0 then mark x [i] = False, y [j] = False. And then we will then have to go through the x, y arrays that take exactly linear time and find any element equal to True.