Sort, Two Pointers Scan
There are N shops in a line and each of them has some different types of items (M types in total). For any i (1<=i<=N), find out the best interval [j, k] (j<=i<=k) such that there are all M types of items available in these shops and k-j is minimized. If there are several ties, take the smallest j.
Let define the minimal intervals are those intervals [j, k] such that there are all M types of items available in these shops but this condition will not be held for either [j + 1, k] and [j, k - 1].
Clearly, there are at most N different minimal intervals, because the left sides of different minimal intervals should be different.
Let right[i] be the right side of the minimal interval starting from i. It is worth noting that there might be impossible to have valid right[i] for some i because of there are not enough types in the tail of shops. In this case, we can set right[i] to INF, which is a very large number.
To compute all right[i], we can simply pass all shops once as following:
j = 1 For i = 1 to N While (j < N) and ([i, j] does not have enough types): j += 1 if j < N: right[i] = j else: right[i] = INF
For a given i, there might be several minimal intervals containing it. For a specific minimal interval [j, k], it could be a possible solutions for the i inside it.
Therefore, we can maintain a data structure, which contains all feasible minimal intervals for current i, sorted by the length of intervals and its left side. By increasing i to i + 1, some intervals starting from i + 1 should be inserted while those intervals ended at i should be removed. Considering these types of operations, the balanced binary search tree is able to do it efficiently. In C++, you can refer to set, where Interval should be user defined struct/class with the special < operator.
Solutions will be available soon.
Author’s solution can be found here.
Tester’s solution can be found here.