MediumArrayBinary SearchStackMonotonic StackUpdated Sep 2026

1966. Binary Searchable Numbers in an Unsorted Array

Asked at Uber

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given an array nums of unique integers. The array may be sorted or not.

Imagine a search function that works like binary search but picks the pivot randomly each round. If the pivot equals the target, it returns true. If the pivot is smaller than the target, it throws away the pivot and everything to its left. If the pivot is bigger than the target, it throws away the pivot and everything to its right. It repeats until the array is empty, then returns false.

A value is binary searchable if this function is guaranteed to find it, no matter how the pivots are chosen. Return the count of such values in nums.

A value is guaranteed to be found exactly when it is strictly greater than every element on its left and strictly smaller than every element on its right. If either side breaks that rule, some pivot choice can throw the value away before it is ever picked.

Which values can never be thrown away?

nums-152012Only -1 is safe: nothing on its left, and 5 and 2 areboth bigger than it.nums5 > 2 breaks it-1520125 has a smaller value (2) on its right, so a pivot of2 would delete 5.
A value is safe only if everything on its left is smaller and everything on its right is bigger.

Constraints

  • ●1 <= nums.length <= 10^5
  • ●-10^5 <= nums[i] <= 10^5
  • ●All values in nums are unique.

Examples

Example 1
Inputnums = [7]
Output1
WhyThere is only one element, so it is always chosen as the pivot and always matches the target. It has no left or right neighbors, so both conditions hold.
Example 2
Inputnums = [-1,5,2]
Output1
WhyOnly -1 is safe. It is smaller than both 5 and 2, so it beats the right-side rule, and it has nothing on its left. The value 5 fails because 2 sits to its right: if 2 is picked first, 5 gets discarded. The value 2 fails because 5 sits to its left: if 5 is picked first, 2 gets discarded.
Example 3
Inputnums = [2,1,3,4]
Output0
WhyNo value passes both tests. The value 2 has 1 on its right, so it is not smaller than everything to its right. The value 3 has 2 and 1 on its left, so it is not greater than everything to its left. The value 4 has 2 and 1 on its left too. The value 1 has 2 on its left. So the count is 0.

Asked At

1 companies
CompanyDifficulty
UberMediumView all Uber questions →

How to Think About It

1

Brute force: for each index i, scan all elements to its left to find the max and all elements to its right to find the min. Check max < nums[i] < min. This is O(nA2) time and O(1) space.

2

Precompute prefix max and suffix min arrays in a single pass each. prefixMax[i] = max of nums[0..i], suffixMin[i] = min of nums[i..n-1]. Then a number is searchable if nums[i] > prefixMax[i-1] and nums[i] < suffixMin[i+1]. This is O(n) time and O(n) space.

3

A monotonic stack approach from the right works: maintain an increasing stack of potential minimums. As you iterate right to left, pop elements >= nums[i] (they cannot be suffix minima), then check if nums[i] is greater than the current left max. Still O(n) time.

4

The key insight is that a searchable number must simultaneously be a record-high from the left (greater than all left neighbors) and a record-low from the right (less than all right neighbors). These two conditions are independent and can be checked with prefix/suffix arrays.

5

Edge cases: the first element is searchable only if it is smaller than the minimum of the rest; the last element is searchable only if it is greater than the maximum of the rest. Single-element arrays return 1.

Optimal Approach

Step 1: If the array is empty, return 0. If it has one element, return 1.

Step 2: Build a prefixMax array where prefixMax[i] = max of nums[0..i]. This tracks the running maximum from the left.

Step 3: Build a suffixMin array where suffixMin[i] = min of nums[i..n-1]. This tracks the running minimum from the right.

Step 4: For each index i, check if nums[i] is strictly greater than all elements to its left (nums[i] > prefixMax[i-1] for i > 0) and strictly less than all elements to its right (nums[i] < suffixMin[i+1] for i < n-1).

Step 5: Count the indices that satisfy both conditions.

Step 6: Return the count.

Time: O(n) Space: O(n)

Prefix max and suffix min

nums-152012The input array we want to test.prefixMax-155012prefixMax[i] is the largest value seen from index 0 upto i.suffixMin-122012suffixMin[i] is the smallest value seen from index ito the end.safe if nums[i] > prefixMax[i-1]and nums[i] < suffixMin[i+1]i = 0: no left, -1 < 2 -> safei = 1: 5 > 2? no -> unsafei = 2: 2 > 5? no -> unsafe
Compare each value with the running max on its left and the running min on its right.
ComplexityTime O(n)Space O(n)We build one prefix-max array and one suffix-min array, then scan once, so every element is touched a constant number of times.

What Trips People Up in Real Interviews

1

Confusing "binary searchable" with being at the correct index for binary search. The property depends on values relative to ALL left and right elements, not just the immediate neighbors.

2

Using non-strict comparisons (>= or <=) instead of strict (>). Equal elements break binary search, so the conditions must be strictly greater on the left and strictly less on the right.

3

Only comparing each element to its immediate left and right neighbors. The definition requires being greater than EVERY element to the left and less than EVERY element to the right, which demands prefix max and suffix min.

4

Falling into the O(nA2) brute force trap. While it works, interviewers expect the O(n) prefix-max / suffix-min optimization after stating the brute force.

5

Forgetting that the leftmost and rightmost elements have no boundary on one side. The first element only needs nums[0] < suffixMin[1] and the last only needs nums[n-1] > prefixMax[n-2]. Handling these edge indices incorrectly leads to off-by-one errors.

6

Misunderstanding that the index of the element within the original unsorted array matters. Binary search operates on the sorted order of indices, and the element must satisfy the left/right property at its actual position.

Solution Code

O(n) time
def binarySearchableNumbers(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return 1

    prefix_max = [0] * n
    prefix_max[0] = nums[0]
    for i in range(1, n):
        prefix_max[i] = max(prefix_max[i - 1], nums[i])

    suffix_min = [0] * n
    suffix_min[n - 1] = nums[n - 1]
    for i in range(n - 2, -1, -1):
        suffix_min[i] = min(suffix_min[i + 1], nums[i])

    count = 0
    for i in range(n):
        left_ok = (i == 0) or (nums[i] > prefix_max[i - 1])
        right_ok = (i == n - 1) or (nums[i] < suffix_min[i + 1])
        if left_ok and right_ok:
            count += 1

    return count

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Binary Searchable Numbers in an Unsorted Array problem?

Given an unsorted array of integers nums, return the count of numbers that are binary searchable. A number is binary searchable if it is strictly greater than every element to its left and strictly smaller than every element to its right. In other words, if you ran a binary search targeting that value on the array, you would find it.

How do you solve Binary Searchable Numbers in an Unsorted Array?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Binary Searchable Numbers in an Unsorted Array?

Binary Searchable Numbers in an Unsorted Array is asked at Uber. It is a medium difficulty problem.

What are common mistakes on Binary Searchable Numbers in an Unsorted Array?
  • Confusing "binary searchable" with being at the correct index for binary search. The property depends on values relative to ALL left and right elements, not just the immediate neighbors.
  • Using non-strict comparisons (>= or <=) instead of strict (>). Equal elements break binary search, so the conditions must be strictly greater on the left and strictly less on the right.
  • Only comparing each element to its immediate left and right neighbors. The definition requires being greater than EVERY element to the left and less than EVERY element to the right, which demands prefix max and suffix min.
  • Falling into the `O(nA2)` brute force trap. While it works, interviewers expect the `O(n)` prefix-max / suffix-min optimization after stating the brute force.
  • Forgetting that the leftmost and rightmost elements have no boundary on one side. The first element only needs `nums[0] < suffixMin[1]` and the last only needs `nums[n-1] > prefixMax[n-2]`. Handling these edge indices incorrectly leads to off-by-one errors.
  • Misunderstanding that the index of the element within the original unsorted array matters. Binary search operates on the sorted order of indices, and the element must satisfy the left/right property at its actual position.