Given a permutation p of length n, a number k is balanced if there are two indices l, r (l <= r) such that the numbers p[l], p[l + 1], …, p[r] form a permutation of the numbers 1, 2, ..., k.
For each k (1 <= k <= n), determine if it is balanced.
Return a binary string of length n where the i-th character is '1' if i is balanced and '0' otherwise.
A permutation of length n contains each integer from 1 to n exactly once, in any order.
Example
n = 4
p = [4, 1, 3, 2]- For
k = 1: Choosel = 2,r = 2, sop[2:2] = [1], which is a permutation of length 1. - For
k = 2: No pair of indices results in a permutation of length 2, so it is not balanced. - For
k = 3: Choosel = 2,r = 4, sop[2:4] = [1, 3, 2], which is a permutation of length 3. - For
k = 4: Choosel = 1,r = 4, sop[1:4] = [4, 1, 3, 2], which is a permutation of length 4.
The balanced numbers are 1, 3, and 4, while 2 is not balanced. Therefore, the answer is 1011.
Function Description
Complete the function countBalancedNumbers in the editor below.
int p[n]: the given permutationReturns string: the binary string as described
The key observation is that the numbers 1..k are balanced exactly when their positions in the permutation occupy one continuous segment. We can store the index of each value, then scan k from 1 to n while maintaining the minimum and maximum positions seen so far. If the segment length equals k, then those values form a contiguous subarray and k is balanced. This leads to a simple O(n) solution with O(n) extra space, which is efficient for large permutations.
