Databases
StackOverflow2013
Postsdbo
POAlgorithm to determine indices i..j of array A containing all the elements of another array B
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAlgorithm to determine indices i..j of array A containing all the elements of another array B
    primarykey
    data
    text
    <p>I came across this question on an interview questions thread. Here is the question:</p> <blockquote> <p>Given two integer arrays A [1..n] and B[1..m], find the <strong>smallest</strong> window in A that contains <strong>all</strong> elements of B. In other words, find a pair &lt; i , j > such that A[i..j] contains B[1..m]. </p> <p>If A doesn't contain all the elements of B, then i,j can be returned as -1. The integers in A need not be in the same order as they are in B. If there are more than one smallest window (different, but have the same size), then its enough to return one of them.</p> <p>Example: A[1,2,5,11,2,6,8,24,101,17,8] and B[5,2,11,8,17]. The algorithm should return i = 2 (index of 5 in A) and j = 9 (index of 17 in A).</p> </blockquote> <p>Now I can think of two variations.</p> <p>Let's suppose that B has duplicates.</p> <ol> <li><p>This variation doesn't consider the number of times each element occurs in B. It just checks for all the unique elements that occur in B and finds the smallest corresponding window in A that satisfies the above problem. For example, if A[1,2,4,5,7] and B[2,2,5], this variation doesn't bother about there being two 2's in B and just checks A for the unique integers in B namely 2 and 5 and hence returns i=1, j=3.</p></li> <li><p>This variation accounts for duplicates in B. If there are two 2's in B, then it expects to see at least two 2's in A as well. If not, it returns -1,-1.</p></li> </ol> <p>When you answer, please do let me know which variation you are answering. Pseudocode should do. Please mention space and time complexity if it is tricky to calculate it. Mention if your solution assumes array indices to start at 1 or 0 too.</p> <p>Thanks in advance.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USSkylark
    1. USSkylark
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POAlgorithm to determine indices i..j of array A containing all the elements of another array B
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POAlgorithm to determine indices i..j of array A containing all the elements of another array B
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POAlgorithm to determine indices i..j of array A containing all the elements of another array B
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou wrote "A[1..n] and B[1..m]"; doesn't that mean array indices start at 1?
      singulars
      1. POAlgorithm to determine indices i..j of array A containing all the elements of another array B
      1. USShreevatsaR
    2. COYep, you're right! I'd meant to say mention if your array starts at 0 or 1. Editing now. :)
      singulars
      1. POAlgorithm to determine indices i..j of array A containing all the elements of another array B
      1. USSkylark
    3. COhttp://stackoverflow.com/a/3592224/172414 O(N) for space and time
      singulars
      1. POAlgorithm to determine indices i..j of array A containing all the elements of another array B
      1. USJack
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload