FastPrep
Problem

Balanced Permutation Subarrays

Learn this problem
Uber logoUberFULLTIMEOA
See Uber hiring insights

Problem statement

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.

Function

countBalancedNumbers(p: int[]) → String

Examples

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.

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.

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