FastPrep
Problem

Balanced Prefix Permutation

Learn this problem
Uber logoUberFULLTIMEOA
See Uber hiring insights

Problem statement

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.

Function

countBalancedPrefixes(p: int[]) → String

Examples

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.

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"
checking account