Archived

monotonic array

An old note — I haven't updated it since I wrote it.

Interesting leetcode problem, and a lot harder than it may seem at first. Here's my slightly improved version of the official answer.

 1class Dir:
 2    inc = 1
 3    flat = 0
 4    dec = -1
 5
 6
 7def isMonotonic(A):
 8    store = Dir.flat
 9    cmp = lambda x, y: Dir.dec if x < y else (Dir.flat if x == y else Dir.inc)
10    for i in range(len(A) - 1):
11        d = cmp(A[i], A[i + 1])
12        if d in [Dir.inc, Dir.dec]:
13            store_initialized = store != 0
14            if store_initialized and d != store:
15                return False
16            store = d
17    return True
18
19
20assert isMonotonic([0, 0, 0, 0, 0])
21assert isMonotonic([0, 0, 0, 0, 1])
22assert isMonotonic([0, 0, 0, 1, 2])
23assert isMonotonic([-1, 0, 0, 1, 2])
24
25assert isMonotonic([-1, -2, 0, 1, 2]) == False
26
27assert isMonotonic([*reversed([0, 0, 0, 0, 0])])
28assert isMonotonic([*reversed([0, 0, 0, 0, 1])])
29assert isMonotonic([*reversed([0, 0, 0, 1, 2])])
30assert isMonotonic([*reversed([-1, 0, 0, 1, 2])])

This is quite a difficult problem since when deltas remain flat, the array remains monotonic. This makes it difficult to ascertain the direction (increasing or decreasing).

This serves as a good reminder about cmp, which was actually deprecated in python 3.

1cmp = lambda x, y: -1 if x < y else (0 if x == y else 1)

cmp offers richer information when comparing two values. In this case, it helps us ignore deltas that are neither go up or down.