we need to find the amount of water stored on every bar of the histogram. For this, we need to find two values :- v1 :- the highest bar to the left - O(n) v2:- the highest bar to the right - O(n) amount of the water stored on the current bar is Res= ( minimum of the two values(v1,v2) - height of the bar ) (assuming the length & breadth of bar is unity) sum all the values of water store on individual bar Time complexity - O(n) Space Complexity - O(n)
On Thursday, 17 May 2012 11:27:44 UTC+5:30, Nik_nitdgp wrote: > > Imagine that you have an histogram stored in an array. Now imagine that > you can pour water on top of your histogram. Describe an algorithm that > computes the amount of water that remains trapped among the columns of the > graph. Clearly on the edges the water would fall off. Use the language or > the pseudocode you prefer. > > -- > Thanks & Regards > Nikhil Agarwal > B.Tech. in Computer Science & Engineering > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > On Thursday, 17 May 2012 11:27:44 UTC+5:30, Nik_nitdgp wrote: > > Imagine that you have an histogram stored in an array. Now imagine that > you can pour water on top of your histogram. Describe an algorithm that > computes the amount of water that remains trapped among the columns of the > graph. Clearly on the edges the water would fall off. Use the language or > the pseudocode you prefer. > > -- > Thanks & Regards > Nikhil Agarwal > B.Tech. in Computer Science & Engineering > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > On Thursday, 17 May 2012 11:27:44 UTC+5:30, Nik_nitdgp wrote: > > Imagine that you have an histogram stored in an array. Now imagine that > you can pour water on top of your histogram. Describe an algorithm that > computes the amount of water that remains trapped among the columns of the > graph. Clearly on the edges the water would fall off. Use the language or > the pseudocode you prefer. > > -- > Thanks & Regards > Nikhil Agarwal > B.Tech. in Computer Science & Engineering > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/SRp0wWOK_kUJ. 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.
