Skip to main content
Talentd

Binary Searchable Numbers in an Unsorted Array - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary Search5 min readAsked at: Microsoft, Uber, Google
Practice this problem

Problem Statement

Consider a function that implements an algorithm similar to Binary Search. The function has two input parameters: sequence is a sequence of integers, and target is an integer value. The purpose of the function is to find if the target exists in the sequence.

The pseudocode of the function is as follows:

func(sequence, target)
  while sequence is not empty
    randomly choose an element from sequence as the pivot
    if pivot = target, return true
    else if pivot < target, remove pivot and all elements to its left from the sequence
    else, remove pivot and all elements to its right from the sequence
  end while
  return false

When the sequence is sorted, the function works correctly for all values. When the sequence is not sorted, the function does not work for all values, but may still work for some values.

Given an integer array nums, representing the sequence, that contains unique numbers and may or may not be sorted, return the number of values that are guaranteed to be found using the function, for every possible pivot selection.

 

Example 1:

Input: nums = [7]
Output: 1
Explanation: 
Searching for value 7 is guaranteed to be found.
Since the sequence has only one element, 7 will be chosen as the pivot. Because the pivot equals the target, the function will return true.

Example 2:

Input: nums = [-1,5,2]
Output: 1
Explanation: 
Searching for value -1 is guaranteed to be found.
If -1 was chosen as the pivot, the function would return true.
If 5 was chosen as the pivot, 5 and 2 would be removed. In the next loop, the sequence would have only -1 and the function would return true.
If 2 was chosen as the pivot, 2 would be removed. In the next loop, the sequence would have -1 and 5. No matter which number was chosen as the next pivot, the function would find -1 and return true.

Searching for value 5 is NOT guaranteed to be found.
If 2 was chosen as the pivot, -1, 5 and 2 would be removed. The sequence would be empty and the function would return false.

Searching for value 2 is NOT guaranteed to be found.
If 5 was chosen as the pivot, 5 and 2 would be removed. In the next loop, the sequence would have only -1 and the function would return false.

Because only -1 is guaranteed to be found, you should return 1.

 

Constraints:

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105
  • All the values of nums are unique.

 

Follow-up: If nums has duplicates, would you modify your algorithm? If so, how?

Approach Overview

Problem Overview: You receive an unsorted array and need to count how many numbers would still be found correctly if a standard binary search was executed on the array. A number is "binary searchable" only if every element on its left is smaller or equal and every element on its right is greater or equal. In other words, the element already sits exactly where it would appear in the sorted order relative to the rest of the array.

Approach 1: Brute Force Validation (O(n²) time, O(1) space)

Check every element nums[i] and verify two conditions: all elements to the left are <= nums[i] and all elements to the right are >= nums[i]. This requires two scans for each index. The approach directly mirrors the binary search correctness condition but repeatedly scans the array, leading to quadratic time complexity. Useful for understanding the rule that defines a valid binary searchable element.

Approach 2: Prefix Max + Suffix Min (O(n) time, O(n) space)

Precompute two helper arrays. The first array stores the maximum value seen so far from the left (prefixMax[i]). The second stores the minimum value from the right (suffixMin[i]). An element nums[i] is valid if prefixMax[i-1] <= nums[i] and nums[i] <= suffixMin[i+1]. This converts repeated scans into constant-time checks per index. The idea relies on tracking global constraints around each position rather than re-evaluating neighbors repeatedly. Time complexity becomes O(n) with O(n) extra memory.

This problem combines reasoning about order constraints in an array with the guarantees required for binary search. Binary search assumes the array is sorted. Here you identify elements that already satisfy that assumption locally relative to the rest of the array.

Recommended for interviews: The prefix-max and suffix-min technique is the expected solution. Interviewers want to see that you transform repeated range checks into precomputed state using linear scans. Showing the brute force first demonstrates you understand the condition that defines a valid element, while the optimized approach shows you can reduce the complexity from O(n²) to O(n).

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ValidationO(n²)O(1)Useful for understanding the binary-search condition or very small arrays
Prefix Max + Suffix MinO(n)O(n)General case; optimal approach used in interviews and production

Video Solution

Binary Searchable Numbers in an Unsorted Array • Shivam Gupta • 35 views views

Frequently Asked Questions

Is Binary Searchable Numbers in an Unsorted Array easy or hard?
The problem is typically rated Medium because the key condition is not obvious at first glance. Once you recognize that a valid element must be larger than everything on the left and smaller than everything on the right, the solution becomes a straightforward linear scan using prefix and suffix preprocessing.
Binary Searchable Numbers in an Unsorted Array Python/Java solution
Implement the prefix-max and suffix-min strategy. First compute prefixMax while iterating left to right. Then compute suffixMin while iterating right to left. Finally count indices where prefixMax[i-1] <= nums[i] <= suffixMin[i+1]. The same logic works in Python, Java, C++, and Go with O(n) time complexity.
How to solve Binary Searchable Numbers in an Unsorted Array in O(n)?
Compute a prefix maximum array while scanning from left to right and a suffix minimum array while scanning from right to left. For each index i, check whether prefixMax[i-1] <= nums[i] <= suffixMin[i+1]. If the condition holds, that element would remain correctly positioned for binary search. This reduces repeated range checks and achieves linear time.
What is the best approach for Binary Searchable Numbers in an Unsorted Array?
The prefix maximum and suffix minimum approach is the most efficient solution. You precompute the largest value seen to the left of each index and the smallest value seen to the right. An element is binary searchable if it is greater than or equal to the left maximum and less than or equal to the right minimum. This runs in O(n) time with O(n) extra space.
Is Binary Searchable Numbers in an Unsorted Array asked at Google/Amazon/Meta?
Problems based on prefix maximum, suffix minimum, and order constraints frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem test understanding of array preprocessing and how binary search relies on global ordering guarantees.
What data structure is used in Binary Searchable Numbers in an Unsorted Array?
The solution primarily uses arrays for prefix maximum and suffix minimum preprocessing. No advanced data structures are required. The logic relies on scanning the array and maintaining running minimum and maximum values.
What is the time complexity of Binary Searchable Numbers in an Unsorted Array?
The optimal solution runs in O(n) time because the array is scanned a constant number of times to build prefix and suffix helper arrays. A naive brute-force approach checks all elements on both sides of every index, resulting in O(n²) time complexity. Space complexity for the optimal solution is O(n).

Ready to solve this problem?

Practice Binary Searchable Numbers in an Unsorted Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays