Shortest stretch where every member posts

Scenario

Kestrel Chat writes short summaries of busy group threads. A good summary starts from a stretch of consecutive messages in which every member of the thread posts at least once. Then nobody's view is left out.

The members of a thread are the people who posted in it. The data is the sender id of each message, in order. The summary team wants the length of the shortest stretch that includes every member. The thread itself always qualifies, so an answer always exists.

Your task

Write shortest_full_span(senders).

senders[i] is the account id of the person who sent message i of the thread, in order.
The members are the distinct values in senders, taken over the whole thread.
Return the length of the shortest window of consecutive messages in which every member appears at least once.
The whole thread is always such a window, so the answer is between 1 and len(senders).

Examples

Example 1 (traced)#

text2 lines

Input:  senders = [12, 31, 12, 12, 47, 31, 12, 47]
Output: 3

A first pass finds three members, 12, 31 and 47, so missing starts at 3. best starts at 8, the whole thread.

right	Joins	missing after joining	Recorded lengths, then the left messages leave	left after	Best
0	12	2	none	0	8
1	31	1	none	0	8
2	12	1	none	0	8
3	12	1	none	0	8
4	47	0	5, 4; then 12, 31 leave (missing 0, 1)	2	4
5	31	0	4, 3; then 12, 12 leave (missing 0, 1)	4	3
6	12	0	3; then 47 leaves (missing 1)	5	3
7	47	0	3; then 31 leaves (missing 1)	6	3

Messages 3 to 5 (12, 47, 31) include all three members.

Example 2#

text2 lines

Input:  senders = [40, 40, 40]
Output: 1

One member wrote every message, so any single message includes everyone.

Example 3#

text2 lines

Input:  senders = [63, 18, 18, 26, 63, 63, 18]
Output: 3

Member 26 posts only once, at message 3. Every answer must include it, and messages 2 to 4 (18, 26, 63) add the other two members.

Constraints

1 ≤ senders.length ≤ 10^5
1 ≤ senders[i] ≤ 10^9

What does n ≤ 10^5 tell you?

Starting at every message and extending until the window includes every member is O(n^2) when one member posts rarely. On the large test stress-rare-member, that is about 4.6 × 10^9 steps. Aim for O(n).

The ids go up to 10^9, so count them in a hash map, not an array. The set of members is not given: one extra pass over the thread finds it, and that pass is O(n) too.

Scenario

Your task

Write shortest_full_span(senders).

senders[i] is the account id of the person who sent message i of the thread, in order.
The members are the distinct values in senders, taken over the whole thread.
Return the length of the shortest window of consecutive messages in which every member appears at least once.
The whole thread is always such a window, so the answer is between 1 and len(senders).

Examples

Example 1 (traced)#

text2 lines

Input:  senders = [12, 31, 12, 12, 47, 31, 12, 47]
Output: 3

A first pass finds three members, 12, 31 and 47, so missing starts at 3. best starts at 8, the whole thread.

right	Joins	missing after joining	Recorded lengths, then the left messages leave	left after	Best
0	12	2	none	0	8
1	31	1	none	0	8
2	12	1	none	0	8
3	12	1	none	0	8
4	47	0	5, 4; then 12, 31 leave (missing 0, 1)	2	4
5	31	0	4, 3; then 12, 12 leave (missing 0, 1)	4	3
6	12	0	3; then 47 leaves (missing 1)	5	3
7	47	0	3; then 31 leaves (missing 1)	6	3

Messages 3 to 5 (12, 47, 31) include all three members.

Example 2#

text2 lines

Input:  senders = [40, 40, 40]
Output: 1

One member wrote every message, so any single message includes everyone.

Example 3#

text2 lines

Input:  senders = [63, 18, 18, 26, 63, 63, 18]
Output: 3

Member 26 posts only once, at message 3. Every answer must include it, and messages 2 to 4 (18, 26, 63) add the other two members.

Constraints

1 ≤ senders.length ≤ 10^5
1 ≤ senders[i] ≤ 10^9

What does n ≤ 10^5 tell you?

The ids go up to 10^9, so count them in a hash map, not an array. The set of members is not given: one extra pass over the thread finds it, and that pass is O(n) too.