Find all balanced k in a permutation
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a permutation \(p\) of length \(n\) containing each integer from \(1\) to \(n\) exactly once.
For each \(k\) where \(1 \le k \le n\), determine whether there exists a **contiguous subarray** of \(p\) whose elements are **exactly** the set \(\{1,2,\dots,k\}\) (in any order).
- If such a subarray exists, call \(k\) **balanced**.
- Output a binary string \(s\) of length \(n\) where \(s[k]\) (1-based) is `'1'` if \(k\) is balanced, otherwise `'0'`.
### Input
- Integer \(n\)
- Array \(p\) of length \(n\), a permutation of \([1..n]\)
### Output
- A string of length \(n\) consisting of `'0'` and `'1'`
### Notes / expectations
- Aim for an efficient algorithm (e.g., \(O(n)\) or \(O(n \log n)\)), not enumerating all subarrays.
Quick Answer: This question evaluates understanding of permutations, array range reasoning, index mapping, and efficient algorithm design for detecting contiguous subarrays that exactly contain the prefix set {1..k}.
You are given a permutation p of length n containing each integer from 1 to n exactly once.
For each k from 1 to n, determine whether there exists a contiguous subarray of p whose elements are exactly the set {1, 2, ..., k} in any order.
If such a subarray exists, then k is called balanced.
Return a binary string s of length n where s[k-1] is '1' if k is balanced, and '0' otherwise.
Constraints
- 1 <= n <= 2 * 10^5
- p is a permutation of the integers from 1 to n
Examples
Input: (5, [3, 1, 2, 5, 4])
Expected Output: '11101'
Explanation: For k = 1, 2, and 3, the positions of {1..k} form contiguous segments. For k = 4 they do not. For k = 5, the whole array works.
Input: (5, [2, 1, 4, 3, 5])
Expected Output: '11011'
Explanation: The sets {1}, {1,2}, {1,2,3,4}, and {1,2,3,4,5} each occupy contiguous positions, but {1,2,3} does not.
Hints
- Instead of checking every subarray, think about where each value 1, 2, ..., k appears in the permutation.
- For a fixed k, the values 1 through k form a valid contiguous subarray exactly when their minimum and maximum positions span a segment of length k.