Find all balanced k in a permutation

Q: Find all balanced k in a permutation

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}.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Find all balanced k in a permutation

Quick Overview

Input

Output

Notes / expectations

Comments (0)