Dynamic Removals

Dynamic Removals

There is an array 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.

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

Output:
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.

Example:
Input: tiles = [1, 4, 4, 2, 5, 3], removalOrder = [2, 1, 4, 0, 5, 3], minOrder = 3
Output: 3
Explanation:
In this example, we can remove numbers 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.



Get one-to-one training from Google Facebook engineers

Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.

Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.