Given an array of integers A, the previous smaller element problem is to find, for each position i in the array, the closest element before position i that is smaller than A[i]. This problem can be solved in linear time using a monotone stack. We consider a variant of this problem:
Given an array of integers A, and a positive integer M, for each position i in the array, find the closest element before position i-M that is smaller than A[i].
Can this problem be solved in linear time? We can modify the monotonic stack approach to obtain a linearithmic time algorithm, but I am unable to improve it to linear time.
