FastPrep
Problem

Balanced Permutation Subarrays

UberFULLTIMEOA
See Uber hiring insights

You are given a permutation p of size n. For each value k from 1 to n, determine whether there exists a contiguous subarray whose elements form a permutation of the integers from 1 to k.

Return a binary string of length n. The k-th character is '1' if k is balanced, and '0' otherwise.

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

For k=1, the subarray [1] works. For k=2, no contiguous subarray contains exactly {1,2}. For k=3, [1,3,2] works, and for k=4, the full array works.

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

Each set {1..k} appears as a contiguous subarray for every k from 1 to 4.

03 · Example 3
p = [4, 1, 3, 2]
return = "1011"

For k=1, the subarray [1] works. For k=2, no contiguous subarray forms exactly {1,2}. For k=3, the subarray [1,3,2] works, and for k=4, the entire array works.

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 countBalancedNumbers(int[] p) {
  // write your code here
}
p[1, 3, 2, 4]
expected"1011"
sign in to submit