Problem

Feasible Indices After Reduction

AmazonINTERNOA
See Amazon hiring insights

You are given an integer array arr of size n. All elements of arr are distinct.

You may perform either of the following operations any number of times:

  1. Choose a non-empty prefix of the current array and delete every element in that prefix except the minimum element of the prefix.
  2. Choose a non-empty suffix of the current array and delete every element in that suffix except the maximum element of the suffix.

After each operation, the remaining elements are concatenated to form the new array.

An index i is called feasible if it is possible to reduce the array to the single element [arr[i]]. Return a binary string of length n where the i-th character is '1' if index i is feasible, and '0' otherwise.

Examples
01 · Example 1
arr = [1, 3, 2, 5, 4]
return = "10011"

The feasible values are 1, 5, and 4. They are the prefix minimum at index 0 or suffix maximums at indices 3 and 4.

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

Values 4 and 1 are prefix minimums, while 3 and 2 are suffix maximums.

Constraints
  • 1 <= arr.length <= 2 * 10^5
  • 1 <= arr[i] <= 10^6
  • All elements of arr are distinct.
More Amazon problems
drafts saved locally
public String feasibleIndicesAfterReduction(int[] arr) {
  // write your code here
}
arr[1, 3, 2, 5, 4]
expected"10011"
sign in to submit