The Cheapest Hill

Easy

You get an array heights with the heights of points along a trail. Call three positions i < j < k a **hill** if the middle point is strictly higher than both outer ones: heights[i] < heights[j] and heights[k] < heights[j]. The outer points do not have to be adjacent to the middle one. Return the smallest possible sum heights[i] + heights[j] + heights[k] over all hills, or -1 if there is no hill at all.

Example 1

heights=[7, 2, 9, 4, 6, 1] → 7

Indices 1, 3, 5 give 2 < 4 > 1 with sum 7, and nothing cheaper exists.

Example 2

heights=[1, 2, 3, 4] → -1

Heights only grow, so no point has a lower one to its right: there is no hill.

Example 3

heights=[5, 5, 5, 6, 5] → 16

Constraints

3 ≤ len(heights) ≤ 50
1 ≤ heights[i] ≤ 50

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array

Similar problems

Pair With a Target Sum Easy Squeeze Repeats Out of a Sorted Array Easy Drop the Unwanted Value Easy Slot on a Sorted Shelf Easy Add One to a Digit Array Easy

Input

heights=[7, 2, 9, 4, 6, 1]

Expected

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