Show problems as
Classic problem #154HardArrayBinary Search

Find Minimum in Rotated Sorted Array II

Real-world version: Lowest Reading On A Turned Drum
Tracked in this browser only
Read Find Minimum in Rotated Sorted Array II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstCounting Occurrences · Binary Search, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def lowest_reading(drum: list[int]) -> int:
Java
public int lowestReading(int[] drum)

More on the same topics