Funcia
Lv.2dequedpsliding-window

Stepping Stones Within K

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

NN 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

costkresult
[1, 100, 1, 1, 100, 1]24
[10, 5, 20, 1, 30]341
[7]17

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

  • 1≤N=1 \le N = cost.length ≤200,000\le 200{,}000
  • 1≤1 \le cost[i] ≤10,000\le 10{,}000
  • 1≤1 \le k ≤200,000\le 200{,}000 (k may exceed NN)
  • The answer may not fit in a 32-bit integer.

Expected complexity

Time
O(N)
Space
O(N)

Examples

costkExpected
[1,100,1,1,100,1]24
[10,5,20,1,30]341
[7]17

Hint

Hint

best[i] = cost[i] + min(best[j]) over i-k ≤ j < i. Scanning the whole window for every stone is O(Nk)O(Nk) 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 O(N)O(N).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251024 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.