The One-Way Street

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Meta

Problem

You're profiling a numeric column pulled from a metrics export, hunting for the longest stretch where the readings only ever move one way. Given arr, return the length of the longest contiguous run that stays entirely non-decreasing or entirely non-increasing.

The longest stretch that never turns around.

Example 1

Input:

arr = [8,1,2,2,5,3]

Output:

4

Example 2

Input:

arr = [5,3,3,1]

Output:

4

Worked solution and explanation

What this problem really is

Strip the costume and this is a single scan that keeps two counters running at once: how long the current stretch has gone without falling, and how long it has gone without rising. You cannot lean on comparing against the sorted array, because the answer is a contiguous window that can sit anywhere and depends entirely on order. The trap is collapsing the two directions into one, or resetting a counter the moment neighbors are equal. Do that and a flat run like [7, 7, 7] gets cut short, and a clean falling segment reads as if it changed direction.

Break down the requirements

Step 1: Extend the non-decreasing counter

Whenever the next value is greater than or equal to the previous one, the current non-decreasing stretch grows by one. The moment a value drops, reset that counter to 1, since the drop starts a fresh single-element window.

Step 2: Extend the non-increasing counter independently

In the very same step, if the next value is less than or equal to the previous one, the non-increasing stretch grows. Equality feeds BOTH counters at once: that is exactly why a flat run counts fully in either direction.

Step 3: Remember the best either counter reaches

After updating both counters at position i, take the larger of the two and fold it into a running best. One pass, and the answer is whatever height either counter ever reached.

The solution

Two-counter scan for the longest one-way run
def longest_monotonic_run(arr):
    if not arr:
        return 0
    best = 1
    inc = 1
    dec = 1
    for i in range(1, len(arr)):
        if arr[i] >= arr[i - 1]:
            inc += 1
        else:
            inc = 1
        if arr[i] <= arr[i - 1]:
            dec += 1
        else:
            dec = 1
        best = max(best, inc, dec)
    return best

Common follow-up questions