Show problems as
Classic problem #1966MediumArrayBinary SearchStackMonotonic Stack

Binary Searchable Numbers in an Unsorted Array

Real-world version: Reliable Lookups On An Unordered Shelf
Tracked in this browser only
Read Binary Searchable Numbers in an Unsorted Array on LeetCode(opens in a new tab)

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

A stockroom shelf holds parts left to right, and codes[i] is the part code in position i. All part codes on the shelf are different. The shelf is not in code order, but the stockroom's lookup routine assumes it is.

Looking up a code v works on a range of positions lo through hi, starting with the whole shelf, lo = 0 and hi = n - 1:

  1. If lo > hi the range is empty and the lookup fails.
  2. Otherwise the routine picks a split position mid with lo <= mid <= hi. Which position it picks is up to the routine and you may not assume anything about the choice.
  3. If codes[mid] == v the lookup succeeds.
  4. If codes[mid] < v the routine repeats from step 1 on the range mid + 1 through hi.
  5. If codes[mid] > v the routine repeats from step 1 on the range lo through mid - 1.

Call position i reliable when looking up codes[i] succeeds for every possible sequence of split positions the routine could pick. A single unlucky sequence that fails is enough to make the position unreliable.

Return how many positions on the shelf are reliable.

Examples

Example 1

Input
codes = [12, 30, 20, 45, 70]
Output
3

Looking up the 30 at position 1 can start by splitting at position 2, whose code 20 is below 30, which sends the search to positions 3 through 4 and leaves position 1 out of range for good. Looking up the 20 at position 2 can start by splitting at position 1, whose code 30 is above 20, which sends the search to positions 0 through 0. Positions 0, 3 and 4 come out successful however the splits are chosen, so the count is 3.

Example 2

Input
codes = [3, 2, 1, 4]
Output
1

Looking up the 3 at position 0 can split at position 2, whose code 1 is below 3, moving the search to positions 3 through 3. Looking up the 2 at position 1 can split at position 0, whose code 3 is above 2, moving the search to an empty range. Looking up the 1 at position 2 fails after the same first split. Position 3 succeeds whatever the routine picks, so the count is 1.

Example 3

Input
codes = [8, 6, 4, 2]
Output
0

Looking up 8 can split at position 3, whose code 2 is below 8, moving the search past the end of the shelf. Looking up 6, 4 or 2 can each split at position 0, whose code 8 is above all of them, moving the search before the start of the shelf. No position is reliable.

Constraints

  • 1 <= codes.length <= 10^5
  • -10^5 <= codes[i] <= 10^5
  • All part codes in codes are different from one another.

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 reliable_lookups(codes: list[int]) -> int:
Java
public int reliableLookups(int[] codes)

More on the same topics