9
\$\begingroup\$

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
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Why do you use These +=0 constructs and These elif Branchen doing Nothing useful? \$\endgroup\$
    – miracle173
    Jun 13 at 8:53

3 Answers 3

14
\$\begingroup\$

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
        )
\$\endgroup\$
6
  • 2
    \$\begingroup\$ This is amazing. I wasn't aware of zip. Love it. I have a lot to learn. \$\endgroup\$ Jun 12 at 1:46
  • 7
    \$\begingroup\$ Your valley and hill conditions can be shortened to left > n < right and left < n > right, respectively. Also, please don't use weird shortening of words unless you really need to, you already formatted it in such a way that there is plenty enough space to write out left and right. \$\endgroup\$
    – Graipher
    Jun 12 at 16:51
  • 2
    \$\begingroup\$ If you use z = zip(nums[:-2], nums[1:-1], nums[2:]), you do not need to check for None in the sum. \$\endgroup\$
    – Jasmijn
    Jun 13 at 4:25
  • 1
    \$\begingroup\$ @FMc I was actually thrown off by lft and rgt for a moment. I assumed they were acronyms (lft = left something something?, rgt = right greater than?) before I realized you were just randomly removing letters from left and right. I see no reason for this since it saves you all of 6 characters on your comparison line and only adds to the confusion for the reader. I don't think I've ever seen lft and rgt as common short-hand forms so perhaps you're always coding in a very particular focus, but it certainly isn't universal and far from conventional. \$\endgroup\$
    – zephyr
    Jun 13 at 18:51
  • 1
    \$\begingroup\$ Scratching my head over the level of concern about lft and rgt, yet not a peep about n, g, z, or nums. In context, all of the names are plenty intuitive – and certainly not "weird" or "randomly" constructed. \$\endgroup\$
    – FMc
    Jun 13 at 20:05
10
\$\begingroup\$

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
\$\endgroup\$
4
  • 2
    \$\begingroup\$ This is a useful review, because it sticks close to the spirit of the OP's strategy. For emphasis on the theme of reducing the number of variables, you could even ditch hills and valleys and just maintain a count. \$\endgroup\$
    – FMc
    Jun 12 at 15:45
  • 1
    \$\begingroup\$ Two other suggestions. (1) Declare constants for ASCENDING and DESCENDING for readability. (2) Less compelling, but worthing considering, is to drop the inner if-blocks and just write count += lastElevationChange == DESCENDING. But, again, a very useful review! \$\endgroup\$
    – FMc
    Jun 12 at 19:04
  • \$\begingroup\$ @FMc These are good suggestions. Keeping hills and valleys separate might be useful for debugging when stepping through the code. Named constants are also a good call. My one disagreement is count += lastElevationChange == DESCENDING. Even though bool is convertible to int, I don't like that kind of type mixing. I find myself staring at lines like that longer than other lines to make sure I understand what it's doing. Just a personal preference. \$\endgroup\$
    – Mark H
    Jun 13 at 1:02
  • \$\begingroup\$ You are right. When I was doing this on paper , I figured out from the problem set that when going up or down was really what it meant to say when it said “still in a valley” or “still in a hill”. I mapped out various test cases on graph paper then walked my code thru it. The extra += zero is really just leftover code I should have removed. \$\endgroup\$ Jun 13 at 17:12
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.