Determine balanced k values in a permutation

Quick Overview

This question evaluates algorithmic reasoning about permutations and contiguous subarray properties, testing skills in array manipulation, positional reasoning, combinatorial insight, and complexity-aware algorithm design within the Coding & Algorithms domain.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

You are given a permutation `p` of the integers `1..n`. For a number `k` (where `1 <= k <= n`), call `k` **balanced** if there exists a contiguous subarray `p[l..r]` such that: - `r - l + 1 = k`, and - the multiset of values in `p[l..r]` is exactly `{1, 2, ..., k}` (i.e., the subarray is a permutation of `1..k`). Your task: for every `k = 1..n`, determine whether `k` is balanced and return a binary string `s` of length `n` where: - `s[k-1] = '1'` if `k` is balanced - `s[k-1] = '0'` otherwise ### Input - An integer `n` - A permutation `p` of length `n` *(If your platform uses multiple test cases, solve independently per test case.)* ### Output - A binary string of length `n`. ### Example If `n = 5` and `p = [4, 1, 3, 2, 5]`, you should output a string of length 5 indicating which `k` are balanced. ### Constraints Assume `n` can be large (e.g., up to `2e5`), so an `O(n log n)` or `O(n)` approach is expected.

Overview: This question evaluates algorithmic reasoning about permutations and contiguous subarray properties, testing skills in array manipulation, positional reasoning, combinatorial insight, and complexity-aware algorithm design within the Coding & Algorithms domain.

You are given a permutation p of the integers 1 through n. For a number k (1 <= k <= n), call k balanced if there exists a contiguous subarray of length k whose elements are exactly the set {1, 2, ..., k} in any order. Return a binary string s of length n where s[k-1] is '1' if k is balanced and '0' otherwise. Because p is a permutation, each value appears exactly once. The challenge is to determine the answer for every k efficiently.

Constraints

1 <= n <= 2 * 10^5
p is a permutation of the integers 1..n
An O(n) or O(n log n) solution is expected

Examples

Input: (5, [4, 1, 3, 2, 5])

Expected Output: "10111"

Explanation: For k=1, the value 1 appears alone, so it is balanced. For k=2, positions of 1 and 2 are not adjacent. For k=3, values {1,2,3} occupy positions 2..4. For k=4 and k=5, the required values also occupy a contiguous block.

Input: (1, [1])

Expected Output: "1"

Explanation: The only possible k is 1, and the single-element subarray [1] matches {1}.

Hints

Instead of checking every subarray, first record the position of each value from 1 to n.
For a fixed k, the numbers 1..k can form a valid length-k subarray exactly when their minimum and maximum positions span k indices.

Approach

Key insight. The values 1..k are exactly k distinct numbers. They form a valid balanced subarray of length k iff the positions where they sit span a window of length exactly k — i.e. they are packed contiguously with no other (larger) value squeezed in between. If max_pos - min_pos + 1 == k, then k distinct values occupy k consecutive slots, so they must fill that window completely, and that window is the set {1,…,k}.

Algorithm.

Build pos, where pos[v] is the index of value v in p. Since p is a permutation, every value 1..n appears once.
Sweep k from 1 to n, incrementally maintaining min_pos and max_pos — the smallest and largest index among the positions of values {1,…,k}. Initialized from pos[1]; for each new k>1 we just fold in pos[k].
Append '1' when max_pos - min_pos + 1 == k, else '0'.

Why incremental works. Going from k-1 to k only adds value k, so the position set grows by one element; the running min/max update in O(1). No window ever shrinks, so a single forward pass suffices.

Correctness of the test. The span can never be smaller than k (k distinct positions need ≥ k slots), so == exactly characterizes "perfectly packed." Edge cases: k=1 always gives '1' (a single element is its own window); n=0 returns "".

Time complexity:

O(n)

Space complexity:

O(n)