Katkat
Back

Determine balanced k values in a permutation

UberSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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.