@Sanjay awesome aproach frd .. --mac On Sat, Aug 20, 2011 at 3:39 PM, Sanjay Rajpal <[email protected]> wrote:
> My previous argument was wrong. > > In the worst case, within a row, you may have to traverse the whole row, > and rest other rows for just testing. Therefore O(m+n). > > But if we dont traverse the other rows once we traversed the whole row, it > can be O(n) in the best case. > > > Sanju > :) > > > > On Sat, Aug 20, 2011 at 3:04 AM, Sanjay Rajpal <[email protected]> wrote: > >> Got it in the worst case also it will be O(m+n) >> Worst case will be >> 00000001 >> 00000011 >> 00000111 >> 00001111 >> 00011111 >> 00111111 >> 01111111 >> 11111111 >> >> at each step just make one comparison and one step towards left, which in >> worst case is >> m comparisons and n increments, so final solution is O(m+n). >> >> Correct me if I am wrong. >> Sanju >> :) >> >> >> >> On Sat, Aug 20, 2011 at 3:00 AM, Shashank Gupta >> <[email protected]>wrote: >> >>> In worst case it would be O(m*n).. >>> >>> >>> >>> On Sat, Aug 20, 2011 at 3:27 PM, shady <[email protected]> wrote: >>> >>>> @Sanjay awesome solution >>>> it won't be O(n^2) in worst case, it will be O(m+n) only >>>> >>>> On Sat, Aug 20, 2011 at 3:22 PM, Sanjay Rajpal <[email protected]>wrote: >>>> >>>>> Yes, thats right. >>>>> I think we can do the following also : >>>>> >>>>> Lets us assume rows are sorted in increasing order. >>>>> >>>>> start from first row say i. Traverse the array from the end of the row >>>>> towards the beginning till 0 occurs say at position j. >>>>> now proceed to the next row i+1, check the value at i+1,j if it is 0, >>>>> go to next row i+2,j >>>>> else if its 1, then go to left till 0 occurs and store that index of 0 >>>>> and follow to the next row. >>>>> >>>>> In the worst case, it will be O(n^2), but in general its a good >>>>> approach i guess. what do u say guys ? >>>>> >>>>> Average Case O(m+n) ? >>>>> >>>>> >>>>> Sanju >>>>> :) >>>>> >>>>> >>>>> >>>>> On Sat, Aug 20, 2011 at 2:47 AM, shady <[email protected]> wrote: >>>>> >>>>>> binary search on every row which will give solution in O(m*(logn)) >>>>>> >>>>>> On Sat, Aug 20, 2011 at 3:13 PM, Sanjay Rajpal <[email protected]>wrote: >>>>>> >>>>>>> Sorry I forgot to mention that. >>>>>>> >>>>>>> Sanju >>>>>>> :) >>>>>>> >>>>>>> -- >>>>>>> You received this message because you are subscribed to the Google >>>>>>> Groups "Algorithm Geeks" group. >>>>>>> To post to this group, send email to [email protected]. >>>>>>> To unsubscribe from this group, send email to >>>>>>> [email protected]. >>>>>>> For more options, visit this group at >>>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>>>> >>>>>> >>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "Algorithm Geeks" group. >>>>>> To post to this group, send email to [email protected]. >>>>>> To unsubscribe from this group, send email to >>>>>> [email protected]. >>>>>> For more options, visit this group at >>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>>> >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To post to this group, send email to [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >>> >>> -- >>> ----------------------------------------- >>> $hashank Gupta >>> ----------------------------------------- >>> Let not a man guard his dignity, but let his dignity guard him. >>> >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- thanks --mac -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
