FastPrepFeasible Indices After Reduction
Problems/Feasible Indices After Reduction

Feasible Indices After Reduction

Amazon logoAmazonINTERNOA

Updated Nov 2026

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 prefix of the current array: one or more elements at its start. Delete every element in that prefix except the smallest one.
  2. 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[]) → String

Examples

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^5
  • 1 <= arr[i] <= 10^9
  • All values in arr are 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

Interview reports that mention this question

  • Amazon Intern OA Problems: Every Task We Have (Part 2 of 5)

Amazon interview experiences

  • Amazon Experienced SDE Onsite Questions: 1 Experience
  • Amazon SDE Onsite Interview Questions: 9 Experiences
  • Amazon SDE II and L5 FDE Interview Questions: 4 Experiences
  • Amazon Full-Time OA Problems, Earlier Reports (Part 5 of 5)
  • Amazon Full-Time OA Problems, Recent Reports (Part 4 of 5)
See Amazon hiring insights
Saved
class Solution {
    public String feasibleIndicesAfterReduction(int[] arr) {
      // write your code here
    }
}
Checking account…