Finding second maximum in an array in most efficient way

Question

I am trying to find the second maximum in an array in the most efficient way both in terms of space and time complexity, but I have two major problems:

1. Time Complexity:

The naive or brute force approach will take two passes to find the smallest element so O(n) complexity, If I sort the array then it would take O(n²).

2. Space Complexity:

I can always use BST for O(log(n)) sorting but they will require additional space for maintaining a tree, I can also create a heap and do two deletes and I would get the second largest element but here also heap is created and stored in memory.

What options do I have here?

I think the brute force attempt would take a single pass if you store the smallest and second smallest element encountered - still technically O(n) I suppose though — Prescott, Sep 28 '13 at 08:39
Related: [How can we find second maximum from array efficiently?](http://stackoverflow.com/questions/2392689/how-can-we-find-second-maximum-from-array-efficiently) — anatolyg, Sep 28 '13 at 08:49

score 5 · Accepted Answer · answered Sep 28 '13 at 08:40

5

You can do this in one pass. Just keep two variables, the max and the 2nd max. Each time you update the max the old max becomes the new 2nd max.

This generalizes to a Top-k algorithm, where you can find the k largest (or smallest) elements using one pass and O(k) space. In your case k=2.

answered Sep 28 '13 at 08:40

Adam

16,808
7
52
98

Okay, I got it thanks. But can I further improve it I means in logn? – Mr_Hmp Sep 28 '13 at 08:41
@Charlie - Only by sorting first, which has additional overhead, as you noted in your question. Generally, sorting is only needed if you will be doing searches/accessing the list in a specific order multiple times. – Clockwork-Muse Sep 28 '13 at 08:43
time or space logn? This is O(1) space for k=2. – Adam Sep 28 '13 at 08:43
1

If you sort then this becomes O(1) time. Just look at the 2nd to last element. – Adam Sep 28 '13 at 08:44
Sorting takes O(nlogn) in time. – ChronoTrigger Sep 28 '13 at 08:44
Yes, I should have said "if your elements are already sorted". – Adam Sep 28 '13 at 08:46

Joni · Answer 2 · 2013-09-28T08:53:35.903

Finding the nth largest item in a list is called a selection problem, and there are many algorithms for solving it. http://en.wikipedia.org/wiki/Selection_algorithm

The lis lowest complexity you can achieve is O(n) since you need to look at every item of the list at least once. For example, finding the top k items from a list of n can be done in O(kn) time using a partial insertion sort (walk through the list and keep track of the top k elements).

There is an algorithm called quickselect that finds the top k items in O(n) time, independently of k. I recommend looking it up, but for finding the top 2 the simple approach that scans through the list once is enough.

Thanks for that mention of Quickselect. It has become a task on [Rosetta Code](http://rosettacode.org/wiki/Quickselect_algorithm), where there are already examples of the algorithm in Python, Perl 6, and Tcl. — Paddy3118, Sep 29 '13 at 07:05

Finding second maximum in an array in most efficient way

1. Time Complexity:

2. Space Complexity:

2 Answers2