Return the depth of the deepest pit in array

pit_depth.md

A non-empty zero-indexed array A consisting of N integers is given. A pit in this aray is any triplet of integers (P, Q, R) such that:

• 0 <= P < Q < R < N;
• sequence [A[P], A[P+1], ... , A[Q]] is strictly decreasing, i.e. A[P] > A[P+1] > ... > A[Q];
• sequence A[P+1], ... , A[R] is strictly increasing, i.e. A[Q] < A[Q+1] < ... < A[R].

The depth of a pit(P, Q, R) is the number min{A[P] - A[Q], A[R] - A[Q]}.

For example, consider array A consisting of 10 elements such that:

A[0] =  0
A[1] =  1
A[2] =  3
A[3] = -2
A[4] =  0
A[5] =  1
A[6] =  0
A[7] = -3
A[8] =  2
A[9] =  3

Triplet(2, 3, 4) is one of pits in this array, because sequence[A[2], A[3]] is strictly decreasing (3 > -2) and sequence [A[3], A[4]] is strictly increasing (-2 < 0). Its depth is min{A[2] - A[3], A[4] - A[3]} = 2. Triplet(2, 3, 5) is another pit with depth 3. Triplet (5, 7, 8) is yeet another pit with depth 4. There is no pit in this array deeper than 4.

Write a function:

    def func(A)

that, given a non-empty zero-indexed array A consisting of N integers, returns the depth of the deepest pit in array A. The function should return -1 if there are no pits in array A.

For example, consider array A consisting of 10 elements such that:

A[0] =  0
A[1] =  1
A[2] =  3
A[3] = -2
A[4] =  0
A[5] =  1
A[6] =  0
A[7] = -3
A[8] =  2
A[9] =  3

the function should return 4, as explained above.

Assume that:

• N is an integer within the range[1 ... 1,000,000];
• each element of array A is an integer within the range [-100,000,000 ... 100,000,000].

pit_depth.py

def func(data):
    def get_state(x, y):
        if x > y:
            return 'down'
        elif y > x:
            return 'up'
        else:
            return 'wait'

    result = -1

    if len(data) < 3:
        return result

    down, mid, up = 0, 0, 0
    state = get_state(data[0], data[1])
    for i in range(1, len(data)):
        next_state = 'wait'
        if i+1 < len(data):
            next_state = get_state(data[i], data[i+1])

        if state == 'up' and next_state == 'up':
            up = i + 1
        elif state == 'up' and next_state == 'down':
            depth = min(data[up] - data[mid], data[down] - data[mid])
            if depth > result:
                result = depth
            down, mid, up = i, i, i
        elif state == 'up' and next_state == 'wait':
            depth = min(data[up] - data[mid], data[down] - data[mid])
            if depth > result:
                result = depth
            down, mid, up = i+1, i+1, i+1
        elif state == 'down' and next_state == 'up':
            mid = i
            up = i + 1
        elif state == 'down' and next_state == 'wait':
            down, mid, up = i, i, i
        elif state == 'wait' and next_state == 'up':
            down, mid, up = i, i, i
        elif state == 'wait' and next_state == 'down':
            down, mid, up = i, i, i
        elif state == 'wait' and next_state == 'wait':
            down, mid, up = i, i, i

        state = next_state
        i += 1
    return result


func([0, 1, 3, -2, 0, 1, 0, -3, 2, 3])  # 4

func([3, 1, 3, -3, 0, -3, 3, 3, 1, 1, 2, 2])  # 3

here's my solution, hope it helps. Very close to yours, but you could clean up the last if clauses and avoid repeating them:

from typing import List, Optional


def pit_depth(start, bottom, end):
    """The pit depth."""
    return min(start - bottom, end - bottom)


def get_state(curr: int, next: int) -> Optional[str]:
    if next < curr:
        return "down"
    elif next > curr:
        return "up"
    else:
        return None


def solution(A: List[int]) -> int:
    max_depth = -1
    curr_state = None
    if not A:
        return max_depth
    curr = A[0]
    top = curr
    bottom = None
    for next in A[1:]:
        next_state = get_state(curr, next)

        if (
            curr_state == "up"
            and next_state != "up"
            and top is not None
            and bottom is not None
        ):
            # we're at the end of a pit
            curr_depth = pit_depth(top, bottom, curr)
            max_depth = max(max_depth, curr_depth)
        if curr_state != "down" and next_state == "down":
            # we're at the top
            top = curr
        elif curr_state == "down" and next_state == "up":
            # we're at the bottom
            bottom = curr
        curr_state = next_state
        curr = next

    if curr_state == "up" and top is not None and bottom is not None:
        # pit at the end
        curr_depth = pit_depth(top, bottom, curr)
        max_depth = max(max_depth, curr_depth)
    return max_depth


assert solution([]) == -1
assert solution([0]) == -1
assert solution([5, 4, 1, -3]) == -1  # no pit, just monotone decreasing
assert solution([0, 2, 3]) == -1  # no pit, just monotone increasing
assert solution([-1, 0, 0, 1]) == -1  # not a pit because not strictly <>
assert solution([1, 2, 1]) == -1  # not a pit because it goes upwards
assert solution([1, 0, 1]) == 1  # simple pit
assert solution([0, 0, 1, 0, 1]) == 1  # simple pit with rubbish before
assert solution([1, 0, 1, 0, 0]) == 1  # simple pit with rubbish after
assert solution([2, 0, 3]) == 2  # asymmetric pit
assert solution([2, 0, -1, 5]) == 3  # long pit
assert solution([5, 3, 8, 0, 1]) == 2  # two pits sharing delimiter, min 1st
assert solution([5, 3, 8, 0, 9]) == 8  # two pits sharing delimiter, min last
assert solution([0, 1, 3, -2, 0, 1, 0, -3, 2, 3]) == 4