Loading...
Loading...
Loading...
Rahul wants his test marks to look like steady progress on his report. He has n marks in order, and he may hide one continuous block of tests (the block may be empty).
After hiding it, the remaining marks, in their original order, must never go down: each mark is at least the one before it. Print the length of the shortest block he must hide.
Example 1
Input
8 1 2 3 10 4 2 3 5
Output
3
Remove 10 4 2 to keep 1 2 3 3 5.
Example 2
Input
5 5 4 3 2 1
Output
4
Only one mark can stay, so 4 must go.
Try the problem first. Open one hint at a time.
What is left after removing a block is some starting part plus some ending part of the list.
The starting part must itself never go down, so it can only be a piece of the longest such prefix. The same holds for the ending part and the longest such suffix.
First try keeping only the prefix or only the suffix. Then try joining a prefix end i with a suffix start j, which needs mark[i] ≤ mark[j].
As i moves right through the prefix, the smallest valid j only moves right too. One pointer for each part gives a single pass.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor