Time Complexity

Question

Suppose that each row of an n x n array A consists of 1's and 0's such that in any row of A, all the 1's come before any 0's in that row. Assuming A is already in memory, what is the complexity of the most efficient algorithm for finding the row of A that contains the most 1's?

A. $O(n²)$

B. $O(logn)$

C. $O(n)$

D. $O(nlogn)$

Answer 1

---

for ( i=0, j=0 ; i<n && j< n ; )
{
    if(a[i][j])
        {j++; row = i ;}
    else
          { i++;}
}

return row;

---

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

Here, We need to return row with maximum 1's ...for above example it is, row=5th. 

---

time complexity - O(n)

Comments

Sorry for not realizing in the morning ! ..I was not really into this then..

---

yes @vijaycs, you are correct we did'nt need to check again a column if 1 is founded ! Make it as answer :)

---

chill @Debashish .. no need of sorry :)

Answer 2

Answer is O(n).

 

Idea is very simple. Start from first row, keep moving through columns till we find a 0. Now, in the rest of the rows, we only need to check from that column. It's like moving from one corner of grid to another taking either a right step or a down step.