FastPrepFeasible Indices After Prefix/Suffix Reduction

Feasible Indices After Prefix/Suffix Reduction

Amazon logoAmazon● MediumINTERNOA

Updated

Problem statement

Note: this problem is a copy of Feasible Indices After Reduction. The dates when it was seen are now listed on that version.

You are given an integer array arr of size n. All its elements are different.

You can use these two moves any number of times:

  1. Pick a non-empty prefix of the array: one or more elements taken from its start. Delete every element in it except the smallest one.
  2. Pick a non-empty suffix of the array: one or more elements taken from its end. Delete every element in it except the largest one.

After each move, the elements that are left join up into a new array.

Call an index i feasible if these moves can shrink the array down to the single element [arr[i]].

Return a binary string of length n, with one character for each index:

  • 1 means the index is feasible.
  • 0 means the index is not feasible.

Function

getFeasibleIndices(arr: int[]) → String

Examples

Example 1

arr = [1, 3, 2, 5, 4]return = "10011"

Constraints

  • 1 <= n <= 2 * 10^5
  • 1 <= arr[i] <= 10^6
  • All elements are distinct.

More Amazon Online Assessment questions

Similar questions at other companies

Interview reports that mention this question

Amazon interview experiences

See Amazon hiring insights
Saved
class Solution {
    public String getFeasibleIndices(int[] arr) {
      // write your code here
    }

}
Checking account…