2D Sliding window min/max problem

Problem

given a matrix and a window size k, output the max/min value in the 2D sliding window with a window size of k by k.

Example:
Matrix = [
[5, 2, 7, 44, 12, 7],
[45, 44, 13, 4, 0, 34],
[5, 2, 7, 11, 16, 42],
[5, 23, 7, 0, 12, 7],
[15, 2, 3, 32, 8, 32],
]

k = 3

Output
[
[45, 44, 44, 44],
[45, 44, 16, 42],
[23, 32, 32, 42],
]

Solution

change it to 1D max/min problem and solve it.

Time complexity O(RC)*O(1D sliding complexity), Space complexity(RC)

Sliding window minimum/maximum in 2D

1D sliding algorithm

A nice implementation from here. O(K), O(log k), and O(1) algorithms are provided.

“We can improve on the naive O(K) algorithm by using a sorted set to speed up the minimum value queries to logarithmic time:

void logarithmic_time(std::vector<int> & ARR, int K) {
  std::multiset<int> window;
  for (int i = 0; i < ARR.size(); i++) {
     window.insert(ARR[i]);
     if (i - K >= 0)
       window.erase(window.find(ARR[i - K]));
     std::cout << *window.begin() << ' ';
  }
}

The window can have at most K elements, so the multiset insert, find and begin operations all take time O(log K). This gives us an overall time of O(NlogK).

We can improve the run-time by a constant factor by using a heap instead. All the heap operations (except finding the minima) have the same run-time complexity as the multiset versions, however, heap empirically performs better. We need to be able to remove arbitrary items in the heap, but the implementation of heaps in C++ (std::priority_queue) does not support this operation. Luckily a technique I have mastered in real life helps us get around this: we delete lazily. For each element in the priority queue, we also store what index it was inserted from. Then when we query what the smallest element is, we discard it if its index falls out of range of our current window.:

void logarithmic_time2(std::vector<int> & ARR, int K) {
  // pair<int, int> represents the pair (-ARR[i], i). We use -ARR[i] since
  // priority_queue is by default a max-heap, but we want a min-heap. By
  // negating the value on insertion and removal we get a min-heap. One can
  // also use the rather ugly
  // std::priority_queue< std::pair<int, int>,
  //                      std::vector< std::pair<int, int> >,
  //                      std::greater< std::pair<int, int> > >
  std::priority_queue< std::pair<int, int> > window;
  for (int i = 0; i < ARR.size(); i++) {
     window.push(std::make_pair(-ARR[i], i));
     while(window.top().second <= i - K)
       window.pop();
     std::cout << (-window.top().first) << ' ';
  }
}

Note that deleting lazily can actually make this algorithm perform rather badly. If the input is N values from N to 1, then a value is never deleted from the priority queue leading to O(logN) insertions. However, on average, this is empirically faster than the multiset version.”

A better one

A better solution is from this link again by using a double-ended queue + soft deletion. Pretty smart.

“The idea of lazily deleting elements is a salient one, but by putting in a bit more effort when inserting an element into the window we can get amortized O(1) run-time. Say our window contains the elements {1, 6, 7, 2, 4, 2}. We want to add the element 5 to our window. Notice that all elements in the window greater than 5 will now never be the minimum in the window for future i values, so we might as well get rid of them. The trick to this is to store the numbers in a deque [1] and whenever inserting a number x we remove all numbers at the back of the deque which are greater than equal to x. Notice that if the deque was sorted before inserting, it will still be sorted after inserting x. Since the deque starts off sorted, it remains sorted throughout the sliding window algorithm. So the front of the deque will always be the smallest value.

The front of the queue might have a value which shouldn’t be in the window anymore, but we can use the lazy delete idea with the deques as well. Now each element of ARR is inserted into the deque and deleted from the deque at most once. This gives as a total run-time of O(N) for the algorithm (amortized O(1) per insertion/deletion). Pretty sweet:

void sliding_window_minimum(std::vector<int> & ARR, int K) {
  // pair<int, int> represents the pair (ARR[i], i)
  std::deque< std::pair<int, int> > window;
  for (int i = 0; i < ARR.size(); i++) {
     while (!window.empty() && window.back().first >= ARR[i])
       window.pop_back();
     window.push_back(std::make_pair(ARR[i], i));
     while(window.front().second <= i - K)
       window.pop_front();
     std::cout << (window.front().first) << ' ';
  }
}

”

Thanks for reading.

Reference

[1]https://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html

[2]https://blog.csdn.net/csyifanZhang/article/details/105257494