FastPrep
Problem

Feasible Indices After Reduction

Learn this problem
Amazon logoAmazonINTERNOA
See Amazon hiring insights

Problem statement

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.

Function

feasibleIndicesAfterReduction(arr: int[]) → String

Examples

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.

Example 2

arr = [4, 1, 3, 2]return = "1100"
Values 4 (index 0) and 1 (index 1) are feasible. Value 4 is the maximum of the entire array, so applying the suffix operation on the full array reduces it to [4]. Value 1 is the minimum of the prefix [4,1], so applying the prefix operation on [4,1] reduces the array to [1,3,2], and then applying the suffix operation on [3,2] gives [1,3], and the prefix operation on [1,3] gives [1]. Values 3 (index 2) and 2 (index 3) are not feasible because 3 is not a suffix maximum of any reachable suffix (4 > 3 blocks it), and 2 is less than 3 in the suffix [3,2] so it can never be isolated as the last remaining element.

Constraints

  • 1 <= n <= 105
  • 1 <= arr[i] <= 109
  • 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"
checking account