Minimum over a sliding window

Question

Is there specific algorithm that allows me to maintain a min/max over a small/medium sized sliding window (typical size is 600, with all elements being integers)? The window is really the last N observations in a stream. So, I add a new observation and remove the oldest observation at each time unit, so I'd like to keep the min and max over the last N obervations.

This is a different problem from the one stated in Sliding window minimum algorithm because I do not maintain the entire data, and therefore the "index-based" solution will not be applicable here. Moreover my input data itself will be in a circular array.

Heaps will probably not work too well: I don't delete/pop the Min/Max element, but the oldest element, which will defeat the purpose of having the heap in the first place.

log(n) complexity-based structures such as Red-black trees will work just fine, and splay trees may be even more suitable for the type of data I'd have, but are they a bit of an overkill for the size I'd deal with?

Better late than never, may help people in the future. There is indeed an algorithm : http://home.tiac.net/~cri/2001/slidingmin.html — Wam, Nov 20 '12 at 14:47
The link above doesn't work but I found a version on archive.org: http://web.archive.org/web/20120805114719/http://home.tiac.net/~cri/2001/slidingmin.html — user674669, Feb 28 '13 at 17:59
You don't actually need to track an ever increasing index, you just need to track it modulo the window size. So the index in your case would go from 0 to 599 and then back to 0. — Christoffer Hammarström, Nov 04 '16 at 15:40
Does this answer your question? https://stackoverflow.com/questions/8499227/ — templatetypedef, Jun 14 '21 at 14:15

score 0 · Answer 1 · answered May 11 '15 at 04:12

The solution to the problem of finding maximum over stream of input data is hosted on the below link, you may easily tweak it to find Min as well.

The size of input stream isn't important and can be infinite. The algorithm executes in Amortized constant O(1) complexity.

https://github.com/varoonverma/code-challenge.git

score 0 · Answer 2 · answered Feb 09 '21 at 06:02

Here is the code in java

import java.io.*;
import java.util.*;

public class MinInwindow {

  public static void main(String[] args) {

      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();

      int arr[] = new int[n];
      for (int i = 0; i < n; i++) {
          arr[i] = sc.nextInt();
      }

      int k = sc.nextInt();

      printMinInWindow(arr, n, k);

  }

  static void printMinInWindow(int[] arr, int n, int k) {
      int start = 0, last = 0;
      ArrayList<Integer> list = new ArrayList<Integer>(k);
      while (last < n) {
          int val = arr[last];
          if (last < k) {

              list = addNewINtoList(list, val);
              last++;
          } else {
              //print minimum from window
              System.out.print(list.get(0) + " ");
              int startValue = arr[start];
              start++;
              list = removefromListIfAvailable(list, startValue);
              list = addNewINtoList(list, val);
              last++;
          }

      }
      System.out.println(list.get(0) + " ");


  }

  static ArrayList<Integer> addNewINtoList(ArrayList<Integer> list, int val) {

      if (list.isEmpty()) {
          list.add(val);
      } else {

          int size = list.size();
          while (size > 0 && list.get(size - 1) > val) {
              list.remove(size - 1);
              size--;
          }
          list.add(val);

      }
      return list;

  }

  static ArrayList<Integer> removefromListIfAvailable(ArrayList<Integer> list, int val) {

      if (list.isEmpty()) {
          return list;
      }

      int startValue = list.get(0);
      if (startValue == val) {
          list.remove(0);
      }
      return list;
  }


}

Please don't post only code as an answer, but also provide an explanation of what your code does and how it solves the problem of the question. Answers with an explanation are usually more helpful and of better quality, and are more likely to attract upvotes — Ran Marciano, Feb 09 '21 at 06:38

Minimum over a sliding window

2 Answers2