Lowest Reading in a Rotated Log With Repeats

HardBinary Search

Problem

A circular buffer of readings was written in non-decreasing order, but the dump starts at an arbitrary slot. Unlike the distinct case, the same reading can appear many times.

Return the smallest reading. Aim for logarithmic time when repeats allow it.

Example 1

Input:
log = [3, 3, 4, 1, 3]
Output:
1

Example 2

Input:
log = [4, 4, 4, 0, 2]
Output:
0

Example 3

Input:
log = [5, 5, 5]
Output:
5

Constraints

  • 1 ≤ log.length ≤ 5000
  • -5000 ≤ log[i] ≤ 5000
  • log is a non-decreasing array rotated between 0 and n - 1 times.

Hint

Show the first hint

Start from the distinct version: compare log[mid] with log[hi].

Walkthrough

How to approach it

01Clarify before coding

  • Return the value or the index? The value (with repeats, 'the index' would be ambiguous anyway).
  • Is a worst case of O(n) acceptable? It has to be: [x, x, ..., y, x, x] hides y from any O(log n) probing.
  • Can the array be not rotated? Yes.

02Brute force

Return min(log) with a scan.

Cost: O(n) always. The binary search below is O(log n) unless repeats force it to degrade.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.