HackerRank's counting valleys exercise in TypeScript

HackerRank has much more to offer than simple exercises, but I’m interested in how I conceptualize their solutions. For that reason, I’m focusing on the simpler ones, and writing down my thinking process. Today, it’s “Counting Valleys”:

Given Gary’s sequence of up and down steps during his last hike, find … the number of valleys he walked through.

I headed for a solution without properly reading the definition of a valley, though:

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.

This definition changes things a bit, so please have some patience for my initial flawed assumption.

In any case, a basic spec file with only a few test cases could be:

1
2
3
4
5
6
7
describe('Counting valleys', () => {
it('should match input to expected output', () => {
expect(countValleys(8, 'UUDDDDUU')).toEqual(1)
expect(countValleys(8, 'UDDDUDUU')).toEqual(1)
expect(countValleys(12, 'DDUUDDUDUUUD')).toEqual(2)
})
})

Here we go.

Basic skeleton: trying to parse the valleys and mountains

To map my thinking, I decided to use a class construct, first in pseudo-code. After I mapped how to handle each step, I defined the methods proper, arriving at the code below. Please note:

  • it doesn’t work on the 2nd test case, and
  • it is just a brain dump.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
export default function countValleys(
steps: number,
path: string
): number {
const counter = new ValleyCounter(steps, path)
return counter.numberOfValleys
}

class ValleyCounter {
private readonly steps: number
private readonly path: string

private weAreGoingUp: boolean
private weAreGoingDown: boolean
private mountainPeaks: number
private valleys: number
private currentLevel: number

constructor(steps: number, path: string) {
this.steps = steps
this.path = path

this.weAreGoingUp = false
this.weAreGoingDown = false
this.mountainPeaks = 0
this.valleys = 0
this.currentLevel = 0

this.runCounter()
}

private runCounter() {
for (let i = 0; i < this.steps; i++) {
const currentStep = this.path[i]
this.handleDirection(currentStep)
}
}

private handleDirection(d: string) {
if (d === 'U') {
this.goUp()
} else if (d === 'D') {
this.goDown()
} else {
throw new Error(`Direction ${d} is not valid`)
}
}

private goUp() {
if (this.weAreGoingDown) {
this.weStoppedGoingDown()
}

this.weAreGoingUp = true
this.weAreGoingDown = false
this.currentLevel += 1
}

private goDown() {
if (this.weAreGoingUp) {
this.weStoppedGoingUp()
}

this.weAreGoingUp = false
this.weAreGoingDown = true
this.currentLevel -= 1
}

private weStoppedGoingDown() {
if (this.currentLevel < 0) {
this.valleys += 1
}
}

private weStoppedGoingUp() {
if (this.currentLevel > 0) {
this.mountainPeaks += 1
}
}

get numberOfValleys() {
return this.valleys
}
}

The reason why the above fails on the 2nd test case, is that I simply assumed that all detections of a peak would constitute a mountain or valley. For example, given the path UDDDUDUU, we map it to:

1
2
3
_/\      _
\ /
\/\/

If you read the definition of a valley, there’s only 1 valley in the above path: it starts at 0, goes down to -2, up to -1, down to -2 again, and finally comes back to 0. Only when we get back to 0 can we say we found a valley.

Properly counting valleys

After realizing the solution is much simpler than I thought, I gave up on the class. Instead, we just have to detect when Gary arrives back at 0 from a negative number. If they’re at level 0 after having gone up, they just left a valley.

Another thing we can ignore is the first parameter: steps, which we can assume to be path.length.

The solution is much simpler:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
export default function countValleys(path: string): number {
let valleys = 0
let currentLevel = 0

for (let i = 0, steps = path.length; i < steps; i++) {
const direction = path[i]

if (direction === 'U') {
currentLevel += 1

if (currentLevel === 0) {
valleys += 1
}
} else if (direction === 'D') {
currentLevel -= 1
}
}

return valleys
}

Note that we keep track of a few variables but must iterate over the entire path, meaning we’re at O(n) time complexity.

Is it the best performance we can get? I don’t see a way to avoid iterating over path, so I’m assuming yes.