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.
time complexity is O(N)
space complexity is O(1)
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.
#!/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.