Click here to see the full article post
A priority queue based approach would be scalable. Especially useful for when the interviewer follows up with "what if we need the max product of 100 numbers".
@vinod23 Hi, To my surprise, I figured out that the time complexity of single scan is more than the time complexity of sorting one, which is O(nlogn), after I submitted the code. Can you explain the reason?
@vpb8262 Actually it depends on array size. Let say our linear algo takes 10n time and our sorting algo takes nlogn time. Now ,for sorting algo to be faster than linear one 10n > nlogn i.e. n >1024. Now if in the given test cases average size of array is less than 1024 then sorting algo will be faster.
@vinod23 Thanks for your reply. It also depends upon the size of array.
What if the array has only 2 elements or 1 element? I believe an error check needs to be there to validate that.
@venkat Why use a priority queue which additional space, when sorting does the same job in O(n log n) while taking scalability into consideration?
@vinod23 Why comparing 10n and nlogn? Solution 3 takes O(n) time, shouldn't we compare n and nlogn?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.