Re: [algogeeks] matrix question ???!!!!!!!!!!??????????
>>> it can be done in O(3n). in worst case one row will have max and anothr >>> row >>> will have min so the third row will be your o/p to print Why is that? The min/max element can occur in every row: 1 4 2 10 2 1 10 4 2 3 4 5 1 2 8 10 ? Besides that, you need to scan the whole array to find the min/max value in the matrix. On 08/14/2011 12:20 PM, shady wrote: no it is 3*n only read it again On Mon, Aug 15, 2011 at 12:45 AM, Amir Aavani wrote: On 08/14/2011 11:46 AM, aditya kumar wrote: it can be done in O(3n). in worst case one row will have max and anothr row will have min so the third row will be your o/p to print Do you mean O(n^3)? Consider this { O(n^2) }: 1- Scan the whole matrix and find minimum and maximum entries in the matrix. Let Delta be the difference between maximum and minimum. 2- For each row, find the minimum and maximum entries in that row. If their difference is exactly Delta, then print that row. Amir On Mon, Aug 15, 2011 at 12:00 AM, Karthikeyan palani< karthikeyan...@gmail.com> wrote: sorry O(n^2) s the time complexity On 14 August 2011 23:56, shady wrote: how can it be O(n) when there are itself n*n elements.. PS : no sharing of code, else the inevitable On Sun, Aug 14, 2011 at 11:51 PM, Karthikeyan palani< karthikeyan...@gmail.com> wrote: Given a n x n matrix. .number are randomly placed. .print any one row which doesn’t have min and max elements. Time Complexity : 0(n) if anyone know the code.. pls share!!! -- karthikeyankkn -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.com . For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=en<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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.com . For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en> . -- karthikeyankkn -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.com . For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=en<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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en<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 algogeeks@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] matrix question ???!!!!!!!!!!??????????
On 08/14/2011 11:46 AM, aditya kumar wrote: it can be done in O(3n). in worst case one row will have max and anothr row will have min so the third row will be your o/p to print Do you mean O(n^3)? Consider this { O(n^2) }: 1- Scan the whole matrix and find minimum and maximum entries in the matrix. Let Delta be the difference between maximum and minimum. 2- For each row, find the minimum and maximum entries in that row. If their difference is exactly Delta, then print that row. Amir On Mon, Aug 15, 2011 at 12:00 AM, Karthikeyan palani< karthikeyan...@gmail.com> wrote: sorry O(n^2) s the time complexity On 14 August 2011 23:56, shady wrote: how can it be O(n) when there are itself n*n elements.. PS : no sharing of code, else the inevitable On Sun, Aug 14, 2011 at 11:51 PM, Karthikeyan palani< karthikeyan...@gmail.com> wrote: Given a n x n matrix. .number are randomly placed. .print any one row which doesn’t have min and max elements. Time Complexity : 0(n) if anyone know the code.. pls share!!! -- karthikeyankkn -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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. -- karthikeyankkn -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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] AMAZON Q
Here is an algorithm which solves this problem in O(nlog^2 n): Create a set of pairs B= {: i= 1..n}. Sort B. Now use the following Divide and Conquer algorithm (Ar_Low is a global array): Fill (Start, End, Low_Array) if Start= End then Low_Array [Start]= 0 else Initialize Low_Array with zero. Fill (Start, (Start+ End)/ 2, Low_Array) Fill ((Start+ End)/ 2+ 1, End, Low_Array) Scan B (the list of sorted pairs) and select the pairs whose second value is in range (End/ 2+ 1, End), call the resulting list B' For each i in (Start, (Start+ End)/ 2): Lets j be the position of arr [i] in B' Set Low_Array [i]= Low_Array [i]+ j The running time of this algorithm is: n\log n for sorting B+ T(n)= 2T(n/2)+ n\log n => T(n)= n\log^2 n So, the total running time is: n\log^2 n . Amir On 07/26/2011 06:48 AM, Piyush Sinha wrote: You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create another array ar_low[] such that ar_low[i] = number of elements lower than or equal to ar[i] in ar[i+1:n-1]. So the output of above should be {0,2,1,2,2,1,0} Time complexity : O(nlogn) use of extra space allowed. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.