Binary Searchable Numbers in an Unsorted Array
Binary Searchable Numbers in an Unsorted Array is a medium arrays & hashing problem solved with the right to left traversal pattern.
The best approach, optimal (prefix maximum + suffix minimum), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (check both sides of every element) up.
Problem
Picture a search for a value target in a sequence that runs like this: while the sequence is not empty, pick any element as the pivot. If the pivot equals target, report success. If the pivot is smaller than target, delete the pivot and everything to its left; if it is larger, delete the pivot and everything to its right. If the sequence runs out, report failure.
On a sorted sequence this always finds the target, but on an unsorted one an unlucky pivot can discard it. You get an array nums of distinct integers. Return how many of its values are guaranteed to be found, no matter which pivots are chosen, when searched for in nums.
Examples
Example 1
- Input
nums = [2,1,3,6,4,8]- Output
2- Why
- Only 3 and 8 have every value to their left smaller and every value to their right larger.
Example 2
- Input
nums = [-4,0,9,12]- Output
4- Why
- The array is sorted, so the search can never throw any target away.
Example 3
- Input
nums = [5]- Output
1- Why
- The only pivot available is the target itself.
Constraints
1 <= nums.length <= 10^5-10^5 <= nums[i] <= 10^5- All values in
numsare distinct.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (check both sides of every element) | O(n²) | O(1) |
| Optimal (prefix maximum + suffix minimum) | O(n) | O(n) |
1Brute force (check both sides of every element)
O(n²)Each of the n positions scans the rest of the array.O(1)Only a counter and loop indices.A value survives every possible pivot choice if and only if all values to its left are smaller and all values to its right are larger. Check that directly for each position.
- For each index i, scan j < i and fail if nums[j] > nums[i].
- Scan j > i and fail if nums[j] < nums[i].
- Count the indices that pass both scans.
class Solution {
public int binarySearchableNumbers(int[] nums) {
int n = nums.length, count = 0;
for (int i = 0; i < n; i++) {
boolean ok = true;
for (int j = 0; j < n && ok; j++) {
if (j < i && nums[j] > nums[i]) ok = false;
if (j > i && nums[j] < nums[i]) ok = false;
}
if (ok) count++;
}
return count;
}
}class Solution:
def binarySearchableNumbers(self, nums: List[int]) -> int:
n = len(nums)
count = 0
for i in range(n):
ok = all(nums[j] < nums[i] for j in range(i)) and \
all(nums[j] > nums[i] for j in range(i + 1, n))
if ok:
count += 1
return countclass Solution {
public:
int binarySearchableNumbers(vector<int>& nums) {
int n = nums.size(), count = 0;
for (int i = 0; i < n; i++) {
bool ok = true;
for (int j = 0; j < n && ok; j++) {
if (j < i && nums[j] > nums[i]) ok = false;
if (j > i && nums[j] < nums[i]) ok = false;
}
if (ok) count++;
}
return count;
}
};function binarySearchableNumbers(nums) {
const n = nums.length;
let count = 0;
for (let i = 0; i < n; i++) {
let ok = true;
for (let j = 0; j < n && ok; j++) {
if (j < i && nums[j] > nums[i]) ok = false;
if (j > i && nums[j] < nums[i]) ok = false;
}
if (ok) count++;
}
return count;
}2Optimal (prefix maximum + suffix minimum)
O(n)Two linear passes.O(n)The suffix-minimum array.The condition 'everything left is smaller' is the same as 'the maximum of the prefix before i is smaller than nums[i]', and 'everything right is larger' is 'the minimum of the suffix after i is larger'. Fill a suffix-minimum array from right to left, then sweep left to right carrying the running prefix maximum.
- sufMin[n] = +infinity; for i from n - 1 down to 0, sufMin[i] = min(nums[i], sufMin[i + 1]).
- Sweep i from 0 with leftMax = -infinity.
- If leftMax < nums[i] and nums[i] < sufMin[i + 1], count it.
- Update leftMax = max(leftMax, nums[i]).
class Solution {
public int binarySearchableNumbers(int[] nums) {
int n = nums.length;
int[] sufMin = new int[n + 1];
sufMin[n] = Integer.MAX_VALUE;
for (int i = n - 1; i >= 0; i--) {
sufMin[i] = Math.min(nums[i], sufMin[i + 1]);
}
int leftMax = Integer.MIN_VALUE, count = 0;
for (int i = 0; i < n; i++) {
if (leftMax < nums[i] && nums[i] < sufMin[i + 1]) count++;
leftMax = Math.max(leftMax, nums[i]);
}
return count;
}
}class Solution:
def binarySearchableNumbers(self, nums: List[int]) -> int:
n = len(nums)
suf_min = [inf] * (n + 1)
for i in range(n - 1, -1, -1):
suf_min[i] = min(nums[i], suf_min[i + 1])
left_max = -inf
count = 0
for i, x in enumerate(nums):
if left_max < x < suf_min[i + 1]:
count += 1
left_max = max(left_max, x)
return countclass Solution {
public:
int binarySearchableNumbers(vector<int>& nums) {
int n = nums.size();
vector<int> sufMin(n + 1, INT_MAX);
for (int i = n - 1; i >= 0; i--) {
sufMin[i] = min(nums[i], sufMin[i + 1]);
}
int leftMax = INT_MIN, count = 0;
for (int i = 0; i < n; i++) {
if (leftMax < nums[i] && nums[i] < sufMin[i + 1]) count++;
leftMax = max(leftMax, nums[i]);
}
return count;
}
};function binarySearchableNumbers(nums) {
const n = nums.length;
const sufMin = new Array(n + 1).fill(Infinity);
for (let i = n - 1; i >= 0; i--) {
sufMin[i] = Math.min(nums[i], sufMin[i + 1]);
}
let leftMax = -Infinity, count = 0;
for (let i = 0; i < n; i++) {
if (leftMax < nums[i] && nums[i] < sufMin[i + 1]) count++;
leftMax = Math.max(leftMax, nums[i]);
}
return count;
}Edge cases to test
- A single element: always found
- A sorted array: every element is found
- A reverse-sorted array of length 2 or more: no element is safe
- The global maximum at the end and the global minimum at the start are always safe
Hints
Hint 1
When can a pivot throw the target away? If a pivot to the left of the target is larger than it, the search discards the left side, target included. The mirror case happens on the right.
Hint 2
So a value is guaranteed to be found exactly when everything before it is smaller and everything after it is larger.
Hint 3
Precompute the maximum of every prefix and the minimum of every suffix, then test each position in O(1).
FAQ
What is the best time complexity for Binary Searchable Numbers in an Unsorted Array?
Optimal (prefix maximum + suffix minimum) runs in O(n) time and O(n) extra space. Two linear passes.
Which pattern does Binary Searchable Numbers in an Unsorted Array use?
It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Next Permutation.
Is there a brute force solution for Binary Searchable Numbers in an Unsorted Array?
Yes. Brute force (check both sides of every element) takes O(n²) time and O(1) space. A value survives every possible pivot choice if and only if all values to its left are smaller and all values to its right are larger.
Which edge cases should I test for Binary Searchable Numbers in an Unsorted Array?
A single element: always found; A sorted array: every element is found; A reverse-sorted array of length 2 or more: no element is safe; The global maximum at the end and the global minimum at the start are always safe.