Highest value of last k values in array, better than O(n^2)

Question

I have an array of n elements and for each element I'm trying to find the highest value from the last k values (including the current value)? E.g. given k,

int[] highestValues = new int[arr.Length];
for (int i = k - 1; i < arr.Length; i++)
{
    int highest = Int32.MinValue;
    for (int j = i - k; j <= i; j++)
    {
        highest = Math.Max(highest, arr[j]);
    }
    highestValues[i] = highest;
}

It appears the complexity of this algorithm is O(n^2). I was wondering if there was any way to do it quicker, e.g. rather than comparing k numbers in the inner loop, reuse the result from the previous operation.

Also, the way your code is now, j goes below 0 and there's an error — Menelaos, Jan 20 '14 at 01:51
Related: http://stackoverflow.com/questions/8499227/minimum-value-of-maximum-values-in-sub-segments-in-on-complexity/8499392#8499392 — Menelaos, Jan 20 '14 at 03:21

Pham Trung · Answer 1 · 2014-01-20T02:43:48.540

There is a nice solution for this problem, using Dequeue data structure (a structure which support add and check element at first and last position).

We create class Entry to store both index of the element and value of that element. Observe that the time complexity is approximately 2*n = O(2*n) = O(n) (Each element is added only once to the queue, and we also iterate through each element in the queue once: remove it either at first or last position of the queue).

Pseudo code:

class Entry {
    int value, index;
}

int [] highestValues;

Dequeue queue = new Dequeue();   

 for(int i = 0; i < arr.Length; i++){
        Entry en = new Entry(arr[i], i);
        while(queue.last().value <= en.value){//Remove all elements smaller than the current element.
            queue.removeLast();
        }
        queue.append(en);
        if(i >= k){
            highestValues[i] = queue.first().value;
            while(queue.first().index < i - k){//Remove all elements which has index out of the range
                 queue.removeFirst();
            }
        }
    }    
}

1) This isn't pseudo code, it's java code. 2) This is the Max within sliding window problem. — Menelaos, Jan 20 '14 at 03:14
@maythesource.com both is correct :) Code is not compilable, so at least the pseudo code thing will make readers not blindly copying the code. — Pham Trung, Jan 20 '14 at 03:18

score 1 · Answer 2 · answered Jan 20 '14 at 03:13

This is the maximum sliding window problem or Array of maximum value in sliding window.

See:

The key to this is the double ended queue that allowed removing elements from beginning and end in order to have maintain what is the maximum as we slide along.

Example from sources:

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindow {

public static void maxSlidingWindow(int A[], int n, int w, int B[]) {
    Deque<Integer> Q = new ArrayDeque<Integer>();

    // Initialize deque Q for first window
    for (int i = 0; i < w; i++) {
        while (!Q.isEmpty() && A[i] >= A[Q.getLast()])
            Q.pollLast();
        Q.offerLast(i);
    }

    for (int i = w; i < n; i++) {
        B[i - w] = A[Q.getFirst()];

        // update Q for new window
        while (!Q.isEmpty() && A[i] >= A[Q.getLast()])
            Q.pollLast();

        // Pop older element outside window from Q
        while (!Q.isEmpty() && Q.getFirst() <= i - w)
            Q.pollFirst();

        // Insert current element in Q
        Q.offerLast(i);
    }
    B[n - w] = A[Q.getFirst()];
}

public static void main(String args[]) {
    int k = 20;

    int a[] = new int[100];
    for(int i=0; i<100; i++)
    a[i] = i;

    int b[] = new int[a.length - k + 1];

    maxSlidingWindow(a, a.length, k, b);

    System.out.println("Sliding Window Maximum is ");
    for (int i = 0; i < b.length; i++) {
        System.out.print(b[i] + ",");
    }

}

}

Nice links, plus the idea of adding index to the queue rather than value +1 — Pham Trung, Jan 20 '14 at 03:24

Tim Destan · Accepted Answer · 2014-01-20T02:46:59.893

I have an implementation that I believe works (coded in C#):

public static int[] LastKHighestValues(int[] array, int k)
{
    int[] maxes = new int[array.Length];

    int indexOfCurrentMax = 0;
    int indexOfNextMax = 0;

    for (int i = 0; i < array.Length; i++)
    {
        if (indexOfNextMax <= indexOfCurrentMax ||
            array[i] > array[indexOfNextMax])
        {
            indexOfNextMax = i;
        }
        if (i - indexOfCurrentMax >= k)
        {
            indexOfCurrentMax = indexOfNextMax;
        }

        if (array[i] > array[indexOfCurrentMax])
        {
            indexOfCurrentMax = i;
        }


        maxes[i] = array[indexOfCurrentMax];
    }

    return maxes;
}

The idea is that you keep two "pointers": one to the current max, and one to the next thing to go to after the current max expires. This can be implemented in one pass through the array (so O(n)).

I have a few passing tests, but I'm far from certain I've covered every corner case:

Puzzle.LastKHighestValues(new[] {4, 3, 1}, 1).Should().Equal(new[] {4, 3, 1});
Puzzle.LastKHighestValues(new[] { 7, 7, 7 }, 3).Should().Equal(new[] { 7, 7, 7 });
Puzzle.LastKHighestValues(new[] { 7, 7, 7 }, 4).Should().Equal(new[] { 7, 7, 7 });
Puzzle.LastKHighestValues(new[] { 3, 2, 1 }, 2).Should().Equal(new[] { 3, 3, 2 });
Puzzle.LastKHighestValues(new[] { 7, 1, 4, 1, 1 }, 3).Should().Equal(new[] { 7, 7, 7, 4, 4 });
Puzzle.LastKHighestValues(new[] { 7, 8, 4, 9, 10 }, 2).Should().Equal(new[] { 7, 8, 8, 9, 10 });

This solution appears to be working for me. It's also the most elegant. Hope it doesn't have a flaw :) I'll continue testing it and revisit the other solutions if anything. — Alec Bryte, Feb 12 '14 at 03:17

Highest value of last k values in array, better than O(n^2)

3 Answers3