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 <topcode...@gmail.com> 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 <topcode...@gmail.com> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%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.
