Counting Valleys
Easy · Counting Warm-ups · String · Simulation · Prefix Sum
Problem
A hiker starts at sea level and takes steps steps, each described by a character in path:
- U — one step up
- D — one step down
A valley is any maximal stretch of the walk that starts with a step *below* sea level and ends when the hiker returns *to* sea level. Return the number of valleys walked through.
Examples
Input: steps = 8, path = "UDDDUDUU" Output: 1
The hiker dips below sea level once and comes back up once.
Input: steps = 8, path = "DDUUDDUU" Output: 2
Two separate dips below sea level.
Constraints
- 2 <= steps <= 10^6
- path[i] is 'U' or 'D'
- len(path) == steps
Approaches
- Sign-change scan over the altitude profile — time O(n), space O(1)
Related problems
Start free on Cariara · Coding problems · System design studio
