FastPrepFeasible Indices After Reduction
Problems/Feasible Indices After Reduction

Feasible Indices After Reduction

Amazon logoAmazonINTERNOA
QuestionFunctionExamplesConstraints

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 = "1111"

All four indices are feasible. Values 4 and 1 are prefix minima, while values 3 and 2 are suffix maxima. For example, after reducing prefix [4,1] to 1, value 3 can survive a reduction of suffix [3,2] and then the whole array. The same first step followed by reducing the whole remaining suffix can leave 2.

Constraints

  • 1 <= n <= 10^5
  • 1 <= arr[i] <= 10^9
  • All values in arr are distinct.

More Amazon problems

  • Count Adjacent Symbol Pairs for BPEONSITE INTERVIEW · Seen Nov 2026
  • First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
See Amazon hiring insights
Saved
public String feasibleIndicesAfterReduction(int[] arr) {
  // write your code here
}
Checking account…