Feasible Indices After Reduction
Updated
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:
- Choose a prefix of the current array: one or more elements at its start. Delete every element in that prefix except the smallest one.
- Choose a suffix of the current array: one or more elements at its end. Delete every element in that suffix except the largest one.
After each operation, the elements that are left keep their order and 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. The first one is the smallest value in the array, at index 0, so reducing the whole array as a prefix leaves only it. The other two, at indices 3 and 4, are each larger than every value after them. The larger of them is the largest value overall, so reducing the whole array as a suffix leaves only it. For the other one, first reduce the prefix made of the first four values. That leaves two values, and reducing both as a suffix keeps only the larger one, which is the last value. No steps can leave a value from any other index, so only these three indices are feasible.
Example 2
arr = [4, 1, 3, 2]return = "1111"All four indices are feasible. Values 4 and 1 are each smaller than every value before them, while values 3 and 2 are each larger than every value after them. For example, start by reducing the prefix [4,1], which keeps only 1. To end with 3, reduce the suffix [3,2], then reduce the whole array as a suffix. To end with 2 instead, reduce the prefix made of the first two remaining values, then reduce the whole array as a suffix. So every index is feasible.
Constraints
1 <= n <= 10^51 <= arr[i] <= 10^9- All values in
arrare distinct.
More Amazon Online Assessment questions
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
- Task SchedulerOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Top K Frequent ElementsOA · PHONE SCREEN · Seen Nov 2026
- Get Smallest Base SegmentOA · Seen Nov 2026
- Minimum Cost of Left and Right PropagationOA · Seen Nov 2026
- Minimum Grid InconvenienceOA · Seen Nov 2026
- Maximize Shipment Order by Sorting One WindowOA · Seen Nov 2026
- Maximum Equal-Bit Pairs in a SubsequenceOA · Seen Nov 2026
- First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
- Two SumOA · PHONE SCREEN · Seen Nov 2026