Balanced prefixes in a permutation

Key idea. A contiguous block holds exactly the values 1..k only if it starts at the leftmost of those k values and ends at the rightmost of them. Any shorter window misses one of them. Any longer window, or any window in another place, contains a value outside 1..k. So k is balanced exactly when

max_pos(1..k) - min_pos(1..k) + 1 == k

The span always holds at least k elements, because the k values are distinct and all lie inside it. If the span is wider than k, some value greater than k lies in it, and the answer is 0.

Brute force (state it, then move on). For each k, slide a window of length k across the array and check whether its maximum is k. A window of k distinct values in 1..n with maximum k must be exactly {1..k}. That costs O(n²), or O(n² log n) if you sort each window. It is fine as a correctness reference and too slow for n = 10^5.

Optimal (O(n)).

1. Build pos[v], the index of value v. This takes one pass.
2. Sweep k = 1..n and keep lo = min(lo, pos[k]) and hi = max(hi, pos[k]).
3. Write '1' when hi - lo + 1 == k, otherwise '0'.

Invariants.

• After step k, [lo, hi] is the smallest window that contains every value in 1..k.
• hi - lo + 1 >= k always holds, so equality is the only success case.
• k = 1 and k = n are always balanced in a valid permutation.

The code below also has a version for the most common follow-up, where swap(i, j) calls are mixed with queries. It uses a segment tree indexed by value that stores the min and max position of each range of values.

from typing import List


def balanced_numbers(p: List[int]) -> str:
    """k-th char is '1' iff some contiguous subarray of p is a permutation of 1..k."""
    n = len(p)
    pos = [0] * (n + 1)
    for i, v in enumerate(p):
        pos[v] = i
    lo, hi = n, -1
    out = []
    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)


def balanced_numbers_brute(p: List[int]) -> str:
    """O(n^2) reference: some window of length k has max == k."""
    n = len(p)
    res = []
    for k in range(1, n + 1):
        ok = any(max(p[s:s + k]) == k for s in range(n - k + 1))
        res.append("1" if ok else "0")
    return "".join(res)


class BalancedWithSwaps:
    """Follow-up: support swap(i, j) and is_balanced(k) in O(log n) each.

    Segment tree indexed by VALUE 1..n; each node stores (min_pos, max_pos)
    over its value range, so a prefix query over values 1..k gives the span.
    """

    def __init__(self, p: List[int]) -> None:
        self.n = len(p)
        self.p = list(p)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        inf = float("inf")
        self.mn = [inf] * (2 * self.size)
        self.mx = [-inf] * (2 * self.size)
        for i, v in enumerate(p):
            self.mn[self.size + v - 1] = i
            self.mx[self.size + v - 1] = i
        for node in range(self.size - 1, 0, -1):
            self._pull(node)

    def _pull(self, node: int) -> None:
        self.mn[node] = min(self.mn[2 * node], self.mn[2 * node + 1])
        self.mx[node] = max(self.mx[2 * node], self.mx[2 * node + 1])

    def _set(self, value: int, index: int) -> None:
        node = self.size + value - 1
        self.mn[node] = self.mx[node] = index
        node //= 2
        while node:
            self._pull(node)
            node //= 2

    def swap(self, i: int, j: int) -> None:
        a, b = self.p[i], self.p[j]
        self.p[i], self.p[j] = b, a
        self._set(a, j)
        self._set(b, i)

    def is_balanced(self, k: int) -> bool:
        lo, hi = float("inf"), float("-inf")
        left, right = self.size, self.size + k  # values 1..k -> leaves [0, k)
        while left < right:
            if left & 1:
                lo, hi = min(lo, self.mn[left]), max(hi, self.mx[left])
                left += 1
            if right & 1:
                right -= 1
                lo, hi = min(lo, self.mn[right]), max(hi, self.mx[right])
            left //= 2
            right //= 2
        return hi - lo + 1 == k


if __name__ == "__main__":
    import random

    assert balanced_numbers([3, 1, 2, 5, 4]) == "11101"
    assert balanced_numbers([2, 4, 1, 3]) == "1001"
    assert balanced_numbers([1]) == "1"
    assert balanced_numbers([1, 2, 3, 4]) == "1111"
    assert balanced_numbers([4, 3, 2, 1]) == "1111"
    for _ in range(300):
        n = random.randint(1, 9)
        q = random.sample(range(1, n + 1), n)
        assert balanced_numbers(q) == balanced_numbers_brute(q)
        ds = BalancedWithSwaps(q)
        for _ in range(5):
            i, j = random.randrange(n), random.randrange(n)
            ds.swap(i, j)
            q[i], q[j] = q[j], q[i]
            want = balanced_numbers(q)
            got = "".join("1" if ds.is_balanced(k) else "0" for k in range(1, n + 1))
            assert got == want
    print("ok")

• balanced_numbers: O(n) time. O(n) space for pos and the output string.
• balanced_numbers_brute: O(n²) time, O(n) extra space per window slice.
• BalancedWithSwaps: O(n) to build. swap is O(log n) because it updates two leaves. is_balanced(k) is O(log n) because it is one prefix range query over values. O(n) space.

• [3, 1, 2, 5, 4] → "11101". For k = 4 the values 1..4 span indices 0..4, which is width 5, so k = 4 is not balanced.
• [2, 4, 1, 3] → "1001". For k = 2 the window [2, 4, 1] includes 4.
• [1] → "1". This is the smallest input.
• [1, 2, 3, 4] → "1111". The array is sorted.
• [4, 3, 2, 1] → "1111". The array is reversed, and every suffix is a valid block.
• [2, 1] → "11".
• [1, 3, 2] → "101". Value 3 lies between 1 and 2.
• [5, 1, 4, 2, 3] → "10011".
• Any permutation of length n: the first and last characters are always '1'.
• Stress: n = 10^5, random permutation. This runs in well under a second. Compare it against the brute force on small random inputs, as the __main__ block does.

1. Swaps between queries. Interleave swap(i, j) with "is k balanced?". Store min and max position per value range in a segment tree indexed by value, and read the span of 1..k with a prefix query. Each operation is O(log n), as in BalancedWithSwaps. If every query asks for the full string, rebuilding it in O(n) per query is often acceptable. Ask about the query mix first.
2. Return the window. Output (lo, hi) for each balanced k, or the number of balanced k. These come straight from the same sweep at no extra cost.
3. Input is not a permutation. The array may have duplicates, missing values, or values outside 1..n. Check that each k appears exactly once, and stop at the first missing value, because every larger k is then 0. With duplicates, a value can appear at several positions. A block for 1..k then needs a window of length k that contains each of 1..k exactly once. Use the "max == k and all distinct" sliding-window test, or a sum and count check per window with hashing.
4. Arbitrary target set. Ask "is there a subarray equal to the set {a..b}?" for many ranges. The span test still works: max_pos - min_pos + 1 == b - a + 1. Answer it with a sparse table over positions indexed by value, which gives O(1) per query after O(n log n) preprocessing.
5. Count all "good" subarrays. Count the subarrays that are a permutation of 1..m for some m. Each balanced k contributes exactly one window, because the window is forced to [lo, hi]. So the answer is the number of '1's. Interviewers like this as a quick check that the candidate understands why the window is unique.

Mid-level (L4)

• Starts with the brute force and explains why a window of length k with maximum k must be {1..k}.
• Moves to position tracking with a hint, and writes the O(n) sweep without off-by-one errors.
• Tests k = 1, k = n, sorted input, and reversed input.

Senior (L5)

• States the min/max position invariant on their own and proves why span == k is both necessary and sufficient.
• Writes clean O(n) code quickly, and checks it against a brute force on small inputs.
• Handles the input-validation follow-up, for example duplicates or values out of range, without a rewrite.

Staff (L6+)

• Asks about the query pattern up front, for example one batch versus online updates, and picks the right structure: a sweep, a segment tree over values, or a sparse table.
• Implements the swap version correctly, explaining why the tree is indexed by value and not by position.
• Generalizes to arbitrary value ranges {a..b}, and explains the trade-offs between preprocessing cost and query cost.