Which prefixes of 1..n appear as a contiguous block

Clarify first. The input is a permutation p of 1..n (every value appears exactly once). For each k in 1..n, answer yes if some contiguous window of length k holds exactly the values 1..k. Return the answers as a string of '0'/'1' (or a list of booleans; confirm the format). Confirm n can reach about 2 * 10^5, which rules out anything quadratic.

Brute force. For each k, slide a window of length k over p and check whether its maximum is k (with distinct values, a window of k distinct values whose max is k is exactly {1..k}). That is O(n) per k with a sliding-window maximum, so O(n^2) overall. It is a fine starting point to state, but too slow.

Key observation. Only one window can work for a given k: the one that contains all of 1..k. Let pos[v] be the index of value v. Let lo_k = min(pos[1..k]) and hi_k = max(pos[1..k]). The smallest window holding 1..k is [lo_k, hi_k]. It has length hi_k - lo_k + 1 >= k, because it holds k distinct values.

• If the length equals k, the window holds exactly those k values and nothing else, so the answer is yes.
• If the length is more than k, the window holds some other value, and every window that holds 1..k contains this one, so it is longer than k. The answer is no.

Optimal method. Build pos in one pass. Then sweep k from 1 to n, extending lo and hi with pos[k], and record hi - lo + 1 == k. This is O(n) time and O(n) space.

Invariant. After processing k, lo and hi are the minimum and maximum positions of values 1..k. Each step only needs pos[k], so the bounds update in O(1).

Small facts worth saying out loud. k = 1 and k = n are always yes. The answer for k does not imply anything about k + 1; answers can go yes, no, yes.

from collections import deque


def prefix_permutation_brute(p: list[int]) -> str:
    """O(n^2): for each k, slide a window of length k and track its max."""
    n = len(p)
    out: list[str] = []
    for k in range(1, n + 1):
        dq: deque[int] = deque()  # indices, values decreasing
        found = False
        for i, v in enumerate(p):
            while dq and p[dq[-1]] <= v:
                dq.pop()
            dq.append(i)
            if dq[0] <= i - k:
                dq.popleft()
            if i >= k - 1 and p[dq[0]] == k:
                found = True
                break
        out.append("1" if found else "0")
    return "".join(out)


def prefix_permutation(p: list[int]) -> str:
    """O(n): the span of positions of 1..k must have length exactly k."""
    n = len(p)
    pos = [0] * (n + 1)
    for i, v in enumerate(p):
        if not 1 <= v <= n or pos[v]:
            raise ValueError("input must be a permutation of 1..n")
        pos[v] = i + 1  # 1-based so 0 means "unseen"

    out: list[str] = []
    lo, hi = n + 1, 0
    for k in range(1, n + 1):
        lo = min(lo, pos[k])
        hi = max(hi, pos[k])
        out.append("1" if hi - lo + 1 == k else "0")
    return "".join(out)


if __name__ == "__main__":
    import random

    assert prefix_permutation([2, 1, 3]) == "111"
    assert prefix_permutation([3, 1, 4, 2]) == "1001"
    assert prefix_permutation([1]) == "1"
    assert prefix_permutation([2, 4, 1, 5, 3]) == "10001"
    assert prefix_permutation([2, 4, 1, 3, 5]) == "10011"
    for _ in range(300):
        n = random.randint(1, 9)
        q = list(range(1, n + 1))
        random.shuffle(q)
        assert prefix_permutation(q) == prefix_permutation_brute(q), q
    print("ok")

• Optimal: O(n) time (one pass to build pos, one sweep over k), O(n) extra space for pos and the output.
• Brute force: O(n^2) time, O(n) space for the deque.

• [2, 1, 3] -> "111": every prefix of values sits together.
• [3, 1, 4, 2] -> "1001": positions of 1, 2 span 3 cells; 1..3 span 4 cells.
• [1] -> "1": single element.
• [2, 4, 1, 5, 3] -> "10001": only k = 1 and k = n work.
• [2, 4, 1, 3, 5] -> "10011": no for k = 2, 3, then yes for k = 4 (yes after no).
• Sorted [1, 2, ..., n] -> all '1'; reversed [n, ..., 1] -> all '1'.
• [4, 2, 1, 3, 5] -> "11111": 1 in the middle, each next value lands right beside the current span.
• Invalid input (duplicate or out-of-range value) -> ValueError, if the interviewer wants validation.

• Count the windows instead of the ks. "How many subarrays are a permutation of 1..len?" Each valid subarray of length k is exactly the span of 1..k, so the count equals the number of '1's. Same O(n).
• The array is not a permutation (values can repeat or be missing). Then "span length equals k" is not enough. Use a sliding window per candidate length with a distinct-count, or for each position of 1 expand and check max == length and all distinct using prefix hashes or a last-occurrence array; the classic solution is O(n log n) or O(n) by anchoring windows at each 1 and growing both sides with a running max.
• Online queries / updates. Values are swapped (p[i], p[j] exchange) and you must re-answer for a given k. Store pos in two segment trees (range min and range max over values 1..k) so each query and each swap is O(log n).
• Return the window. For each yes, return (lo, hi) too; they are already tracked.
• Streaming positions. If values arrive one at a time in order 1, 2, ... with their positions, the same running min/max answers each k as it arrives in O(1).

Mid-level (L4)

• States the brute force, then finds the "positions span" idea with some prompting.
• Writes the O(n) sweep correctly, with clean 0- or 1-based indexing.
• Tests k = 1, k = n, and a case that goes yes, no, yes.

Senior (L5)

• Reaches the span argument quickly and proves both directions (span == k means yes; span > k means no window can work).
• Points out that distinct values are what make the check sufficient.
• Checks the fast solution against a brute force on random permutations.

Staff (L6+)

• Handles the non-permutation variant and explains why the proof breaks there.
• Designs the update/query version with segment trees and states its costs.
• Discusses input validation and output format choices for an OA versus a production API.