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:

  1. Come up with an $O(n)$ algorithm for FIND-SNIPPET.
  2. 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)$.

  • 1
    $\begingroup$ I don't understand your task. What does "closest to the end of $A$" mean? Given a bunch of solutions $A[i_1:j_1],\ldots,A[i_\ell:j_\ell]$, which one is closest to the end of $A$? $\endgroup$ – Yuval Filmus Jan 10 at 14:57
  • $\begingroup$ You have described an idea for a dynamic programming solution. The fact that you cannot express it as pseudocode hints that your idea is at this point just an idea, and not quite a solution. For example, you don't explain how to quickly extend the $M-1$ snippet to an $M$ snippet. $\endgroup$ – Yuval Filmus Jan 10 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.