You get a list p holding the numbers 1..n, each exactly once, in some order. Call a size k compact when the numbers 1, 2, ..., k occupy k consecutive positions of p (in any order among themselves). In other words, some contiguous slice of p of length k contains exactly the numbers 1..k.
Write compact_sizes(p: list[int]) -> str returning a string of n characters: character k-1 is "1" if size k is compact and "0" otherwise.
compact_sizes([3, 1, 2, 5, 4]) # "11101"
# k=1: [1] yes
# k=2: [1, 2] yes
# k=3: [3, 1, 2] yes
# k=4: 1..4 are spread over positions 0..4 with 5 in between -> no
# k=5: the whole list -> yes
compact_sizes([2, 4, 1, 3]) # "1001"
compact_sizes([1]) # "1"
n can be 200,000. Checking every k by scanning slices is quadratic; aim for O(n).
Notes:
k = 1andk = nare always compact.- The input is always a valid permutation of
1..nwithn >= 1.
Show hint
Record where each value sits. As k grows, track the leftmost and rightmost positions used by 1..k. What must the width of that span be?