Re: [algogeeks] Find a specific number in a special matrix.
@MAC ur solution is wrong 1 9 24 2 12 33 3 16 49 search for 3 O(logn) solution let the matrix be A[][] and number to be searched is x divide the array from middle in 4 parts lets say it four quadrants now check if xA[n/2][n/2] search in bottom right quadrant if xA[n/2][n/2] search in other 3 quadrants On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.com wrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. Thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find a specific number in a special matrix.
I think if x a[n/2][n/2] than we need to search in 1st quadrant otherwise in others. On Wed, Jan 5, 2011 at 7:20 PM, sourabh jakhar sourabhjak...@gmail.comwrote: aditya solution is correct it is a standard question of young tabuleau it is complexity is log(n) On Wed, Jan 5, 2011 at 6:52 PM, ADITYA KUMAR aditya...@gmail.com wrote: @MAC ur solution is wrong 1 9 24 2 12 33 3 16 49 search for 3 O(logn) solution let the matrix be A[][] and number to be searched is x divide the array from middle in 4 parts lets say it four quadrants now check if xA[n/2][n/2] search in bottom right quadrant if xA[n/2][n/2] search in other 3 quadrants On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.com wrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. Thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers Naveen Kumar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find a specific number in a special matrix.
@ankit thanks for correcting @naveen yeah that will make it more precise On Wed, Jan 5, 2011 at 7:51 PM, Ankit Babbar ankitbabba...@gmail.comwrote: @ Aditya: Mac's Solution works correctlyfor your example: Start from 24(top right)..245: go left;95: go left; 13: go down; 23:go down: 3 found..:) On Wed, Jan 5, 2011 at 7:37 PM, Naveen Kumar naveenkumarve...@gmail.comwrote: I think if x a[n/2][n/2] than we need to search in 1st quadrant otherwise in others. On Wed, Jan 5, 2011 at 7:20 PM, sourabh jakhar sourabhjak...@gmail.comwrote: aditya solution is correct it is a standard question of young tabuleau it is complexity is log(n) On Wed, Jan 5, 2011 at 6:52 PM, ADITYA KUMAR aditya...@gmail.comwrote: @MAC ur solution is wrong 1 9 24 2 12 33 3 16 49 search for 3 O(logn) solution let the matrix be A[][] and number to be searched is x divide the array from middle in 4 parts lets say it four quadrants now check if xA[n/2][n/2] search in bottom right quadrant if xA[n/2][n/2] search in other 3 quadrants On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.comwrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. Thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers Naveen Kumar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Ankit Babbar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find a specific number in a special matrix.
Either x is greater or less than the middle vale you have to search 3 quardant. Because the value could be in bottom left or top tight. On Jan 5, 2011 7:14 AM, ADITYA KUMAR aditya...@gmail.com wrote: @ankit thanks for correcting @naveen yeah that will make it more precise On Wed, Jan 5, 2011 at 7:51 PM, Ankit Babbar ankitbabba...@gmail.com wrote: @ Aditya: Mac's Solution works correctlyfor your example: Start from 24(top right)..245: go left; 95: go left; 13: go down; 23:go down: 3 found..:) On Wed, Jan 5, 2011 at 7:37 PM, Naveen Kumar naveenkumarve...@gmail.com wrote: I think if x a[n/2][n/2] than we need to search in 1st quadrant otherwise in others. On Wed, Jan 5, 2011 at 7:20 PM, sourabh jakhar sourabhjak...@gmail.com wrote: aditya solution is correct it is a standard question of young tabuleau it is complexity is log(n) On Wed, Jan 5, 2011 at 6:52 PM, ADITYA KUMAR aditya...@gmail.com wrote: @MAC ur solution is wrong 1 9 24 2 12 33 3 16 49 search for 3 O(logn) solution let the matrix be A[][] and number to be searched is x divide the array from middle in 4 parts lets say it four quadrants now check if xA[n/2][n/2] search in bottom right quadrant if xA[n/2][n/2] search in other 3 quadrants On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.com wrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. Thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers Naveen Kumar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Ankit Babbar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to
Re: [algogeeks] Find a specific number in a special matrix.
For n x m take first element of all the rows and insert in a min heap. Now take the smallest element and and if we have a track of from which row it belongs, we can take an element out of that row and insert in the heap. this will be done n x m times. Hence we have a time complexity of O(nmlog(m)) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find a specific number in a special matrix.
Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 *In how much time we can sort the elements of this matrix ? As far as i m getting idea that if we have n*n elements then we can sort it in n^3 time*. It can be done as--- 1) The left top element is the smallest one . remove it from the matrix.(Store it somewhere) 2)Ask from it's right or down element to be present at this new blank position (Just like the heap sorting). keep on doing step 2 unless the blank reaches the n*m position. Again repeat the step 1 and 2 unless thr is no element left in matrix. On Sat, Dec 25, 2010 at 9:14 AM, yq Zhang zhangyunq...@gmail.com wrote: @mac, Nice solution! On Fri, Dec 24, 2010 at 7:13 PM, MAC macatad...@gmail.com wrote: move from top rightmost column , go down if the number being searched is greater or left if the number being seracehd is small .. O(m+n) if u wanted to search 5 , u start from 3 (top right) , and since 53 , u go down to 4 , then 5 4 so go down , u reach 6 . now 5 6 so u will need to go left .. till u find 5 or less than 5 hope this helps regards --mac On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.com wrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. Thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find a specific number in a special matrix.
But if we sort n*n elements directly using quick sort, the expected sorting time is only n*n*log(n*n) n^3. On Sat, Dec 25, 2010 at 9:19 AM, monty 1987 1986mo...@gmail.com wrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 *In how much time we can sort the elements of this matrix ? As far as i m getting idea that if we have n*n elements then we can sort it in n^3 time*. It can be done as--- 1) The left top element is the smallest one . remove it from the matrix.(Store it somewhere) 2)Ask from it's right or down element to be present at this new blank position (Just like the heap sorting). keep on doing step 2 unless the blank reaches the n*m position. Again repeat the step 1 and 2 unless thr is no element left in matrix. On Sat, Dec 25, 2010 at 9:14 AM, yq Zhang zhangyunq...@gmail.com wrote: @mac, Nice solution! On Fri, Dec 24, 2010 at 7:13 PM, MAC macatad...@gmail.com wrote: move from top rightmost column , go down if the number being searched is greater or left if the number being seracehd is small .. O(m+n) if u wanted to search 5 , u start from 3 (top right) , and since 53 , u go down to 4 , then 5 4 so go down , u reach 6 . now 5 6 so u will need to go left .. till u find 5 or less than 5 hope this helps regards --mac On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.comwrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. Thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Find a specific number in a special matrix.
Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. Thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find a specific number in a special matrix.
move from top rightmost column , go down if the number being searched is greater or left if the number being seracehd is small .. O(m+n) if u wanted to search 5 , u start from 3 (top right) , and since 53 , u go down to 4 , then 5 4 so go down , u reach 6 . now 5 6 so u will need to go left .. till u find 5 or less than 5 hope this helps regards --mac On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.com wrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. Thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find a specific number in a special matrix.
@mac, Nice solution! On Fri, Dec 24, 2010 at 7:13 PM, MAC macatad...@gmail.com wrote: move from top rightmost column , go down if the number being searched is greater or left if the number being seracehd is small .. O(m+n) if u wanted to search 5 , u start from 3 (top right) , and since 53 , u go down to 4 , then 5 4 so go down , u reach 6 . now 5 6 so u will need to go left .. till u find 5 or less than 5 hope this helps regards --mac On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.com wrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. Thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
