FastPrep
Problem

Balanced Prefix Permutation

UberFULLTIMEOA
See Uber hiring insights

You are given a permutation p of size n. For each prefix p[0..k-1], determine whether it forms a valid permutation of the integers from 1 to k.

A prefix is valid if it contains every integer from 1 to k exactly once. Return a binary string of length n, where the k-th character is '1' if the prefix of length k is valid, and '0' otherwise.

Examples
01 · Example 1
p = [1, 4, 2, 3]
return = "1001"

The prefix [1] is a permutation of [1], and the full prefix [1,4,2,3] is a permutation of [1,2,3,4]. The middle prefixes are not valid.

02 · Example 2
p = [2, 1, 3]
return = "011"

The first prefix is not [1]. Prefixes of lengths 2 and 3 contain exactly 1..2 and 1..3.

Constraints
  • 1 <= p.length <= 2 * 10^5
  • p is a permutation of integers from 1 to p.length.
More Uber problems
drafts saved locally
public String countBalancedPrefixes(int[] p) {
  // write your code here
}
p[1, 4, 2, 3]
expected"1001"
sign in to submit