PROBLEM LINK:
Author: Abhra Dasgupta
Tester: Kevin Atienza
Editorialist: Ajay K. Verma
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Range Minimum Query, Sliding Range Minimum Query
PROBLEM:
Given an array A of size N, and an integer K, handle the queries of the form: find the minimum element of the subarray A[L, R], where length of the subarray lies between K and 2K.
QUICK EXPLANATION:
Any interval which has length between K and 2K, can be represented as a union of two K-length intervals. Hence, the minimum of any subarray of length n \in [K, 2K] can be computed by taking the minimum of two K length subarrays. Hence, the task reduces to precomputing the minimum of all K length subarrays, which can be done in linear time using sliding range minimum query method.
.
EXPLANATION:
We are given an array A, and we need to handle several queries, each of which asks the minimum of some subarray A. Also, we are given an integer K, and it is guaranteed that all the subarrays in the queries have length between K and 2K.
If we were not given the special constraint about the size of queried subarrays, then this problem would be a standard range minimum query problem, which can be solved using O (N \log N) preprocessing time and O (1) query time as described here. In fact, this approach will suffice to solve the smaller subtasks (and probably the large one as well, if well optimized). However, here we describe an approach, which uses this constraint, and requires O (N) preprocessing time, while still answering queries in O (1) time.
Reduction into Fixed-Length Subarray:
Any interval [x, y] of length between K and 2K can be written as a union of two K length interval.
[x, y] = [x, x + K] \cup [y - K, y].
Similarly, a subarray A[L, R], can be seen as the union of two (possibly overlapping) subarrays A[L, L + K - 1] and A[R - K + 1, R]. Since, the length of the original subarray is at least K, none of the two subarrays cover any element outside the original subarray. On the other hand, the length of the original subarray is no longer than 2K (i.e., R - L + 1 \leq 2K), hence the two subarrays must cover each element of the original subarray (i.e., (R - k + 1) \leq (L + K) ).
Based on this we can write
\min (A[L, R]) = \min (\min(A[L, L + K - 1]), \min(A[R - K + 1, R]))
In other words, we have reduced the problem of computing the minimum of A[L, R] into computing the minimum of two K-length subarrays. There are exactly (N - K + 1) subarrays of length K, so we can precompute the minimum of all such subarrays and store them to handle the general queries in O (1) time. In the next section we show that this pre-computation can be done in O (N) time.
Computing Minimum of All K-Length Subarrays:
There are two possible ways to compute the minimum of all K-length subarrays.
First Method:
In this method, we partition the original array into blocks of size K, i.e., A[0, K - 1], A[K, 2K - 1], \cdots. For each block we compute the minimum of each prefix and suffix of that block. In other words, for the block A[nK, (n + 1)K - 1], we compute the minimum of following subarrays:
Prefix:
A[nK, nK]
A[nK, nK + 1]
A[nK, nK + 2]
\cdots
A[nK, (n + 1)K - 1]
Suffix:
A[(n + 1)K - 1, (n + 1)K - 1]
A[(n + 1)K - 2, (n + 1)K - 1]
A[(n + 1)K - 3, (n + 1)K - 1]
\cdots
A[nK, (n + 1)K - 1]
For each block we are computing 2K values, and they can be computed in O (K). Hence, the overall time complexity is O (N).
Now let us see how to compute the minimum of subarray A[x, x + K - 1] using these values. If x is a multiple of K, then this subarray is the same as one of the blocks, so we already have this value. If x is not a multiple of K, then y = \lfloor (x / K) \rfloor-th block will contain the endpoint x, and (y + 1)-th block will contain the endpoint (x + K - 1). Hence, we can take the appropriate suffix of y-th block and prefix of (y + 1)-th block and compute their minimum to compute the minimum of subarray A[x, x + K - 1]. More formally,
\min (A[x, x + K - 1]) = \min(\min(A[x, (y + 1)K - 1]), \min(A[(y + 1)K, x + K - 1])).
Hence, we can compute the minimum of all K length subarrays in O (N) time.
Second Method:
This approach is slightly faster than the previous method, as it requires only a single scan of the array. This method is explained here in detail. We describe this method only briefly. We use a window of size K, and slide it from left to right so that it covers all K-length subarrays of A. Initially, the window corresponds to the subarray A[0, K - 1], when we slide it one step to the right it corresponds to the subarray A[1, K]. This sliding corresponds to adding A[K] into the window, and removing A[0] from the window.
The basic idea is that we maintain a list P, which consist of potential minimum element of the current and future windows. Whenever, we add an element A[x] into the window, we discard all elements of the list which are larger than A[x], this is because these elements can never be the minimum element of any future window, as any future window containing these elements will also contain A[x], which is strictly smaller than these elements. This means element of P will be in non-decreasing order. When we remove an element from the window, we check if the removed element is the same as the first element of list P, if so, we have to discard it, as this element no longer belongs to the window. The first element of the list is the minimum element of the current window. The following snippet contains the pseudocode for this method.
// B[i] will contain the minimum of subarray A[i, i + K - 1]
B[1..N] = {INF};
// deque, which will contain the potential candidate for minimum elements
// of current and future windows.
P = {};
for (int i = 0; i < N; ++i) {
// Discard elements of the list larger than current element.
while (!P.empty() && P.back() > A[i])
P.pop_back();
// Add the new element.
P.push_back(A[i]);
// Remove the first element of the window,
// and from the list P as well, if it belongs there.
if (i >= K && A[i - K] == P.front()) {
P.pop_front();
}
// Set the minimum of the window
if (i >= (K - 1)) {
B[i - K + 1] = P.front();
}
}
Since each element can be added into the list P at most once, and removed at most once, the complexity of this algorithm remains O (N)
Time Complexity:
O (N + Q)
