### 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.