Frontend School

Maximum Path Points on Stepping Stones

DSA
easy

Maximum Path Points on Stepping Stones

Easy
Dynamic Programming
1D DP

Overview

Imagine you are a treasure hunter navigating a treacherous path made of stepping stones. Each stone has a certain number of points you can collect by landing on it. To make progress, you can only jump a short distance: either to the very next stone, or skip one stone and jump to the stone after that. Your mission is to find the path from the starting stone to the final stone that yields the maximum total points.

This problem evaluates your ability to model sequential decision-making using dynamic programming, a fundamental technique for optimizing over overlapping subproblems.

What you need to do / Task

Your task is to implement a function maxPathPoints that calculates the maximum total points achievable when traversing a path of stepping stones.

  1. Implement the maxPathPoints function.
  2. Ensure your solution correctly handles paths of varying lengths, including very short paths.
  3. Optimize for time and space complexity where appropriate.

Input & output

Input:

  • stones: An array of integers, stones[i] represents the points gained by landing on the i-th stone. The path starts at stones[0] and ends at stones[n-1].

Output:

  • An integer representing the maximum total points collected when reaching the last stone (stones[n-1]).

Function Signature (TypeScript):

function maxPathPoints(stones: number[]): number

Clarifications

  • Do I collect points from all intermediate stones? Yes, you collect points from every stone you land on, including the starting stone (stones[0]) and the ending stone (stones[n-1]).
  • What if stones contains negative values? The problem constraints will specify stones[i] >= 0.

Examples

1

Example 1

Input:

stones = [10, 20, 30, 40]

Output:

100

Note:

To reach stone 0: 10 To reach stone 1 (from 0): 10 + 20 = 30 To reach stone 2 (from max of reaching 0 or 1): 30 + max(10, 30) = 60 To reach stone 3 (from max of reaching 1 or 2): 40 + max(30, 60) = 100 Maximum points collected is 100.

2

Example 2

Input:

stones = [5]

Output:

5

Note:

With only one stone, you start and end on it, collecting its points.

3

Example 3

Input:

stones = [100, 1, 1, 100]

Output:

202

Note:

To reach stone 0: 100 To reach stone 1 (from 0): 100 + 1 = 101 To reach stone 2 (from max of reaching 0 or 1): 1 + max(100, 101) = 102 To reach stone 3 (from max of reaching 1 or 2): 100 + max(101, 102) = 202 Maximum points collected is 202.

Constraints

Constraints & assumptions

  • 1 <= stones.length <= 10^5 (denoted as n)
  • 0 <= stones[i] <= 1000
  • The answer is guaranteed to fit within a 32-bit signed integer.

Out of scope

  • Handling non-integer point values.
  • Validating the input array for non-numeric elements.
  • Finding all possible paths that yield the maximum points.

What interviewers evaluate

  • Problem understanding and DP formulation: Ability to correctly identify the optimal substructure and overlapping subproblems, and define the recurrence relation.
  • Algorithm correctness: The solution should pass all test cases, including edge cases like very short paths.
  • Time and space complexity: An efficient solution (O(N) time, O(1) or O(N) space) is expected.
  • Code clarity and maintainability: Well-structured, readable code with appropriate variable names.

Loading editor...