Author |
Topic: Maximum zeros (Read 437 times) |
|
mad
Junior Member
Posts: 118
|
 |
Maximum zeros
« on: Mar 8th, 2008, 5:39pm » |
 Quote  Modify
|
You are given a NXN matrix, each element of which is either 0 or 1 with the restriction that no 0 can appear before a 1 in any row. Example-
1 0 0 0 0
1 1 0 0 0
1 0 0 0 0
0 0 0 0 0
1 1 1 1 1
Assuming the row and col indices to be zero based, you have to return the index of the row with maximum number of zero's.
Achieve:
Space- O(1)
Time- O(n)
I think a similar question has been posted before.
But, that required checking each row making it O(n^2). Can there be an O(n) solution by say checking the diagonal(not sure).
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Maximum zeros
« Reply #1 on: Mar 9th, 2008, 3:11am » |
Quote Modify
|
1: start at the top right
2: move left until you meet the first one or leave the bound of the matrix
3: if you made at least one step left save the index of the row
4: move down until you meet the first zero or leave the bounds of matrix
5: goto 2 unless you left bounds of the matrix
6: return the saved row index
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print