PROBLEM LINK:
Author: Anudeep Nekkanti
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Sort, Two Pointers Scan
PROBLEM:
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.
EXPLANATION:
Minimal Intervals
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
Original Question
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.
AUTHOR’S AND TESTER’S SOLUTIONS:
Solutions will be available soon.
Author’s solution can be found here.
Tester’s solution can be found here.