Find All The Hills And Valley In A List

I am writing a function to find all the hills and valleys in a given list. For instance, [1,0,0,0,1] returns 3 and [0,1,0,1,0] returns 5. [0,2,2,1,1,0,0] returns 3. If a number (or

Solution 1:

Here's how I would do it:

• compute differences d between consecutive elements (remove 0s from result)
• count the number of times the sign changes in d
• return 2 plus that count (because there is a hill and a valley even in a monotonically increasing sequence)

In code:

def hill_and_vally(s):
    d=[x1-x0 for x0,x1 in zip(s,s[1:]) if x1!=x0]
    return 2+sum(d0*d1<0 for d0,d1 in zip(d,d[1:]))

of course it can be implemented with for loops and indexes, but zip and list comprehensions is more pythonic.

zip(s,s[1:]) is a common way to get pairs of adjacent elements in a list.

Tests:

>>> hill_and_vally([1,0,0,0,1])
3
>>> hill_and_vally([0,1,0,1,0])
5
>>> hill_and_vally([0,2,2,1,1,0,0])
3

Handling corner cases such as the reported [1,1,1,1] is left as an exercise :-)

Solution 2:

I know that the question is quite old and already answered, but recently solved the same problem with just one linear scan:

def solution(arr):
  prev = None
  curr = None
  total = 0

  for n in arr:
    if curr == None:
      curr = n
    else:
      if n != curr:
        if prev != None:
          if (prev < curr and n < curr) or (prev > curr and n > curr):
            total += 1
        else:
          prev = curr
          total += 1
        prev = curr
        curr = n

  if prev != curr:
    total += 1

  return total

It works well for all the inputs:

print(solution([1]))                   # 1
print(solution([1,2]))                 # 2
print(solution([1,1,1]))               # 1
print(solution([1,2,1]))               # 3
print(solution([1,2,6]))               # 2
print(solution([1,2,3,4,4,3,4,4,5,6])) # 4
print(solution([-10,2,2,2,2]))         # 2

print(solution([1,0,0,0,1]))           # 3
print(solution([0,1,0,1,0]))           # 5
print(solution([0,2,2,1,1,0,0]))       # 3

What it does, it keeps track of previous downhill/uphill and increments total counter if another appropriate downhill/uphill is met.