Still incomplete. In summary we go in the following order 1) Positive product (3 largest positives or largest positive and 2 smallest negative numbers) 2) ZERO 3) Negative product (3 largest negatives or largest negative and 2 smallest positive)
I am not sure if we can find the largest k of n numbers of O(n) for the simple reason that we'd have to maintain sorted list of k elements. If the list exhibits O(1) insertion then we can do each insertion with O(log k) complexity. We would be able to do the same using max heap (for finding smallest k element) or min heap (for finding greatest k elements). Not writing a loop and maintaining k locals would entail the same complexity if not more. @Dufus: Does your approach find k largest / smallest elements in O(n) time and O(1) space complexity? On Mon, Sep 14, 2009 at 10:49 AM, Ramaswamy R <ramaswam...@gmail.com> wrote: > We probably missed just one case here. All numbers being negative, in which > case the ans would be the product of the greatest 3 negative numbers. > > > On Sun, Sep 13, 2009 at 10:10 AM, Dave <dave_and_da...@juno.com> wrote: > >> >> The following assumest that n >= 5. Find the 3 largest positive >> numbers and the two largest-in-magnitude negative numbers (i.e., the >> two smallest signed numbers). >> >> If there are not two negative numbers, the 3 largest positive numbers >> are the answer. >> >> Otherwise, if there are only one or two positive numbers, the largest >> positive number and the two largest-in-magnitude negative numbers are >> the answer. >> >> Otherwise, compare the product of the three largest positive numbers >> with the product of the largest positive number and the two largest-in- >> magnitude negative numbers. The answer is whichever set produces the >> largest product. >> >> If the product of the answer set is zero, the answer will not be >> uniquely determined. >> >> This can be done in O(n) time and O(1) extra space. >> >> Dave >> >> On Sep 13, 8:34 am, SP Praveen <praveen.sel...@gmail.com> wrote: >> > Given an array of integers (signed integers), find three numbers in >> > that array which form the maximum product. >> >> >> > > > -- > Yesterday is History. > Tomorrow is a Mystery. > Today is a Gift! That is why it is called the Present :). > > http://sites.google.com/site/ramaswamyr > -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~---------~--~----~------------~-------~--~----~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
