NeetCode #294LC-1966MediumBinary Search
← Back to All Problems#294 · #1966 · Binary Searchable Numbers in an Unsorted Array(未排序数组中的可二分查找数)
📌 Problem Statement & Constraints
A binary searchable number in an array is one that would be found by the standard binary search procedure regardless of the search target. Given an array
nums of distinct integers, return the number of binary searchable numbers. Constraints: 1 <= nums.length <= 10^5, 0 <= nums[i] <= 10^9, all elements are distinct.💡 Core Algorithmic Approaches
- An element is binary searchable exactly when it is greater than every element to its left and less than every element to its right.
- Why: the binary search must not discard the half containing the element before reaching it, which requires all elements to the left to be smaller and all to the right to be larger.
- So compute the prefix maximum and the suffix minimum, then count positions where
nums[i]equals both. - This is O(n) time and O(n) space (O(1) extra if the suffix minima are computed on the fly in a second pass).
💻 Benchmark Python3 Implementation
class Solution:
def binarySearchableNumbers(self, nums: List[int]) -> int:
n = len(nums)
pref_max = [0] * n
cur = float("-inf")
for i in range(n):
cur = max(cur, nums[i])
pref_max[i] = cur # max of nums[0..i]
suff_min = [float("inf")] * n
cur = float("inf")
for i in range(n - 1, -1, -1):
cur = min(cur, nums[i])
suff_min[i] = cur # min of nums[i..n-1]
res = 0
for i in range(n):
if nums[i] == pref_max[i] and nums[i] == suff_min[i]:
res += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): two passes for the prefix maxima and suffix minima, plus one counting pass.
💾 Space Complexity
O(n) for the two arrays.
⚠️ Interview Pitfalls & Follow-ups
- Using
nums[i] > pref_max[i-1]without the boundary: at index 0 there is no left neighbour, andpref_max[0] == nums[0]handles it naturally. - Only checking one side: both the prefix maximum and the suffix minimum conditions are required.
- Simulating the binary search for every possible target: O(n log n) or worse.
- Assuming the array is sorted: it is not; the condition is about the extremes on each side.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.