โ† Microsoft questions
CodingReported in a candidate post, Dec 2020

Find Binary Searchable Elements in Unsorted Array

Filed under Microsoft

Free read 1 of 3

Confirm 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

  1. Confirm definition of binary searchable element: an element arr[i] such that max(arr[0...i]) <= arr[i] <= min(arr[i...n-1]).

Solution

O(n) time, O(n) space

Python
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.