Find indexes that form the Middle point of a Non-decreasing and Non-increasing sequence

Question

Given a list of positive integers and an integer k.

Find all indexes r in the list such that the k numbers before the index r and including the number at index r form a non-increasing r and including the number at index r forms a non-decreasing sequence.

Example:

list =  [3, 2, 2, 2, 3, 4] and k = 2 output = [2,3]  

My Thoughts:

One naive approach would be for each index to check the k elements in front of it and the k elements behind it. Not sure if there could be some efficient way to do it.

An alternative would be to scan the list, and if two consecutive number a and b are found such that a<b then from this index till the next k index, none of the indexes could be in the output.

I am looking for an efficient approach. Coding I could do myself.

Answer 1

A sliding window approach would work here. In essence you are looking for the middle of valleys of length 2*k+1. This can be done in linear time with a space complexity of k.

Here are the general steps to achieve this:

1. Use a doubly ended queue for the window to get constant addition/removal time from both ends and also constant access time by index.
2. Start iterating over the input array for k+1 elements and add them to the deq while they are none-increasing. If you find some violation, reset the deq to the index after the violation as you can be sure that you won't find the first part (none-increasing) before that index.
3. If/when you get your k+1 non-increasing elements, save the index your current potential valley as r. start to add the remaining k elements, this time the condition is to be non-decreasing. Now, here are 3 possibilities:

a. The element is non-decreasing: Add it to the deq.

b. The element is decreasing: This is a violation with 2 possibilities:

b1. You already had some increasing elements before: This means that you can't use the part before this for the number 2 (non-increasing). In this case, you just have to let go of all you got till here and start from your current index+1 with step 2. The first part.

b2. You didn't have any increasing elements, this means that the first part is still good. You can move r to the current index and be sure that all the elements from r-k to r are non-increasing. Now, go to step 3, trying to find the non-decreasing part.

4. Now suppose you find a window of size 2*k+1. Store r in your results and start moving the window forward by removing an element from the head of the deque and adding one to the tail. Check whether the new r is still a valley by making sure r-1 <= r and r+1 >= r. Also check whether the newly added element to the deq is non-decreasing. If so, you're all good. Store the new r in your result.