Find Binary Searchable Elements in Unsorted Array
Filed under Microsoft
Free read 1 of 3Confirm definition of binary searchable element: an element arr[i] such that max(arr[0...i]) <= arr[i] <= min(arr[i...n-1]).
The question
Given an unsorted array of integers, find all elements that would be successfully found using binary search if the array were processed appropriately. Specifically, identify elements where the left maximum and right minimum values coincide with the element itself.
Constraints
- Array length is between 1 and 10^5.
- Array elements are integers.
Examples
- Input
- arr = [2, 1, 3, 5, 4]
- Output
- [3]
- Why
- For 3, all elements to its left are smaller (max is 2 or 1) and all elements to its right are larger (min is 4). Thus it is a binary searchable element.
Approach
Confirm definition of binary searchable element: an element arr[i] such that max(arr[0...i]) <= arr[i] <= min(arr[i...n-1]).
For every element, scan all elements to its left to find the maximum and all elements to its right to find the minimum. Time complexity: O(N^2).
Precompute prefix maximum array from left to right and suffix minimum array from right to second. A number is valid if left_max[i] <= arr[i] <= right_min[i]. Time complexity: O(N), Space complexity: O(N).
Single-element array, duplicate elements, and already sorted arrays.
Solution
O(n) time, O(n) space
def findBinarySearchableElements(arr):
n = len(arr)
if n == 0: return []
left_max = [0] * n
right_min = [0] * n
curr_max = -float('inf')
for i in range(n):
curr_max = max(curr_max, arr[i])
left_max[i] = curr_max
curr_min = float('inf')
for i in range(n - 1, -1, -1):
curr_min = min(curr_min, arr[i])
right_min[i] = curr_min
result = []
for i in range(n):
if (i == 0 or arr[i] >= left_max[i-1]) and (i == n - 1 or arr[i] <= right_min[i+1]):
result.append(arr[i])
return result
Tips
- What they are testing: Test with strictly sorted arrays (all elements valid), reverse sorted arrays (no elements valid), and arrays with duplicate values.
- Common mistake: Using an O(N^2) nested loop approach instead of precalculating prefix maximums and suffix minimums.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.