Row with minimum number of zeros

Row with the maximum number of 1s

Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.

Example :Input matrix

0 1 1 1

0 0 1 1

1 1 1 1  // this row has maximum 1s

0 0 0 0

Output: 2

http://www.geeksforgeeks.org/find-the-row-with-maximum-number-1s/

Row with minimum 0's

You have a matrix with 0 & 1 with rows being in sorted order. Find the row with minimum number of 1's

0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 0 1 1 1

Solution:

1. Start from row1 till you keep getting a 0, as soon as you encounter a 1 go south and use the following table

1 -> 1 similar row
1 -> 0 better row make this is as candidate for answer


1. let's run through the algorithm from row1, col4 go south as row1, col4 is 1
2. transition is 1->1 so ignore second row and go south
3. 1 -> 1 similar row ignore row3 also
4. on same logic ignore row4 also so answer is row1

Let's take another matrix and run the same algo again

0 0 1 1 1
0 0 0 1 1
0 0 0 0 1

1. first transtion on row1, col3 is 1->0 so row is better
2. now run right on row2 till you get a 1 which is row3,col4 and now go south for which the transition is 1->0 making it a better row and since this is the last row hence the final answer

Time complexity analysis
1. best case-> 0(number of rows) it's a straight down south
2. worst case -> 2 (number of rows) wherein it's a zig zag motion