FastPrep
Problem · Binary Search

Maximum Domino Removals

● HardAmazonOA
See Amazon hiring insights

Amazon Games has introduced an exciting new game that revolves around dominoes! 🎲 The game consists of n dominoes, each having a distinct size represented by an array tiles.

In this game, the "order" of the dominoes is defined as the length of the longest strictly increasing subsequence (LIS) formed by their sizes.

Additionally, there is another array removalOrder, which contains integers ranging from 0 to n-1. These integers indicate the positions of dominoes that can be removed one by one in the specified sequence.

Your objective is to determine the maximum number of removals that can be performed while ensuring that the order (LIS) of the remaining dominoes remains at least a given threshold minOrder.

Parameters -

  • int tiles[n] – an array of n integers representing the sizes of dominoes.
  • int removalOrder[n] – an array specifying the sequence in which the dominoes should be removed.
  • int minOrder – an integer representing the minimum required LIS that must be maintained after removals.

    • Return -

    The function should return a single integer, which represents the maximum number of removals possible while keeping the longest strictly increasing subsequence at least minOrder.

    Examples
    01 · Example 1
    tiles = [1, 4, 4, 2, 5, 3]
removalOrder = [2, 1, 4, 0, 5, 3]
minOrder = 3
return = 3
    In this example, the player can remove dominoes in the order specified by remove. After each removal, the length of the LIS of the remaining dominoes should be at least min_order. The task is to find out the maximum number of such removals possible.
    More Amazon problems
    drafts saved locally
    public int maximumDominoRemovals(int[] tile, int[] removalOrder, int minOrder) {
  // write your code here
}
    tiles[1, 4, 4, 2, 5, 3]
    removalOrder[2, 1, 4, 0, 5, 3]
    minOrder3
    expected3
    sign in to submit