I have faced the following problem in an entrance examination, and need to verify a few results plus a question part that did not manage to get in time.
Given an array $A$ of length $n$ which contains all integers $1,\ldots,m$, the goal is to find a consecutive subarray of $A$ containing the integers $1,\ldots,m$ which is closest to the end of $A$. For example, if the array is $2,2,1,2$, then we need to return the final two elements $1,2$. We may use a procedure HAS-INTEGERS that given the first and last index of a subarray, checks whether the subarray contains all integers $1,\ldots,m$. We assume that HAS-INTEGERS can be implemented in $O(1)$.
The task, known as FIND-SNIPPET, can be solved in $O(n^2)$ by simply trying all subarrays. The problem has two parts:
- Come up with an $O(n)$ algorithm for FIND-SNIPPET.
- Show how to implement HAS-INTEGERS in $O(1)$.
I thought about a dynamic programming solution using the fact that the function can be expressed recursively on $m$: FIND-SNIPPET($n,m,A$) equals FIND-SNIPPET($n,m-1,A$) extended to contain the closest $m$ (if $m$ is not already inside), and respecting the priority to the right side in case of equal distance.
I am not sure how to get this to a pseudocode using dynamic programing, Also, I'm not sure how to implement HAS-INTEGERS in $O(1)$.