FastPrep
Problem · Array

Balanced Numbers

Learn this problem
● MediumExpedia logoExpediaINTERNOA

Problem statement

Given a permutation p of length n, a number k is balanced if there are two indices l and r with 1 <= l <= r <= n such that the numbers p[l], p[l + 1], ..., p[r] form a permutation of the numbers 1, 2, ..., k.

For each k with 1 <= k <= n, determine whether it is balanced. Return a binary string of length n whose k-th character is '1' if k is balanced and '0' otherwise.

A permutation of length n contains each integer from 1 to n exactly once, in any order.

Function

countBalancedNumbers(p: int[]) → String

Examples

Example 1

p = [4,1,3,2]return = "1011"
  • For k = 1, choose l = 2 and r = 2. The subarray is [1].
  • For k = 2, no subarray forms a permutation of [1, 2].
  • For k = 3, choose l = 2 and r = 4. The subarray is [1, 3, 2].
  • For k = 4, choose l = 1 and r = 4. The subarray is [4, 1, 3, 2].

Therefore, the answer is "1011".

Constraints

  • 1 <= n <= 2 * 10^5
  • 1 <= p[i] <= n
  • All values in p are distinct.

More Expedia problems

drafts saved locally
public String countBalancedNumbers(int[] p) {
  // write your code here
}
p[4,1,3,2]
expected"1011"
checking account