[algogeeks] To find a rectangle of max sum
How to find the Rectangle of Max sum in a 2D matrix consisting of both +ve and -ve numbers,,, Logic needed .. No brute Force pls... --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Largest Bound rectangle in a bar graph
I think it should be O(n) which is an obvious lower bound since we need to look at each rectangle at least once. On 3/12/07, Balachander [EMAIL PROTECTED] wrote: 1. How to find the largest bound rectangle in a bar graph It seems a Google question was to solve this in O(Log n) Try any Soln..and Post it.. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: To find a rectangle of max sum
On 3/12/07, Balachander [EMAIL PROTECTED] wrote: How to find the Rectangle of Max sum in a 2D matrix consisting of both +ve and -ve numbers,,, This solution is based on a similar variant of the problem, calculating maximum contiguous sub-array in one dimension. That problem can be solved in O(n) time (time linear to the size of the input array). For an array of dimensions m x n, the rectangle of maximum sum can be computed in O(m^2 * n). The idea is as follows, (A) Along one dimension calculate the cummulative sums, That yields, For each j, CUMM[i][j] = A[1][j] + ... + A[n][j] This step calculates the CUMM[][] array in O(m * n) Having done this we can for any sub-array along this dimension answer queries of the form Sum(A[i1][j] to A[i2][j]) in O(1) time. This is required for the next step. (B) For each pair of start and end points along the precalculated dimension, perform a linear scan similar to the one dimensional version of the problem along the other dimension. The pairs enumerable will work out to O(m*m) and the sweep will be O(n). (Made possible with the help of the precalcuation in the previous step). -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: To find a rectangle of max sum
First, find a prefix-sum on each column (O(N^2)). This is done so that we can later on compute the sum of consecutive rows in O(1) complexity. Now, observe all possible row-pairs (O(N^2)), and for each pair, you can see that we can get the sum of each column in O(1) complexity. This will provide us with a feeling that you can view the contiguous rows within each row-pair as only one row per column. Thus, we have a somewhat a one-dimensional array of column sums. To find the maximum contiguous elements in one-dimensional array, there is a Kadane's algorithm which is O(N). All the steps above gives O(N^3) algorithm. -Lego On 3/12/07, Balachander [EMAIL PROTECTED] wrote: How to find the Rectangle of Max sum in a 2D matrix consisting of both +ve and -ve numbers,,, Logic needed .. No brute Force pls... -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: To find a rectangle of max sum
On 3/12/07, Balachander [EMAIL PROTECTED] wrote: How to find the Rectangle of Max sum in a 2D matrix consisting of both +ve and -ve numbers,,, Is any one aware of any theoretical lower bounds on this problem? I remember reading about this in ``Programming Pearls'' by Jon Bentley, where he had mentioned that the O(m^2 * n) bound was the best any one had done back then. I realize now that ``Programming Pearls'' are pretty outdated and was wondering if any one is aware of anything that has bettered this? -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: To find a rectangle of max sum
Another variant...(or rather wanted to say in my previous post) How do you find a maximum square of all ones in a binary matrix of 0s and 1s? --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Largest Bound rectangle in a bar graph
I give a try to start at an O(mn) algorithm (where m is the size of the longest bar) Maxrect[height][width] = --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Largest Bound rectangle in a bar graph
This problem was recently posted in a TopCoder match: http://www.topcoder.com/tc?module=Staticd1=match_editorialsd2=srm337 Checkout BuildingAdvertise problem in above editorial. On 3/12/07, Karthik Singaram L [EMAIL PROTECTED] wrote: I give a try to start at an O(mn) algorithm (where m is the size of the longest bar) Let Maxrect[i][j] denote the width of the maximum rectangle ending at the ith position of height j if(height[i] = j) Maxrect[i][j] = Maxrect[i-1][j]+1 else Maxrect[i][j] = 0 We can traverse this array to find the maximum value in O(mn) now. This may not be the best but to just get things rolling. -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Largest Bound rectangle in a bar graph
A shot at an O(nlgn) algorithm. Do a sweep line from top to bottom. Only look at the events when a new bar is introduced (this is accomplished by sorting the bars based on height). When a new bar arises, if there exist values immediately to the left and right of the bar just merge them into a new sum. This algorithm takes O(nlgn) --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Inplace sorting
On Mar 13, 12:02 am, Karthik Singaram L [EMAIL PROTECTED] wrote: Given a binary tree in an array in the standard representation with left and right nodes being stored in 2i and 2i+1 for a node at position i. Assuming that the array indices start at 1. This is how a heap is organized. I think you are looking for heapsort. Look at any standard book on data structures/algorithms viz Data structures by tanenbaum. This is an O(nlogn) algorithm How do you perform a sort of the array with constant space and O(n) time. Not possible with what you've asked for above! Heapsort/Binary-tree sort works in O(nlogn) time. However there are sorts like counting sort, radix sort that work in O(n) time because they are NOT comparison sorts! you can find them in the same book as above. You may look at Introduction to algorithms: Cormen or a book by Horowitz/ sahni. Regards, Nupul --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
