Hi Janak Thanks for your reply and good that we are exited. But if you see the problem, this approach is already known which has space complexity of O(n). But this if you are lucky that the array has numbers which are not more than n itself.
If the given array is say 1000 size and it has numbers which can be anything, say a very large number 14556543 (lets forget max storage of int/long in various programing languages). Then it will be a tough job to keep insertion in your hash table O(1). There will be lots of hash classes and if you do not chose a good hash function (which can be better found by knowing the nature of the numbers in the aray and we done know about them) you may end up with O(n) insertion time. So lets think a less space expensive method. Tanks, Veer On Jun 1, 9:57 am, janak chandarana <jac...@gmail.com> wrote: > On Mon, May 31, 2010 at 10:01 PM, souravsain <souravs...@gmail.com> wrote: > > Hi All > > > This is my first post to this community and so am exited. The problem > > is to find the no. that has maximum frequency in an array (size n) of > > integers. > > > The approach to use a hash table, itereate through array (O(n)) and > > keep inserting into hash table (O(1)) and then scan the hash table > > (O(n)) to find entry with max frequency is known. > > You don't need to scan hash table again. > Keep track of max while inserting. > Update max when ever freq of some character is more than max. > > > Not to mention that > > one more iteration is needed to find the maximum value in array so as > > to decide the sixe of hash table (to keep insertion perfectly O(N). > > > I am looking for a solution which is having O(1) space complexity. The > > best I can think of is to sort the array in O(nlogn) and then make a > > pass through the array O(n) to find one with max frequency. So here > > time complexity is O(nlogn + n). Can we have a better solution? > > > -- > > 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.
