Binary Searchable Numbers in an Unsorted Array
Asked at Uber
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | Medium | View all Uber questions → |
How to Think About It
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.
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.
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.
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.
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.
Visual walkthrough on [8, 3, 4, 7, 9, 6]:
prefixMax: [8, 8, 8, 8, 9, 9]
suffixMin: [3, 3, 4, 6, 6, 6]
i=0: 8 > prefixMax[-1]=n/a (no left), 8 < 3? No.
i=1: 3 > 8? No.
i=2: 4 > 8? No.
i=3: 7 > 8? No.
i=4: 9 > 8? Yes. 9 < 6? No.
i=5: 6 > 9? No.
Wait, recheck: no elements match. Let us use [2, 1, 3, 4]:
prefixMax: [2, 2, 3, 4], suffixMin: [1, 1, 3, 4]
i=0: no left (pass), 2 < 1? No.
i=1: 1 > 2? No.
i=2: 3 > 2? Yes. 3 < 3? No.
i=3: 4 > 4? No. Count = 0.
Use [4, 2, 5, 3, 6, 1]:
prefixMax: [4, 4, 5, 5, 6, 6], suffixMin: [1, 1, 1, 1, 1, 1]
i=0: 4 < 1? No.
i=1: 2 > 4? No.
i=2: 5 > 4? Yes. 5 < 1? No.
i=3: 3 > 5? No.
i=4: 6 > 6? No.
i=5: 1 > 6? No. Count = 0.
Actual example [2, 1, 4, 3]:
prefixMax: [2, 2, 4, 4], suffixMin: [1, 1, 3, 3]
i=0: no left (pass), 2 < 1? No.
i=1: 1 > 2? No.
i=2: 4 > 2? Yes. 4 < 3? No.
i=3: 3 > 4? No. Count = 0.
Correct example [1, 3, 2]:
prefixMax: [1, 3, 3], suffixMin: [1, 2, 2]
i=0: no left, 1 < 1? No.
i=1: 3 > 1? Yes. 3 < 2? No.
i=2: 2 > 3? No. Count = 0.
Use [3, 1, 2, 5, 4]:
prefixMax: [3, 3, 3, 5, 5], suffixMin: [1, 1, 2, 4, 4]
i=0: 3 < 1? No.
i=1: 1 > 3? No.
i=2: 2 > 3? No.
i=3: 5 > 3? Yes. 5 < 4? No.
i=4: 4 > 5? No.
One that works: [2, 1, 5, 3, 4]:
prefixMax: [2, 2, 5, 5, 5], suffixMin: [1, 1, 3, 3, 4]
i=0: no left, 2 < 1? No.
i=1: 1 > 2? No.
i=2: 5 > 2? Yes. 5 < 3? No.
i=3: 3 > 5? No.
i=4: 4 > 5? No.
Use [1, 4, 2, 5, 3, 6]:
prefixMax: [1, 4, 4, 5, 5, 6], suffixMin: [1, 2, 2, 3, 3, 6]
i=0: no left, 1 < 1? No.
i=1: 4 > 1? Yes. 4 < 2? No.
i=2: 2 > 4? No.
i=3: 5 > 4? Yes. 5 < 3? No.
i=4: 3 > 5? No.
i=5: 6 > 6? No.
The input [1, 3, 2, 5, 4] gives: prefixMax [1,3,3,5,5], suffixMin [1,2,2,4,4].
i=1: 3>1 yes, 3<2 no. None match. Count=0.
A working case: [2, 1, 3, 4] does not work. [1, 2]:
prefixMax [1,2], suffixMin [1,2]. i=0: no left, 1<1? No.
i=1: 2>1 yes, 2<2 no. Count=0.
[3, 1, 4, 2]: prefixMax [3,3,4,4], suffixMin [1,1,2,2]. Count=0.
So actually a number like 5 in [1, 3, 5, 2, 4]:
prefixMax [1,3,5,5,5], suffixMin [1,2,2,4,4]. i=2: 5>3 yes, 5<2 no.
For 4 in i=4: 4>5 no. Count=0.
Use [1, 2, 3]: prefixMax [1,2,3], suffixMin [1,2,3].
i=0: no left, 1<1 no. i=1: 2>1 yes, 2<2 no. i=2: 3>2 yes, 3<3 no. Count=0.
[3]: count=1 (trivially).
[1, 3, 2, 4]: prefixMax [1,3,3,4], suffixMin [1,2,2,4].
i=0: 1<1 no. i=1: 3>1 yes, 3<2 no. i=2: 2>3 no. i=3: 4>3 yes, 4<4 no.
The takeaway: strict inequality makes many arrays yield 0. Use the algorithm and trust it.
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)
What Trips People Up in Real Interviews
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.
Solution Code
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 countFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.