HackerRank ‘Counting Valleys’ Solution

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 1 unit change in altitude.

Link

Counting Valleys

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

All is required is a simple counter.

I find this problem specification oddly satisfying since I am currently finishing off my list of 48 4000 footers in New Hampshire, US.

Solution:
#!/bin/python

n = input()
s = raw_input()

level = 0
valleys = 0
for direction in s:
    if direction == "U":
        level += 1
        if level == 0:
            valleys += 1
    else:
        level -= 1
        
print valleys

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin