Stepping Stones Within K
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
stepping stones are lined up across a stream, numbered 0 to N-1. Stepping on stone i costs cost[i].
You start on stone 0 and must reach stone N-1. Each jump moves you forward by at least 1 and at most k stones.
Return the minimum possible sum of the costs of all stones you step on, including the first and the last stone.
Examples
| cost | k | result |
|---|---|---|
[1, 100, 1, 1, 100, 1] | 2 | 4 |
[10, 5, 20, 1, 30] | 3 | 41 |
[7] | 1 | 7 |
Example 1 — Stones 0 → 2 → 3 → 5 cost 1 + 1 + 1 + 1 = 4; both stones of cost 100 are skipped.
Example 2 — 0 → 3 → 4 costs 10 + 1 + 30 = 41. The last stone must always be paid.
Example 3 — With a single stone you are already at the destination.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(cost: int[], k: int) → long
Constraints
-
cost.length -
cost[i] -
k(kmay exceed ) - The answer may not fit in a 32-bit integer.
Expected complexity
- Time
- O(N)
- Space
- O(N)
Examples
| cost | k | Expected |
|---|---|---|
[1,100,1,1,100,1] | 2 | 4 |
[10,5,20,1,30] | 3 | 41 |
[7] | 1 | 7 |
Hint
Hint
best[i] = cost[i] + min(best[j]) over i-k ≤ j < i. Scanning the whole window for every stone is and times out.
Keep a monotonic deque of indices with increasing best: drop indices that left the window from the front, and drop values
≥ best[i] from the back before pushing i. Every index enters and leaves once, so the whole DP is .
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1024 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |