Short Problem Definition:
Gary is an avid hiker. He tracks his hikes meticulously, paying close attention to small details like topography. During his last hike he took exactly n steps. For every step he took, he noted if it was an uphill, U, or a downhill, D step. Gary’s hikes start and end at sea level and each step up or down represents a 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.
Link
Complexity:
time complexity is O(N)
space complexity is O(1)
Execution:
I am a hiker myself, so this challenge is kinda funny. The description looks complex, but realistically one only needs to calculate whether the section was above or below sea level.
Solution:
def countingValleys(n, s):
level = 0
valleys = 0
for direction in s:
if direction == "U":
level += 1
if level == 0:
valleys += 1
else:
level -= 1
return valleys