Problem
Feasible Indices After Reduction
Learn this problem
AmazonINTERNOAProblem 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:
- Choose a non-empty prefix of the current array and delete every element in that prefix except the minimum element of the prefix.
- 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[]) → StringExamples
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 <= 1051 <= arr[i] <= 109- All elements of
arrare distinct.