Dynamic programming function in O(nk) time

Question

Given two integer arrays A of size n and B of size k, and knowing that all items in the array B are unique, I want to find an algorithm that finds indices j' < j'', such that all elements of B belong to A[j' : j''] and value |j''-j'|is minimized or returns zero if there are no such indices at all. I also note that A can contain duplicates.

To provide more clarity, we can consider array A = {1, 2, 9, 6, 7, 8, 1, 0, 0, 6} and B {1, 8, 6}, then you can see that B ⊆ A[1 : 6] and B ⊆ A[4 : 7], but at the same time 7−4 < 6−1, thus algorithm should output j'= 4 and j''= 7.

I want to find an algorithm that runs in O(nk) time.

My work so far is that I was thinking for each j'∈ [n], I can compute the minimum j'' ≥ j' so that B ⊆ A[j', j'']. If I assume B = {b1, ..., bk}, let Next[j'][i] denote the smallest index t ≥ j' so that at = b_i, i.e., the index of next element after a_j' (included) which equals bi. In particular if such t doesn’t exist, simply let Next[j'][i] = ∞. If I am able to show that the minimum j'' is the following

j'' = max i∈[k] of Next[j'][i],

then I think I will be able to design a dynamic programming algorithm to compute Next in O(nk) time. Any help on this dynamic programming problem would be much appreciated!

Answer 1

Just run a sliding window that maintains the invariant of including all elements of B. That's O(n) with a hashmap.