Loading page…
Practice problem · hard
Kestrel Shop shows a "You compared these" panel next to a shopper's wishlist. It replays the part of the browsing session where the shopper looked at the wishlist items.
A session is the list of product ids the shopper viewed, in order. Many products have offers from several sellers, and each view shows one offer. A shopper who wants to compare offers puts the product on the wishlist once for each offer. So a product listed twice needs at least two views in the span.
The panel uses the shortest span of consecutive views that covers the wishlist, and the earliest one on a tie. If no span covers it, the panel stays hidden.
Write shortest_span(views, wishlist).
views[i] is the product id of view i of the session, in order.wishlist lists product ids in any order. A product can appear in it more than once.wishlist. Other products may appear too.[start, end], the first and last view of the shortest covering window.[-1, -1]. This includes the case where wishlist is longer than views.Input: views = [52, 18, 52, 52, 31, 18, 52, 31], wishlist = [31, 52, 52]
Output: [2, 4]The need map is 52→2, 31→1, and missing starts at 3, the length of the wishlist. Product 18 is not on the wishlist.
| right | Joins | Counts of 52, 31 after joining | missing after joining | Recorded, then the left view leaves | left after | Best |
|---|---|---|---|---|---|---|
| 0 | 52 | 1, 0 | 2 | none | 0 | none |
| 1 | 18 | 1, 0 | 2 | none | 0 | none |
| 2 | 52 | 2, 0 | 1 | none | 0 | none |
| 3 | 52 | 3, 0 | 1 | none: a third 52 is a surplus view | 0 | none |
| 4 | 31 | 3, 1 | 0 | views 0 to 4, 1 to 4, 2 to 4; then 52, 18, 52 leave (missing 0, 0, 1) | 3 | 2 to 4 |
| 5 | 18 | 1, 1 | 1 | none | 3 | 2 to 4 |
| 6 | 52 | 2, 1 | 0 | views 3 to 6, then 52 leaves (missing 1) | 4 | 2 to 4 |
| 7 | 31 | 1, 2 | 1 | none | 4 | 2 to 4 |
Views 2 to 4 (52, 52, 31) hold two views of 52 and one of 31. The 52 at view 0 is a surplus view, so it leaves without changing missing.
Input: views = [52, 31, 18], wishlist = [52, 52, 31]
Output: [-1, -1]The wishlist needs two views of 52, and the session has only one.
Input: views = [52, 31, 52, 18, 52, 31, 52], wishlist = [52, 52, 31]
Output: [0, 2]Views 0 to 2 and views 4 to 6 both hold 52, 31, 52. The earlier span wins.
1 ≤ views.length ≤ 10^51 ≤ views[i] ≤ 10^61 ≤ wishlist.length ≤ 10^51 ≤ wishlist[i] ≤ 10^6Starting at every view and extending until the counts cover the wishlist is O(n^2) extension steps when one product is viewed late. On the large test stress-rare-product, that is about 4.9 × 10^9 steps, and each step compares counts for up to 1,123 products. Aim for O(n + m), where m is the length of the wishlist.
The wishlist can be as long as the session, so comparing two count maps at every step is too slow too. Keep one counter of the views the window still lacks, so each step costs O(1).
shortest_span · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.