Pillar Hops
Problem
A row of n stone pillars has heights heights[0..n-1]. A climber starts on pillar 0 and wants to reach pillar n - 1. From pillar i they can hop to pillar i + 1 or pillar i + 2.
A hop from pillar i to pillar j costs |heights[i] - heights[j]| units of effort. Return the minimum total effort to reach the last pillar.
Example 1
- Input:
- heights = [10, 30, 40, 20]
- Output:
- 30
0 → 1 → 3: |10 - 30| + |30 - 20| = 20 + 10 = 30.
Example 2
- Input:
- heights = [30, 10, 60, 10, 60, 50]
- Output:
- 40
0 → 2 → 4 → 5: 30 + 0 + 10 = 40.
Constraints
- 1 ≤ heights.length ≤ 10^5
- 0 ≤ heights[i] ≤ 10^4
Hint
Show the first hint
Ask how you could have arrived at pillar i, not where to go from it.
Walkthrough
How to approach it
01Clarify before coding
- Is the cost the absolute difference, so going down costs as much as going up? Yes.
- With a single pillar, what is the answer? 0: you are already there.
- Can the climber hop backwards? No, only forward by one or two.
02Brute force
Recursively try both hops from every pillar and take the cheaper total. Memoising on the pillar index makes it linear.
Cost: Without memo: O(2ⁿ) calls. With memo: O(n) time and O(n) space, plus recursion depth n, which overflows Python's default stack at 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.