Balanced Values in a Permutation

MicrosoftPhone screenHard

You work with a permutation of the numbers 1 to n.

Part 1: Balanced values

You are given a permutation p of the numbers 1 to n: every number appears exactly once.

A value k with 1 <= k <= n is balanced when the values 1, 2, ..., k occupy a contiguous block of p — the cells holding exactly those values form one interval, with no other value inside it.

Return a string of n characters whose character at index k - 1 is 1 if k is balanced and 0 otherwise.

Example 1
n
5
p
[3,1,2,5,4]
Output
"11101"
Why: The values 1, 1 2 and 3 1 2 each fill a contiguous block, so k = 1, 2, 3 give 1. The values 1 to 4 sit at positions 1, 2, 0 and 4, spanning 5 cells, so k = 4 gives 0. For k = 5 the whole array is the block.

Constraints

1 <= n <= 2 * 10^5
len(p) == n
p contains each integer from 1 to n exactly once

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question