Trim Down to a Hill

Hard

Call an array a **hill** if it has at least three elements and a summit: a position, neither first nor last, such that the elements strictly increase up to it and strictly decrease after it. You get an array values. Return the smallest number of elements to delete (the rest keep their order) so that a hill remains. This is guaranteed to be possible.

Example 1

values=[4, 1, 5, 7, 3, 3, 2] → 2

Remove the 1 and one of the 3s: [4, 5, 7, 3, 2] remains, climbing to 7 and then descending.

Example 2

values=[1, 2, 1] → 0

The array is already a hill.

Constraints

3 ≤ len(values) ≤ 1000
1 ≤ values[i] ≤ 10⁹
Deleting elements from values can leave a hill

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Binary Search Dynamic Programming

Similar problems

The Heaviest Reading Day Hard Pass the Load to the Left Medium Boxes Inside Boxes Hard Fuel Stops Along the Way Hard Numbers From Working Keys Hard

Input

values=[4, 1, 5, 7, 3, 3, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 98 tests on the server, hidden ones included.