Finding second largest element in sliding window

Question

So given an array and a window size, I need to find the second largest in every window. Brute force solution is pretty simple, but I want to find an efficient solution using dynamic programming

The brute force solution times out when I try it for big arrays, so I need to find a better solution. My solution was to find the second greatest in each sliding window by sorting them and getting the second element, I understand that some data structures can sort faster, but I would like to know if there are better ways.

Answer 1

There are many ways that you can solve this problem. Here are a couple of options. In what follows, I'm going to let n denote the number of elements in the input array and w be the window size.

Option 1: A simple, O(n log w)-time algorithm

One option would be to maintain a balanced binary search tree containing all the elements in the current window, including duplicates. Inserting something into this BST would take time O(log w) because there are only w total elements in the window, and removing an element would also take time O(log w) for the same reason. This means that sliding the window over by one position takes time O(log w).

To find the second-largest element in the window, you'd just need to apply a standard algorithm for finding the second-largest element in a BST, which takes time O(log w) in a BST with w elements.

The advantage of this approach is that in most programming languages, it'll be fairly simple to code this one up. It also leverages a bunch of well-known standard techniques. The disadvantage is that the runtime isn't optimal, and we can improve upon it.

Option 2: An O(n) prefix/suffix algorithm

Here's a linear-time solution that's relatively straightforward to implement. At a high level, the solution works by splitting the array into a series of blocks, each of which has size w. For example, consider the following array:

31  41  59  26  53  58  97  93  23  84  62  64  33  83  27  95  02  88  41  97

Imagine that w = 5. We'll split the array into blocks of size 5, as shown here:

31  41  59  26  53 | 58  97  93  23  84 | 62  64  33  83  27 | 95  02  88  41  97

Now, imagine placing a window of length 5 somewhere in this array, as shown here:

31  41  59  26  53 | 58  97  93  23  84 | 62  64  33  83  27 | 95  02  88  41  97
                             |-----------------|

Notice that this window will always consist of a suffix of one block followed by a prefix of another. This is nice, because it allows us to solve a slightly simpler problem. Imagine that, somehow, we can efficiently determine the two largest values in any prefix or suffix of any block. Then we could find the second-max value in any window as follows:

• Figure out which blocks' prefix and suffix the window corresponds to.
• Get the top two elements from each of those prefixes and suffixes (or just the top one element, if the window is sufficiently small).
• Of those (up to) four values, determine which is the second-largest and return it.

With a little bit of preprocessing, we can indeed set up our windows to answer queries of the form "what are the two largest elements in each suffix?" and "what are the two largest elements in each prefix?" You can kinda sorta think of this as a dynamic programming problem, set up as follows:

• For any prefix/suffix of length one, store the single value in that prefix/suffix.
• For any prefix/suffix of length two, the top two values are the two elements themselves.
• For any longer prefix or suffix, that prefix or suffix can be formed by extending a smaller prefix or suffix by a single element. To determine the top two elements of that longer prefix/suffix, compare the element used to extend the range to the top two elements and select the top two out of that range.

Notice that filling in each prefix/suffix's top two values takes time O(1). This means that we can fill in any window in time O(w), since there are w entries to fill in. Moreover, since there are O(n / w) total windows, the total time required to fill in these entries is O(n), so our overall algorithm runs in time O(n).

As for space usage: if you eagerly compute all prefix/suffix values throughout the entire array, you'll need to use space O(n) to hold everything. However, since at any point in time we only care about two windows, you could alternatively only compute the prefixes/suffixes when you need them. That will require only space O(w), which is really, really good!

Option 3: An O(n)-time solution using clever data structures

This last approach turns out to be totally equivalent to the above approach, but frames it differently.

It's possible to build a queue that allows for constant-time querying of its maximum element. The idea behind this queue - beginning with a stack that supports efficient find-max and then using it in the two-stack queue construction - can easily be generalized to build a queue that gives constant-time access to the second-largest element. To do so, you'd just adapt the stack construction to store the top two elements at each point in time, not just the largest element.

If you have a queue like this, the algorithm for finding the second-max value in any window is pretty quick: load the queue up with the first w elements, then repeatedly dequeue an element (shift something out of the window) and enqueue the next element (shift something into the window). Each of these operations takes amortized O(1) time to complete, so this takes time O(n) overall.

Fun fact - if you look at what this queue implementation actually does in this particular use case, you'll find that it's completely equivalent to the above strategy. One stack corresponds to suffixes of the previous block and the other to prefixes of the next block.

This last strategy is my personal favorite, but admittedly that's just my own data structures bias.

Hope this helps!

Answer 2

So just take a data structure as like as set which stores the data orderly. like if you store 4 2 6 on the set it will store as 2 4 6.

So what will be the algorithm:

Let,

Array = [12,8,10,11,4,5] window size =4

first window= [12,8,10,11] set =[8,10,11,12]

How to get the second highest:
- Remove the last element from the set and store in a container. set=[8,10,11],contaniner = 12
- After removing, current last element of the set is the second largest of the current window.
- Again put the removed element stored in the container to the set,set=[8,10,11,12]
Now shift your window, - delete 12 from the set and add 4.
- Now you will get the new window and set.
- check like the similar process.
Complexity of removing and adding element in a set is about log(n).

One tricks:

If you always want to store the data in decreasing order, then you can store the data by multiplying it by -1. And when you pop up the data, use it by multiplying it by -1.

Answer 3

We can use a double ended queue for an O(n) solution. The front of the queue will have larger (and earlier seen) elements:

  0  1  2  3  4  5
{12, 8,10,11, 4, 5}
window size: 3

i   queue (stores indexes)
-   -----
0   0
1   1,0
2   2,0 (pop 1, then insert 2)
output 10
remove 0 (remove indexes not in
   the next window from the front of
   the queue.)
3   3 (special case: there's only one
   smaller element in queue, which we
   need so keep 2 as a temporary variable.)
output 10
4   4,3
output 10
remove 2 from temporary storage
5   5,3 (pop 4, insert 5)
output 5

The "pop" and "remove from front" are while A[queue_back] <= A[i] and while queue_front is outside next window respectively (the complication of only one smaller element left represented in the queue notwithstanding). We output the array element indexed by the second element from the front of the queue (although our front may have a special temporary friend that was once in the front, too; the special friend is dumped as soon as it represents an element that's either outside of the window or smaller than the element indexed by the second queue element from the front). A double ended queue has complexity O(1) to remove from either front or back. We insert in the back only.

Per templatetypedef's request in the comments: "how you determine which queue operations to use?" At every iteration, with index i, before inserting it into the queue, we (1) pop every element from the back of the queue that represents an element in the array smaller than or equal to A[i], and (2) remove every element from the front of the queue that is an index outside the current window. (If during (1), we are left with only one smaller or equal element, we save it as a temporary variable since it is the current second largest.)

Answer 4

There is a relatively simple dunamic programming O(n^2) solution: Build the classic pyramid structure for aggregate value over a subset (the one where you combine the values from the pairs below to make each step above), where you track the largest 2 values (and their position), then simply keep the largest 2 values of the 4 combined values (which is less in practise due to overlap, use the position to ensure they are actually different). You then just read off the second largest value from the layer with the correct sliding window size.