Loading…

easyStringsFrequently asked

Counting Valleys

Q: How do you solve Counting Valleys using the Brute Force — Reconstruct Altitude Array, Then Scan Segments approach?

When to use it: Mention it to show you understand the structure, then immediately collapse it into the one-pass counter — it's the same time complexity but wastes space. The most literal way to make this problem tangible is to materialize what 'altitude over time' means. Create an array `altitude` of length `n + 1` where `altitude[0] = 0` and each subsequent entry adds `+1` for `'U'` or `-1` for `'D'`. Now the abstract notion of a valley becomes a concrete shape in the array: a contiguous run of entries that dip below zero. **Why build the array at all.** For many candidates the prompt feels slippery — 'what exactly is a valley?' Drawing the altitude profile turns the words into a picture. Once you can *see* the negative runs, counting them is mechanical: a valley is one maximal stretch of negative values bracketed by zeros. **How the counting works on the array.** Walk the profile left to right. Track whether you are currently 'inside a valley' (the previous value was negative). The instant you step from a negative value back to exactly `0`, a valley just closed — increment the count. You never count on the way down, only on the surfacing. **Why we don't ship this.** Everything the second pass needs is already known *during* the first pass — the altitude at the current step. Storing the whole `altitude` array of size `n + 1` is pure waste: for `n = 10⁶` that's a million-entry array buying you nothing. The fix is to fuse the two passes and drop the array entirely, which is the optimal solution below. Time complexity: O(n). Space complexity: O(n).

Arrays & Hashing · 32 of 83 · 7 min

An avid hiker keeps detailed records of their hikes. During the last hike that took exactly steps steps, for every step it was noted if it was an uphill 'U' or a downhill 'D' step. Hikes always start and end at sea level, and each step up or down represents a 1 unit change in altitude.

We define the following terms:

A mountain is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level.
A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.

Given the sequence of up and down steps during a hike, find and return the number of valleys walked through.

In plain English

You walk a path of unit up/down steps starting at altitude 0. A valley is any maximal stretch spent strictly below 0. You must count how many such stretches occur — equivalently, how many times you climb back up to exactly 0 from a negative altitude.

Examples

Example 1

Input: steps = 8, path = "UDDDUDUU"
Output: 1
Note: Altitude trace: 1,0,-1,-2,-1,-2,-1,0. We go below sea level after step 2 and surface only at the final step → one valley.

Example 2

Input: steps = 12, path = "DDUUDDUDUUUD"
Output: 2
Note: Two separate below-sea-level segments. First valley: DDUU returns to 0. Then DD goes under again, and UDUUUD eventually surfaces → second valley.

Example 3

Input: steps = 4, path = "UUDD"
Output: 0
Note: Altitude: 1,2,1,0 — entirely a mountain, never below sea level. Zero valleys.

Constraints

2 ≤ steps ≤ 10⁶
path[i] ∈ {'U', 'D'}
The number of 'U' steps equals the number of 'D' steps (the hike starts and ends at sea level)

Clarifying questions4First question: Does the hike always start and end at sea level?Explore questions

Q1.Does the hike always start and end at sea level?
Yes — equal 'U' and 'D' counts are guaranteed. That means every dip below 0 is eventually closed, so counting surfacing events is safe.
Q2.Can altitude go above sea level, and do those count?
Yes it can, but mountains (above 0) are not what we count. Only below-sea-level valleys matter.
Q3.Should a valley with multiple internal bumps (e.g. DDUDDUUU) count as one valley or several?
One. A valley is a single maximal below-sea-level segment, counted once when you finally return to 0. This is exactly why we count the surfacing step, not every downward step.
Q4.Is the input a string or a char array?
Treat it as an ordered sequence of 'U'/'D' characters; iterate left to right. The data structure doesn't change the O(n) one-pass logic.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Track one integer — your altitude relative to sea level. Walk the string: 'U' adds 1, 'D' subtracts 1. A valley is counted at the exact moment you step back up to altitude 0 from below (the step that takes you from -1 to 0). Count those surfacing events in one pass: O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that the full path is irrelevant — that a single running altitude is sufficient state — and whether you pin down the exact moment a valley should be counted instead of hand-waving 'when I go below zero'.

Where candidates slip

Counting a valley every time altitude drops below 0 (so a single W-shaped valley with two dips gets counted twice), or counting on the 'D' that drops to -1 instead of the 'U' that returns to 0.

How to stand out

State the invariant out loud: 'a valley begins the first step below sea level and ends when I surface; I count exactly the surfacing step.' Name it as a running-sum/depth pattern and note it's the same shape as balanced-parentheses depth.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Reconstruct Altitude Array, Then Scan Segments	`O(n)`	`O(n)`	Mention it to show you understand the structure, then immediately collapse it into the one-pass counter — it's the same time complexity but wastes space.	Read
2	One-Pass Running Altitude Counter (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'I keep one altitude counter and count the step that surfaces me' — not just 'I loop through the string'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewRead next stepStep is U or D?UDExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Reconstruct Altitude Array, Then Scan Segments

TimeO(n)SpaceO(n)

Mention it to show you understand the structure, then immediately collapse it into the one-pass counter — it's the same time complexity but wastes space.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

First make the problem concrete: build the full altitude profile as an array, where altitude[k] is your height after k steps.

2Hint 2Explore hint

Now a valley is a maximal run of entries that are strictly below 0. How would you count maximal negative runs in an array?

3Hint 3Explore hint

Walk the altitude array; each time you transition from a negative value back to 0, you've closed one valley. Count those transitions.

A · Core idea

The most literal way to make this problem tangible is to materialize what 'altitude over time' means. Create an array altitude of length n + 1 where altitude[0] = 0 and each subsequent entry adds +1 for 'U' or -1 for 'D'. Now the abstract notion of a valley becomes a concrete shape in the array: a contiguous run of entries that dip below zero.

Why build the array at all. For many candidates the prompt feels slippery — 'what exactly is a valley?' Drawing the altitude profile turns the words into a picture. Once you can see the negative runs, counting them is mechanical: a valley is one maximal stretch of negative values bracketed by zeros.

How the counting works on the array. Walk the profile left to right. Track whether you are currently 'inside a valley' (the previous value was negative). The instant you step from a negative value back to exactly 0, a valley just closed — increment the count. You never count on the way down, only on the surfacing.

Why we don't ship this. Everything the second pass needs is already known during the first pass — the altitude at the current step. Storing the whole altitude array of size n + 1 is pure waste: for n = 10⁶ that's a million-entry array buying you nothing. The fix is to fuse the two passes and drop the array entirely, which is the optimal solution below.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

path = "UDDDUDUU"

Array state

profile built

altitudes after each step

[0]

[1]

[2]

-1

[3]

-2

[4]

-1

[5]

-2

[6]

-1

[7]

[8]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

Reference implementation previewpublic int countingValleys(int steps, String path) { int n = path.length(); int[] altitude = new int[n + 1]; for (int i = 0; i < n; i++) { altitude[i + 1] = altitude[i] + (path.charAt(i) == 'U' ? 1 : -1);Explore the full code

solution.javaJava

Brute Force — Reconstruct Altitude Array, Then Scan Segments — reference

2 teaching notes

1
public int countingValleys(int steps, String path) {
2
    int n = path.length();
3
    int[] altitude = new int[n + 1];
4
    for (int i = 0; i < n; i++) {
5
        // Prefix-style build: each altitude is the previous plus this step's unit
6
        // change.
7
        altitude[i + 1] = altitude[i] + (path.charAt(i) == 'U' ? 1 : -1);
8
    }
9
    int valleys = 0;
10
    for (int i = 1; i <= n; i++) {
11
        // A valley closes only on a 0 reached from a negative value — this is the
12
        // surfacing test.
13
        if (altitude[i] == 0 && altitude[i - 1] < 0) {
14
            valleys++;
15
        }
16
    }
17
    return valleys;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Materializing the altitude profile is a great whiteboard move to understand the problem, but it exposes that the only fact you ever consult is 'what is my altitude right now?'. Anything you can compute on the fly should not be stored — that realization is what turns this O(n)-space sketch into the O(1)-space answer.

ComplexityO(n) time, O(n) space — Building the altitude array is one pass over n steps. Scanning it for negative runs is another pass. Two O(n) passes is still O(n) time, but storing the full profile costs O(n) extra space we don't actually need.

E · Edge cases and pitfalls3Allocating an O(n) array when a single integer suffices — wasteful on 10⁶ steps.Explore edge cases

Pitfalls

Allocating an O(n) array when a single integer suffices — wasteful on 10⁶ steps.
Counting every negative entry instead of each negative→0 transition — massively over-counts.
Off-by-one when indexing the n+1 altitude array versus the n-length path.

03.2

Approach 2 of 2 · Optimal

One-Pass Running Altitude Counter (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'I keep one altitude counter and count the step that surfaces me' — not just 'I loop through the string'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The brute force stored a whole altitude array, but at any moment you only ever read the current altitude. What if you kept just that one number?

2Hint 2Explore hint

Maintain a single integer altitude. 'U' adds 1, 'D' subtracts 1. The only question left is: at which step do I increment the valley count?

3Hint 3Explore hint

You're surfacing from a valley exactly when a 'U' step makes altitude become 0. Equivalently: the step was 'U' and the new altitude is 0. Count those.

A · Core idea

Walk the path once, holding a single integer altitude (starts at 0) and a valleys counter. For each character, adjust altitude by +1 for 'U' or -1 for 'D'. Then ask one question: did this step just bring me back to sea level from below?

The state collapse that makes this optimal. The brute force kept an entire altitude array, but notice every decision used only the current altitude. Past altitudes never get re-read. That's the signal to throw away history and keep a single running number — the classic running-sum compression from O(n) space to O(1).

Pinning the exact counting moment. The subtle part is when to increment valleys. A valley is a maximal below-sea-level run, so it must be counted exactly once. The cleanest invariant: count the step that closes the valley — the 'U' step after which altitude == 0. Why this step and not, say, the first 'D' that drops below 0? Because a single valley can dip, rise partway, and dip again (DDUDD...) — but it touches altitude == 0 only when it is truly finished. Tying the count to 'surfaced to 0' guarantees one increment per valley regardless of internal wiggles.

Why `step == 'U' && altitude == 0` is the right test. After applying a 'U', altitude increased by 1. If it landed on 0, the previous altitude was -1 — you were below sea level and just stepped up to the surface. That is the definition of finishing a valley. A 'D' can never land you on 0 from below (it only goes lower), so guarding on 'U' is both correct and a touch faster. In practice checking altitude == 0 right after a 'U' is enough, since only an upward step can reach 0 from −1.

Why no special-casing is needed for the end. Because the hike is guaranteed to end at sea level, any valley that opened is guaranteed to close, and its closing 'U' is counted naturally inside the loop. There is no leftover state to flush after the loop ends.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

path = "UDDDUDUU"

Array state

start

altitude = 0 at sea level

i ↓

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

solution.javaJava

One-Pass Running Altitude Counter (Optimal) — optimal

4 teaching notes

1
public int countingValleys(int steps, String path) {
2
    // The entire state — your height relative to sea level. No array needed.
3
    int altitude = 0;
4
    int valleys = 0;
5
    for (int i = 0; i < path.length(); i++) {
6
        // Only an upward step can close a valley, so we branch on it.
7
        if (path.charAt(i) == 'U') {
8
            altitude++;
9
            // Landed on 0 after a 'U' → you just surfaced from below → a valley ended.
10
            if (altitude == 0) {
11
                // Count exactly the surfacing event — once per valley, no matter how
12
                // bumpy it was.
13
                valleys++;
14
            }
15
        } else {
16
            altitude--;
17
        }
18
    }
19
    return valleys;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

This is the purest form of the running-sum pattern: replace a stored sequence with one accumulator and a well-chosen 'event' to count. The hard part is never the loop — it's defining the single moment that uniquely identifies the thing you're counting. Here that moment is 'surfaced to 0', which fires exactly once per valley. The same discipline (count the closing event, not the opening one) reappears in balanced-parentheses depth and 'minimum add to make parentheses valid'.

ComplexityO(n) time, O(1) space — Exactly one pass over n characters, doing O(1) work each (one comparison, one add, one conditional). No auxiliary storage beyond two integers → O(n) time, O(1) space.

E · Edge cases and pitfalls6path = "UDUDUDUD" — Altitude oscillates 1,0,1,0,... and never goes negative. No 'U' ever lands on 0 from below, so valleys = 0. Confirms surfacing-from-above is not counted.Explore edge cases

Edge cases handled

path = "UDUDUDUD"Altitude oscillates 1,0,1,0,... and never goes negative. No 'U' ever lands on 0 from below, so valleys = 0. Confirms surfacing-from-above is not counted.
path = "DUDUDUDU"Each 'D' drops to -1 and each following 'U' returns to 0 → four separate valleys. Returns 4, showing each surfacing event counts independently.
path = "DDDUUU"One deep valley to -3 then back to 0. Only the final 'U' lands on 0 → valleys = 1, proving internal depth doesn't inflate the count.

Pitfalls

Counting on the 'D' that first goes below 0 instead of the 'U' that surfaces — over-counts valleys with multiple dips.
Forgetting the altitude == 0 guard and counting every 'U' — returns the number of up-steps, not valleys.
Counting when altitude returns to 0 from above (closing a mountain) — only below-sea-level segments are valleys.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int countingValleys(int steps, String path) { int altitude = 0; int valleys = 0; for (int i = 0; i < path.length(); i++) { if (path.charAt(i) == 'U') {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Counting on descent instead of ascent

A valley like DDUDD...UUU dips, rises partway, and dips again. Counting every downward crossing of 0 (or every first 'D') counts internal wiggles as separate valleys. Count the single surfacing step instead.

Explore the code comparison

Don't write this

if (path.charAt(i) == 'D') {
    altitude--;
    if (altitude == -1) {   // 'just went below sea level'
        valleys++;
    }
}

Write this instead

if (path.charAt(i) == 'U') {
    altitude++;
    if (altitude == 0) {   // 'surfaced from a valley'
        valleys++;
    }
}

Missing the altitude == 0 guard

Incrementing valleys on every 'U' returns the total number of up-steps, not the number of valleys. The guard restricts counting to the surfacing step only.

Explore the code comparison

Don't write this

if step == 'U':
    altitude += 1
    valleys += 1   # counts every up-step

Write this instead

if step == 'U':
    altitude += 1
    if altitude == 0:
        valleys += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Running altitude counter + surface-from-below detection

Code pattern to memorize

altitude = 0
valleys = 0
for step in path:
    altitude += 1 if step == 'U' else -1
    if step == 'U' and altitude == 0:   # just surfaced
        valleys += 1

Rules to remember

1A valley is counted when you climb back to 0 from below — i.e. a 'U' that lands you exactly on altitude == 0.
2Do not count valleys when you enter them (going below 0) — count them when you exit at sea level. Counting entries double-counts a valley with multiple dips.
3The mountain analog (peak ending at 0 from above) is irrelevant here — only below-sea-level segments are valleys.
4You never need the whole path stored — one altitude integer is the entire state. Resist building arrays.
5Equal numbers of 'U' and 'D' are guaranteed, so you always return to 0 — but never assume that in code; let the loop drive it.

Use this pattern when

A sequence of +1/−1 (or open/close, in/out) events and you must count how many times a running total crosses or returns to a threshold
Balanced-parenthesis-style problems where depth matters
Streaming input where you only care about a running aggregate, not the history
'Count the number of complete dips below a baseline' style prompts

Choose another pattern when

You need the actual valley contents or their lengths → you'd track start/end indices, not just a counter
Steps have variable magnitude (not unit ±1) → still a running sum, but the 'crossing 0' test needs care
Nested structure with types that must match (different bracket kinds) → that's a stack problem, not a counter

Interview takeaway

When events are just +1/−1, the entire problem collapses to a single running integer. Counting Valleys is the gateway example of the running-sum pattern — the same trick powers balanced-parentheses depth, 'minimum add to make valid', and stock-span style scans.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical Running-Sum / Depth Counter. Recognise it whenever events are unit ±1 changes and you must count threshold crossings or returns to a baseline. The key skill is choosing the single 'event' that uniquely identifies each thing you count — here, the 'U' that surfaces to 0. Same shape as balanced-parentheses depth and minimum-add-to-make-valid.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Score After Splitting a String
Coming soon
Same running-count idea — track zeros on the left and ones on the right in one or two passes.
Minimum Add to Make Parentheses Valid
Coming soon
Running depth counter; '(' is +1, ')' is -1, and you act when depth would go negative — the same surfacing logic.
Number of Students Unable to Eat Lunch
Coming soon
Simulate a queue with a running tally instead of storing the whole sequence.

Same pattern

←

CamelCase

Continue · Next problem

Mars Exploration

easyStringsFrequently asked

Counting Valleys

Arrays & Hashing · 32 of 83 · 7 min

We define the following terms:

A mountain is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level.
A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.

Given the sequence of up and down steps during a hike, find and return the number of valleys walked through.

In plain English

Examples

Example 1

Input: steps = 8, path = "UDDDUDUU"
Output: 1
Note: Altitude trace: 1,0,-1,-2,-1,-2,-1,0. We go below sea level after step 2 and surface only at the final step → one valley.

Example 2

Input: steps = 12, path = "DDUUDDUDUUUD"
Output: 2
Note: Two separate below-sea-level segments. First valley: DDUU returns to 0. Then DD goes under again, and UDUUUD eventually surfaces → second valley.

Example 3

Input: steps = 4, path = "UUDD"
Output: 0
Note: Altitude: 1,2,1,0 — entirely a mountain, never below sea level. Zero valleys.

Constraints

2 ≤ steps ≤ 10⁶
path[i] ∈ {'U', 'D'}
The number of 'U' steps equals the number of 'D' steps (the hike starts and ends at sea level)

Clarifying questions4First question: Does the hike always start and end at sea level?Explore questions

Q1.Does the hike always start and end at sea level?
Yes — equal 'U' and 'D' counts are guaranteed. That means every dip below 0 is eventually closed, so counting surfacing events is safe.
Q2.Can altitude go above sea level, and do those count?
Yes it can, but mountains (above 0) are not what we count. Only below-sea-level valleys matter.
Q3.Should a valley with multiple internal bumps (e.g. DDUDDUUU) count as one valley or several?
One. A valley is a single maximal below-sea-level segment, counted once when you finally return to 0. This is exactly why we count the surfacing step, not every downward step.
Q4.Is the input a string or a char array?
Treat it as an ordered sequence of 'U'/'D' characters; iterate left to right. The data structure doesn't change the O(n) one-pass logic.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Counting a valley every time altitude drops below 0 (so a single W-shaped valley with two dips gets counted twice), or counting on the 'D' that drops to -1 instead of the 'U' that returns to 0.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Reconstruct Altitude Array, Then Scan Segments	`O(n)`	`O(n)`	Mention it to show you understand the structure, then immediately collapse it into the one-pass counter — it's the same time complexity but wastes space.	Read
2	One-Pass Running Altitude Counter (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'I keep one altitude counter and count the step that surfaces me' — not just 'I loop through the string'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Reconstruct Altitude Array, Then Scan Segments

TimeO(n)SpaceO(n)

Mention it to show you understand the structure, then immediately collapse it into the one-pass counter — it's the same time complexity but wastes space.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

First make the problem concrete: build the full altitude profile as an array, where altitude[k] is your height after k steps.

2Hint 2Explore hint

Now a valley is a maximal run of entries that are strictly below 0. How would you count maximal negative runs in an array?

3Hint 3Explore hint

Walk the altitude array; each time you transition from a negative value back to 0, you've closed one valley. Count those transitions.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

path = "UDDDUDUU"

Array state

profile built

altitudes after each step

[0]

[1]

[2]

-1

[3]

-2

[4]

-1

[5]

-2

[6]

-1

[7]

[8]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

solution.javaJava

Brute Force — Reconstruct Altitude Array, Then Scan Segments — reference

2 teaching notes

1
public int countingValleys(int steps, String path) {
2
    int n = path.length();
3
    int[] altitude = new int[n + 1];
4
    for (int i = 0; i < n; i++) {
5
        // Prefix-style build: each altitude is the previous plus this step's unit
6
        // change.
7
        altitude[i + 1] = altitude[i] + (path.charAt(i) == 'U' ? 1 : -1);
8
    }
9
    int valleys = 0;
10
    for (int i = 1; i <= n; i++) {
11
        // A valley closes only on a 0 reached from a negative value — this is the
12
        // surfacing test.
13
        if (altitude[i] == 0 && altitude[i - 1] < 0) {
14
            valleys++;
15
        }
16
    }
17
    return valleys;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Allocating an O(n) array when a single integer suffices — wasteful on 10⁶ steps.Explore edge cases

Pitfalls

Allocating an O(n) array when a single integer suffices — wasteful on 10⁶ steps.
Counting every negative entry instead of each negative→0 transition — massively over-counts.
Off-by-one when indexing the n+1 altitude array versus the n-length path.

03.2

Approach 2 of 2 · Optimal

One-Pass Running Altitude Counter (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'I keep one altitude counter and count the step that surfaces me' — not just 'I loop through the string'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The brute force stored a whole altitude array, but at any moment you only ever read the current altitude. What if you kept just that one number?

2Hint 2Explore hint

Maintain a single integer altitude. 'U' adds 1, 'D' subtracts 1. The only question left is: at which step do I increment the valley count?

3Hint 3Explore hint

You're surfacing from a valley exactly when a 'U' step makes altitude become 0. Equivalently: the step was 'U' and the new altitude is 0. Count those.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

path = "UDDDUDUU"

Array state

start

altitude = 0 at sea level

i ↓

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

solution.javaJava

One-Pass Running Altitude Counter (Optimal) — optimal

4 teaching notes

1
public int countingValleys(int steps, String path) {
2
    // The entire state — your height relative to sea level. No array needed.
3
    int altitude = 0;
4
    int valleys = 0;
5
    for (int i = 0; i < path.length(); i++) {
6
        // Only an upward step can close a valley, so we branch on it.
7
        if (path.charAt(i) == 'U') {
8
            altitude++;
9
            // Landed on 0 after a 'U' → you just surfaced from below → a valley ended.
10
            if (altitude == 0) {
11
                // Count exactly the surfacing event — once per valley, no matter how
12
                // bumpy it was.
13
                valleys++;
14
            }
15
        } else {
16
            altitude--;
17
        }
18
    }
19
    return valleys;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Edge cases handled

path = "UDUDUDUD"Altitude oscillates 1,0,1,0,... and never goes negative. No 'U' ever lands on 0 from below, so valleys = 0. Confirms surfacing-from-above is not counted.
path = "DUDUDUDU"Each 'D' drops to -1 and each following 'U' returns to 0 → four separate valleys. Returns 4, showing each surfacing event counts independently.
path = "DDDUUU"One deep valley to -3 then back to 0. Only the final 'U' lands on 0 → valleys = 1, proving internal depth doesn't inflate the count.

Pitfalls

Counting on the 'D' that first goes below 0 instead of the 'U' that surfaces — over-counts valleys with multiple dips.
Forgetting the altitude == 0 guard and counting every 'U' — returns the number of up-steps, not valleys.
Counting when altitude returns to 0 from above (closing a mountain) — only below-sea-level segments are valleys.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Counting on descent instead of ascent

Explore the code comparison

Don't write this

if (path.charAt(i) == 'D') {
    altitude--;
    if (altitude == -1) {   // 'just went below sea level'
        valleys++;
    }
}

Write this instead

if (path.charAt(i) == 'U') {
    altitude++;
    if (altitude == 0) {   // 'surfaced from a valley'
        valleys++;
    }
}

Missing the altitude == 0 guard

Incrementing valleys on every 'U' returns the total number of up-steps, not the number of valleys. The guard restricts counting to the surfacing step only.

Explore the code comparison

Don't write this

if step == 'U':
    altitude += 1
    valleys += 1   # counts every up-step

Write this instead

if step == 'U':
    altitude += 1
    if altitude == 0:
        valleys += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Running altitude counter + surface-from-below detection

Code pattern to memorize

altitude = 0
valleys = 0
for step in path:
    altitude += 1 if step == 'U' else -1
    if step == 'U' and altitude == 0:   # just surfaced
        valleys += 1

Rules to remember

1A valley is counted when you climb back to 0 from below — i.e. a 'U' that lands you exactly on altitude == 0.
2Do not count valleys when you enter them (going below 0) — count them when you exit at sea level. Counting entries double-counts a valley with multiple dips.
3The mountain analog (peak ending at 0 from above) is irrelevant here — only below-sea-level segments are valleys.
4You never need the whole path stored — one altitude integer is the entire state. Resist building arrays.
5Equal numbers of 'U' and 'D' are guaranteed, so you always return to 0 — but never assume that in code; let the loop drive it.

Use this pattern when

A sequence of +1/−1 (or open/close, in/out) events and you must count how many times a running total crosses or returns to a threshold
Balanced-parenthesis-style problems where depth matters
Streaming input where you only care about a running aggregate, not the history
'Count the number of complete dips below a baseline' style prompts

Choose another pattern when

You need the actual valley contents or their lengths → you'd track start/end indices, not just a counter
Steps have variable magnitude (not unit ±1) → still a running sum, but the 'crossing 0' test needs care
Nested structure with types that must match (different bracket kinds) → that's a stack problem, not a counter

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Score After Splitting a String
Coming soon
Same running-count idea — track zeros on the left and ones on the right in one or two passes.
Minimum Add to Make Parentheses Valid
Coming soon
Running depth counter; '(' is +1, ')' is -1, and you act when depth would go negative — the same surfacing logic.
Number of Students Unable to Eat Lunch
Coming soon
Simulate a queue with a running tally instead of storing the whole sequence.

Same pattern

←

CamelCase

Continue · Next problem

Mars Exploration