How should I practice Get Balanced String?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Uber online assessment problems in FastPrep.

Is Get Balanced String associated with Uber?

FastPrep tags this as a Uber online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Get Balanced String

Learn this problem

● Medium

UberFULLTIMEOA

See Uber hiring insights

Problem statement

Given an array arr of length n which is a permutation of 1, 2, ..., n, a number k is called balanced if there exist two indices i and j such that arr[i], arr[i+1], ..., arr[j] is a permutation of 1, 2, ..., k.

Return a binary string of length n, where the character at 0-indexed position k-1 is '1' if k is balanced, and '0' otherwise.

Function

getBalancedString(arr: int[]) → String

Examples

Example 1

arr = [4, 1, 3, 2]return = "1011"

k=1: subarray [1] is a permutation of {1} → balanced.
k=2: no contiguous subarray equals {1, 2} → not balanced.
k=3: subarray [1, 3, 2] is a permutation of {1, 2, 3} → balanced.
k=4: full array [4, 1, 3, 2] is a permutation of {1, 2, 3, 4} → balanced.

Example 2

arr = [1, 2, 3]return = "111"

For every k from 1 to 3, the prefix arr[0..k-1] is already a permutation of {1, ..., k}.

Example 3

arr = [2, 3, 1]return = "101"

k=1: subarray [1] exists → balanced.
k=2: no contiguous subarray is exactly {1, 2} — elements 1 and 2 are separated by 3 → not balanced.
k=3: full array [2, 3, 1] is a permutation of {1, 2, 3} → balanced.

Example 4

arr = [1]return = "1"

Constraints

1 ≤ n ≤ 10⁵
arr is a permutation of 1, 2, ..., n