Determine balanced k values in a permutation

Q: Determine balanced k values in a permutation

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.

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

Determine balanced k values in a permutation

Quick Overview

Input

Output

Example

Constraints

Comments (0)