How should I practice Balanced Permutation Subarrays?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Balanced Permutation Subarrays associated with Microsoft?

FastPrep tags this as a Microsoft online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Balanced Permutation Subarrays

Learn this problem

● Medium

MicrosoftINTERNNEW GRADOA

See Microsoft hiring insights

Problem statement

Given a permutation permutation of length n, determine for every integer k from 1 through n whether some contiguous subarray contains exactly the values 1, 2, ..., k, in any order.

Return a binary string of length n. Its character at zero-based index k - 1 must be '1' when such a subarray exists for k, and '0' otherwise.

A permutation of length n contains every integer from 1 through n exactly once.

Function

balancedPermutationSubarrays(permutation: int[]) → String

Examples

Example 1

permutation = [4,1,3,2]return = "1011"

For k = 1, the one-element subarray [1] works.
For k = 2, the values 1 and 2 are separated by 3, so no length-2 subarray contains exactly those values.
For k = 3, the subarray [1, 3, 2] works.
For k = 4, the whole permutation works.

The four decisions form "1011".

Example 2

permutation = [2,1,4,3,5]return = "11011"

The values 1 and 2 occupy one contiguous block, but adding 3 leaves the value 4 inside their positional span. Adding 4 makes that span contain exactly 1 through 4, and the whole permutation works for k = 5.

Constraints

1 <= permutation.length <= 200000
permutation is a permutation of the integers from 1 through permutation.length.