Determine balanced k values in a permutation
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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.
Quick Answer: 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.