CATEGORY: EASY-MEDIUM
PRE-REQUISITES: Binary search, dynamic programming
PROBLEM:
You are asked to remove minimum number of students such that remaining students are standing in monotonically increasing order according to their height.
EXPLAINATION:
It is a simple LIS (Longest Increasing Subsequence) problem with a slight modification. In this question, you are to first calculate the LIS of the input array which is provided to you and after that take the difference of the number of students with the LIS you calculated. Since, the number of students N could be 10^6. Therefore, O(N^2) solution will not pass.
But, it can be solved in O(NlogN) time. All you need to do is to maintain an array, let’s call it DP [](it will store the height of the students in increasing order, initially empty). Now, traverse the original array (which contains the height of the students) from index 1 to N and at each index check whether DP is empty or not. If yes, then put that number into the DP and set the length of the LIS equal to 1, else do binary search and find the right place to put the number (height of the student), and last case if the number (height of the student) is greater than all the heights of the students present in the array DP, then put the number at the last and increase the value of LIS by 1.
NOTE: You may check how this algorithm is working by clicking on this link.
C++ CODE:
Link
Author: Suraj Singh
Tester: Naman Taneja
Editorialist: Suraj Singh