0456HardArrayBinary Search

Lowest Reading On A Turned Drum

Tracked in this browser only

Trains the technique from

LeetCode 154Find Minimum in Rotated Sorted Array II

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A chart recorder writes its calibration readings around the rim of a drum, one reading per slot, in non-decreasing order all the way round. Repeated readings are ordinary: a stretch of slots may all carry the same figure.

Before the drum was read off, it was turned by somewhere between 1 and n slots, n being the number of slots. The array drum holds the readings as they were then read off, starting from the slot at the index mark and going once round. So drum is the non-decreasing sequence cut at one point, with the tail moved in front of the head.

Return the lowest reading on the drum. Aim to do it without reading every slot: your work should scale with the logarithm of n when the drum holds few repeats.

Examples

Example 1

Input: drum = [78, 78, 12, 45, 45, 61]
Output: 12

Read from slot 2 onwards the drum gives 12, 45, 45, 61, 78, 78, which is the non-decreasing round, so the lowest figure on it is 12.

Example 2

Input: drum = [-9, 4, 4, 4, 4]
Output: -9

The readings rise from -9 through four slots reading 4, and -9 is the lowest of them.

Example 3

Input: drum = [206, 206, 206, 206]
Output: 206

Every slot carries 206, so that figure is both the highest and the lowest on the drum.

Constraints

n == drum.length
1 <= n <= 5000
-5000 <= drum[i] <= 5000
drum is a non-decreasing sequence turned by between 1 and n slots.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def lowest_reading(drum: list[int]) -> int:

Java

public int lowestReading(int[] drum)

The intended approach

Time O(log n) when repeats are few, degrading to O(n) when nearly every slot repeats.Space O(1).

Keep a live range that is known to contain the cut and weigh its middle slot against the slot at its far end. A middle above the far end puts the cut strictly beyond the middle; a middle below it lets the far end be discarded while the middle is kept. When the two readings are equal neither side can be ruled out, so the far slot alone is dropped, which is safe because an equal slot elsewhere in the range still holds whatever it carried. The range closes on the slot holding the lowest reading.

Pythonentry point: lowest_reading

def lowest_reading(drum):
    # Compare the middle slot against the slot at the far end of the live range.
    # A middle above the far end puts the wrap strictly to its right; a middle
    # below it means the far end can be dropped; equal readings say nothing
    # about which side holds the wrap, so give up one slot from the far end.
    # O(log n) on a drum with few repeats, O(n) worst case, O(1) extra space.
    lo = 0
    hi = len(drum) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if drum[mid] > drum[hi]:
            lo = mid + 1
        elif drum[mid] < drum[hi]:
            hi = mid
        else:
            hi -= 1
    return drum[lo]

The obvious version

Walk the slots in order and stop at the first place a reading drops below the one before it, which is the cut; if no drop turns up the drum was read off from its lowest slot. O(n), so this is not asymptotically slower than the reference's worst case - it is here as an independent check, not as a slower baseline.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_lowest_reading(drum):
    wrap = 0
    for i in range(1, len(drum)):
        if drum[i - 1] > drum[i]:
            wrap = i
            break
    return drum[wrap]

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in