CareerCup

Here is a working code in C. The complexity is of O(n).

#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
#define COL 4
#define ROW 4
using namespace std;
int main()
{
    int arr[ROW][COL]= {
                     {1,1,1,1},
                     {1,1,0,0},
                     {1,0,0,0},
                     {1,1,0,0},
                     };
                     
    int rownum;
    int i = 0, j = COL-1;
    while(i<ROW && j>0)
    {
      if(arr[i][j]==0)
      {
        j--;
        rownum=i;}
      else
      i++;
    }
    printf("%d",rownum);
    getch();
    return 0;

}

1. Find the first occurrence of 0 in the first row, let's say it's the kth element, if no 0s then k==n. This takes O(n)

2. From this element, we go down to the next row, if the kth element is 1, then we skip this row; else find the 'dividing element' in this row and we update k.

Observe that the number k will be strictly non-ascending, meaning that the updating happens for at most n-1 times, thus it gives a time complexity of O(n).

Here's a little approach I came up with using ArrayLists. I don't know if using Lists and Collections.frequency is any more or less efficient?

Byte[][] matrix = {
						   {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						   {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
						   {1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						   {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						   {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						   {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						   {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						   {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						   {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						   {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
						   {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						   {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						   {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						   };
		
		
		List<Byte> list = new ArrayList<Byte>();
		
		int r = 0, 
			 c = matrix[r].length, 
			 max = 0, location = 0;
		
		while ( r < matrix.length && c > 0 )
		{
			
			list = Arrays.asList(matrix[r]);
			Byte b = new Byte((byte) 0);
			
			if ( Collections.frequency(list, b) > max)
			{
				max = Collections.frequency(list, b);
				location = r;
			}
			r++;
			c--;
			
		}
		
		System.out.println(location);

Well this question is trivial ,
it can be solved in O(n) time ..

here is my approach
Start from the top right element
if you heat 1 then go down
if you heat zero goto left
last location is your row with max zeros ..

We can achieve this in NlogN. here is the approach

1. Start with the middlle column and look for any zeros
2. If we find zeros it means we have to look in the left half
3. If no zeros found it means we have to look on the right half
4. Now do step 1,2 and 3 untill we have only one or two columns left.

Here is the example
1--1--0--0--0
1--0--0--0--0
1--1--1--0--0
0--0--0--0--0

Now for step 1 start with 3rd column, We found zero Now take the left half i.e matrix col(1,2,3)
again we will have a look at middle column i.e. row-2 we found zero again, so now we move to left again i.e. col(1,2)
Now we can check row 1 if we found zero i.e. row with max zeros, If not look at row 2 and find zero and that is the row with max zeroes

We can achieve this in NlogN. here is the approach

1. Start with the middlle column and look for any zeros
2. If we find zeros it means we have to look in the left half
3. If no zeros found it means we have to look on the right half
4. Now do step 1,2 and 3 untill we have only one or two columns left.

Here is the example
1--1--0--0--0
1--0--0--0--0
1--1--1--0--0
0--0--0--0--0

Now for step 1 start with 3rd column, We found zero Now take the left half i.e matrix col(1,2,3)
again we will have a look at middle column i.e. row-2 we found zero again, so now we move to left again i.e. col(1,2)
Now we can check row 1 if we found zero i.e. row with max zeros, If not look at row 2 and find zero and that is the row with max zeroes

When ever there is a zero in the first column means rest are also 0.
Do linear search column wise i.e. from col1,col2 etc ... search for a 0 , Row containing first 0 will be the answer.

1. Find the first occurrence of 0 in the first row, let's say it's the kth element, if no 0s then k==n. This takes O(n)

2. From this element, we go down to the next row, if the kth element is 1, then we skip this row; else find the 'dividing element' in this row and we update k.

Observe that the number k will be strictly non-ascending, meaning that the updating happens for at most n-1 times, thus it gives a time complexity of O(n).

Here is my solution using Scala. Time complexity around N*logN.

def find(m:Array[Array[Int]]):Option[Array[Int]] = {
    def _find(m:Array[Array[Int]], range:(Int, Int) ):Option[Array[Int]] = {
      if (range._1 >= m.size) return None //out of the border
      val median = if (range._1 == range._2)  {
        range._1 //range reduced to one column
      } else { 
        range._1 + ((range._2 - range._1) / 2) //find the range median
      }
      
      val rows:Array[Array[Int]] = m.filter {(row)=>row(median) == 0} //locate rows with '0' at median position
      rows.size match {
        case notFound if (notFound == 0) => _find(m, (median+1, range._2)) //try the right side
        case one if (one == 1)=> Some(rows(0)) //found it!
        case _ =>
          if (median == 0) return Some(rows(0)) //first column
          _find(m, (range._1, median-1)) //more to explore on the left side
      }
    }
    _find(m, (0, m.size))
  }

It also handles situation when no rows with zero's. And even when all of them are zeroes :)

We can search each column and which

We can scan each column and whichever row we would find zero that would have maximum zeros in it :
So for ex :
1 1 0
1 0 0
1 0 0
In this matrix we scan first column all are 1`s so nothing happened
Then again we scan through second column and we found zero in second and third row so we output these rows as having max. no. of 0`s

How about taking every row and right shifting it until we reach (row & 1) = 1 and having this count. If a new count exceeds the previous count , maintain the new count ..

One approach that I could think of is:
- Since all one comes before the zeros, sum up all all the values in a row until zero is found.
- Hold the row number of the lowest sum.
- The lowest sum row would be the one which contains maximum zeros

Set the first row as bestRow and find the bestColumn (corresponding to left most '0').
Iterate through rest of the rows
->If this row has a '0' in column bestColumn - 1, then set this row as bestRow and find the actual bestColumn of this row (corresponding to left most '0').
At the end of the loop, bestRow is the row that you are looking for and bestColumn contains the left most '0' in that row.

Complexity O(n)

Let's see.
One approach is ->
Start from top right. Scan last column, then second last column and third last column............. and so on.......... stop as soon as you found a zero and that row should be the answer.
(This is algorithm will stop - on first successful find of zero - and will ignore other rows with maximum number of zeros)