Katkat
Back

Find all balanced k in a permutation

MicrosoftSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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

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.