Monotonic Lists

Photo by Samuel Sweet from Pexels

I watched a youtube video from Engineering with Utsav, and he mentioned a question that had to do with monotonically increasing linked lists. Having never heard of it before, the question intrigued me, and I looked it up. 

Turns out it simply required you to figure out if the linked list (or any similar data structure) had elements in an increasing or decreasing order. Easy right? Well... alright, I didn't succeed on my first (five) attempts.

Missteps

My original plan was to decide whether the array was increasing or decreasing - the monotonicity. This, I assumed, could be done by comparing the first two elements of the list. Once the monotonicity was established, it was simply a matter of traversing the rest of the data structure and validating whether the elements conformed.

I later learned through test failures that this would not work if the first two elements were identical (consecutive identical elements are allowed). 

Rework

Having given up on my original plan, I determined that establishing a monotonicity type wasn't relevant. The list could be traversed, and we could simultaneously check whether the elements were increasing or decreasing.

At the end of the run, we would have 4 possible outcomes

• The list has elements that are increasing and not decreasing.
• The list has elements that are not increasing but are decreasing.
• The list is not monotonic - neither increasing nor decreasing.
• The list has both increasing and decreasing elements (all identical elements)

Code

The for loop in the code iterates over the elements and establishes whether the list has increasing/ decreasing elements. 

Finally, the return statement checks if the items are identical or if the list is monotonic.

if len(nums) <= 2:
    return True;

increasing = True;
decreasing = True;

for i in range(0,len(nums)-1):
    increasing = increasing and nums[i] <= nums[i+1];
    decreasing = decreasing and nums[i] >= nums[i+1];

return (increasing == decreasing and increasing == True) or increasing != decreasing;