Determine if Hill or Valley

Question

This is my accepted submission for LeetCode. The problem is

You are given a 0-indexed integer array nums. An index i is part of a hill in nums if the closest non-equal neighbors of i are smaller than nums[i]. Similarly, an index i is part of a valley in nums if the closest non-equal neighbors of i are larger than nums[i]. Adjacent indices i and j are part of the same hill or valley if nums[i] == nums[j].

Note that for an index to be part of a hill or valley, it must have a non-equal neighbor on both the left and right of the index.

Return the number of hills and valleys in nums.

(from LeetCode website)

It seemed to make the most sense to break this out by cases basically using if/elif. Due to rules, it also made sense to me at the time to reverse the list and go backwards in order to find whether still in a hill or valley. Do you see any improvements I could make?

class Solution(object):
    def countHillValley(self, nums):
       hills = 0
       valley = 0
       for index, item in enumerate(nums):
         lastIndex = len(nums)-1
         prevItem = nums[index-1]
         nextItem = 0
         if index != lastIndex:
            nextItem = nums[index+1]
         # no left neighbor
         if index == 0:
            hills += 0
            valley += 0
         # last index, no right neighbor
         elif index == lastIndex:
            # at last index there is no non-equal
            # neighbor on the right
            # so index is neither a hill or a valley
            hills += 0
            valley += 0
         elif item > prevItem and item > nextItem:
            hills += 1
         elif item < prevItem and item == nextItem:
            # enumerate over remainder of list
            # start at next index
            # This creates a list slice
            # until find next non-equal neighbor
            for interiorIndex, interiorItem in enumerate(nums[index:]):
               if interiorItem != item:
                  if item < interiorItem:
                     valley += 1
                     break
                  if item > interiorItem:
                     hills += 0
                     break
         elif item < prevItem and item < nextItem:
            valley += 1
         elif item < prevItem and item > nextItem:
            valley += 0
         elif item > prevItem and item < nextItem:
            valley += 0
         elif item == prevItem and item > nextItem:
            reversedList = reversed(list(enumerate(nums[:index])))
            for prevIndex, prevItem in reversedList:
               if prevItem != item:
                  if item < prevItem:
                     hills += 0
                     valley += 0
                     break
                  if item > prevItem:
                     hills += 0
                     break
                  
         elif item > prevItem and item == nextItem:
            for interiorIndex, interiorItem in enumerate(nums[index:]):
               if interiorItem != item:
                  if item > interiorItem:
                     hills += 1
                     break
                  else:
                     valley += 0
                     break
       return hills+valley

Answer 1

The primary problem with your current implementation is its logical complexity. Your code looks generally reasonable and LeetCode says it works, so that's great -- congratulations in achieving the most important goal. However, I must admit that I lacked the patience to give it in-depth study. There's just a lot going on: several variables to mutate to keep track of things; several if-else branches to handle the different possibilities; and, worst of all, inner loops to look-ahead or look-behind to deal with the pesky problem of adjacent equal values. Rather than spend too much effort reviewing your specific code in great detail, I'll offer a different implementation that illustrates a few useful techniques that apply to many other types of problems.

Technique 1a: grouping equal values. As noted, the worst part of your current implementation is handling adjacent equal values. But those values don't affect the final result at all. So let's just get rid of them before doing anything else. Python's groupby function can do many useful things and is worth learning about, but its simplest behavior is to group equal values. The function emits (KEY, GROUP) tuples where the "key" is the value and the "group" is an iterable of those values. More commonly, one uses the function so that groups of related values can be processed in batches together, but in our case, we can ignore the groups and retain only the keys. This will give us a sequence with no pesky duplicates sitting side-by-side.

Technique 1b: pre-processing the data. More broadly, sometimes the best thing you can do to simplify a problem is to refuse to accept the provided data as given. When solving a problem on LeetCode, during a job interview, or when working on a project, don't be afraid to think a bit outside the box: rather than puzzling over how to solve the problem with the data at hand, try to imagine whether a different organization of the data (or a subset of it) would make life easier. Which leads us to the next technique.

Technique 2: zipping to look-behind or look-ahead in sequences. Many programming problems ask us to process a sequence of values while also knowing things about nearby values in the sequence. That's annoying because one has to worry about out-of-bounds problems. The resulting code tends to become logically complex as we keep track of prior values or attempt to peek ahead toward future values. A nice alternative is to zip the sequence together with a shifted version of itself, which allows us to process each value with full knowledge of its neighbors.

Technique 3: remembering that bool is a subclass of int. Specifically, true and false can function as one and zero in a numeric context. This means our function can just return a sum of logical evaluations.

Putting the techniques together. The code below illustrates one way to solve the problem. Although LeetCode was happy with it, it is not optimized for raw speed. Rather, its focus is code simplicity and intuitiveness: no if-else logic; no mutation of status values; just just two steps involving data reorganization and a final stage to sum over some boolean checks.

from itertools import groupby

class Solution(object):
    def countHillValley(self, nums):
        # Get rid of adjacent equal values.
        nums = [n for n, g in groupby(nums)]

        # Zip the sequence to itself so we can evaluate each number
        # alongside its neighbors to the left and right.
        z = zip(nums[:-2], nums[1:-1], nums[2:])

        # Count the hills and valleys. 
        return sum(
            lft > n < rgt or lft < n > rgt
            for lft, n, rgt in z
        )

Answer 2

One aspect of your code that makes it hard to read is that you're keeping track of too many variables. The problem doesn't ask for where the hills are, just how many. So, imagine you're driving along this terrain. How do you know when you've crossed a hill? When you've gone up then down. How do you know when you've crossed a valley? When you've gone down then up. All you need to track is what direction you went when you last changed elevation and what your previous elevation was.

class Solution(object):
    def countHillValley(self, nums):
        previousHeight = nums[0]
        lastElevationChange = 0 # -1 = descending, +1 = ascending
        hills = 0
        valleys = 0

        for height in nums:
            if height > previousHeight:
                if lastElevationChange == -1: # went down, now going up
                    valleys += 1
                lastElevationChange = +1
            elif height < previousHeight:
                if lastElevationChange == +1: # went up, now going down
                    hills += 1
                lastElevationChange = -1

            previousHeight = height

        return hills + valleys

Also, notice that I do nothing in the case of height == previousHeight. If a branch in your code requires no action, then don't write that branch. In your code, there are several places that look like this:

if index == 0:
   hills += 0
   valley += 0

This makes me wonder why this was written. Or, since these branches in your code are required to handle edge cases, make it explicit that nothing should be done:

if index == 0:
   continue

Answer 3

Additionally to Mark H's post I want to point your that your method can become very inefficient. nums[:index] and nums[index:] make a copy of a part of the nums-list. On average there are len(num)/2 elements copied and this may happen rather often. So if nums is very large your program will most of its execution time use for copying these lists.