Hello Algoose I believe the maximum space needed in the hashtable is O(max positve - (max negative value). Since the possible cumulative sum is of that order. Correct me if i am wrong
On Dec 2, 12:00 pm, Algoose chase <[email protected]> wrote: > I believe the space complexity should be O(n) since you need to store the > cumulative sum corresponding to each of the elements from the input starting > from the first element. > > > > On Wed, Dec 1, 2010 at 12:04 AM, Prims <[email protected]> wrote: > > I got the solution to use a hash table storing partial sums a[0], > > a[0]+a[1], a[0]+a[1]+a[2], etc. in a hash table, along with i > > > Whenever a collision happens, then it is the sub array from i to the > > last summand. > > > This involves O(N) Time complexity but i what is the space complexity > > in this case? > > > On Nov 30, 10:19 pm, Prims <[email protected]> wrote: > > > There is an unsorted array of positive and negative integers. I need > > > to find out maximum sub array whose sum is zero efficiently. > > > > I can able to provide an answer in O(N^2) time complexity with O(N) > > > Space Complexity > > > Can anyone know better than this? > > > -- > > 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]<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- 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.
