Find smallest & second smallest element in every k elements of an array with size N

Question

I am trying to find smallest and second smallest elements in k elements of a N-sized array(without sorting and min/max heap).

Using traditional approach of first starting from 0th element and finding smallest and second smallest element in first k elements and then moving start point by 1 and repeating the process works. But its complexity is O(Nk). I need a solution with complexity O(N) if possible. Any suggestions on this?

Edited after Jubobs's comment: e.g. if say array is {12, 1, 78, 90, 57, 89, 56} and k is 3, then for first k elements (12, 1, 78) smallest element will be 1 and second smallest element will be 12. For second k elements (1, 78, 90), smallest element will be 1 and second smallest element will be 78 and so on.

Following is the code snippet I have written with O(Nk) complexity:

int j=0;
while(j < input.length-k+1) {
    int i=j;
    for(i=j; i < j+k; i++) {
        if(input[i] < min) {
            min2 = min;
            min = input[i];
        } else if(input[i] > min && input[i] < min2) {
            min2 = input[i];    
        }                   
    }
}

This is not terribly different from getting just the min (or max), which been asked many, many times. — David Eisenstat, Sep 06 '15 at 16:34
Where do you promote `j` and why do you need `K` if the result is the `min` and `min2` of the whole array? — Alex Lop., Sep 06 '15 at 17:05
Look at the dynamic programming solution in http://stackoverflow.com/questions/8031939/finding-maximum-for-every-window-of-size-k-in-an-array?rq=1 — FrankM, Sep 06 '15 at 20:10

IVlad · Accepted Answer · 2015-09-06T18:12:15.680

You can use a deque that you keep sorted.

At each step, if the first element in the deque (d.front.index) is older than k steps relative to the current step, pop it (d.popFront()).

Then, while the element at the current position in the array is smaller than the last element in the deque (d.back.value), pop elements from the deque (d.popBack()).

Finally, add the current value to the end of the deque (d.pushBack()).

At each step, d.front.value will be the smallest value of [step - k + 1, step].

You can store the deque as a linked list of size k. Then you will have access to the second element in it at all times, which will be the second smallest in [step - k + 1, step]. You have to be careful if you end up with only a single element due to popping every element. In that case, the ones popped might be the second smallest for future queries. You can keep these in another list that you handle similarly to the deque, see below for an example.

This is O(n) amortized, because each element in your array will enter and leave the deque at most once. It might seem like O(nk) because you will have some nested loops, but if you think about the total number of operations, you'll see that it is actually O(n).

Pseudocode

for i = 0, i < n:
    if not d.empty and i - d.front.index >= k:
      d.popFront()
    while not d.empty and d.back.value > a[i]:
      d.popBack()

    d.pushBack({index = i, value = a[i]})

    output d.front.value as the minimum value in [i - k + 1, i]

Code for tracking the second minimum is left as an exercise.

For your example:

a = {12, 1, 78, 90, 57, 89, 56}, k = 3

d = {12}
d = {1} (12 popped, track this)
d = {1, 78} => we have to output smallest and second smallest in [0, 2].
            => smallest is always the first in the deque, so 1
            => second = min(12 [this was popped], 78) = 12
d = {1, 78, 90)
            => smallest 1, second is 78 (12 is too old now)
d = {57}
            => 1 popped for being too old, the others for being too large
            => smallest = 57, second = 78 (last popped)
d = {57, 89}
            => smallest = 57, second = 89
d = {56}
            => smallest = 56, second = 57

Basically, you keep an array for the second smallest. This will contain the popped values that aren't yet too old. These will also be sorted, but descendingly.

Example run for this approach, where d2 is the second array:

a = {12, 1, 78, 90, 57, 89, 56} 

d = {12},           d2 = {}
d = {1},            d2 = {12}
d = {1, 78},        d2 = {12}
  => output 1, 12
d = {1, 78, 90},    d2 = {} - 12 was too old
  => output 1, 78
d = {57}            d2 = {90, 78}
  => output 57, 78
d = {57, 89}        d2 = {90} - 78 too old
  => output 57, 89 (if we had 91 instead of 89, we'd have output the 90 in d2)
d = {56}            d2 = {89, 57}
  => output 56, 57

You are not counting the keeping sorted part of your algorithm — FrankM, Sep 06 '15 at 20:05
@FrankM I am. You keep them sorted by the push / pop operations, not by applying a sorting algorithm, so it's `O(n)`. — IVlad, Sep 06 '15 at 20:07

Find smallest & second smallest element in every k elements of an array with size N

1 Answers1