LeetCode 1966 - Binary Searchable Numbers in an Unsorted Array

LeetCode Problem 1966

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Stack, Monotonic Stack

Solution

Problem Understanding

This problem asks us to identify how many numbers in an unsorted array are still guaranteed to be found by a randomized binary-search-like process.

The array nums contains unique integers. The search procedure repeatedly chooses a random pivot element from the current remaining sequence. Depending on whether the pivot is smaller or larger than the target, part of the sequence is discarded. Unlike standard binary search, the sequence is not necessarily sorted, so the elimination process can accidentally remove the target even when it exists.

We must determine which values are "binary searchable". A value is binary searchable if, regardless of how pivots are chosen during the process, the algorithm is guaranteed to eventually find it.

The important phrase is "for every possible pivot selection". We are not checking whether the value can sometimes be found. We are checking whether it is impossible for the randomized process to eliminate it incorrectly.

The input size can be as large as 10^5, which immediately tells us that any quadratic or cubic simulation will be too slow. We need an algorithm that runs in linear or near-linear time.

The array contains unique values, which simplifies comparisons because we never have to worry about equality between different indices. The follow-up question asks about duplicates separately.

Several edge cases are important:

• A single-element array always has exactly one searchable number.
• A completely sorted array makes every number searchable.
• A completely reversed array usually leaves very few searchable numbers.
• Numbers near the middle may fail if a smaller number exists to the right or a larger number exists to the left.
• Since values are unique, strict comparisons are sufficient.

Approaches

Brute Force Approach

A brute force solution would examine every number in the array and determine whether the randomized process can ever fail for that target.

For a target nums[i], we would need to simulate all possible pivot choices recursively. At every step, the pivot can be any remaining element. If there exists even one sequence of pivot choices that removes the target incorrectly, then the number is not searchable.

This approach is correct because it directly follows the problem definition. However, it is computationally infeasible. The number of pivot-selection sequences grows exponentially with the array size.

Even a simplified brute force approach that checks all subarrays or repeatedly simulates elimination would still be far too slow for n = 10^5.

Key Insight

A number nums[i] is guaranteed to be found if and only if:

• Every element to its left is smaller than it.
• Every element to its right is larger than it.

Why is this true?

Suppose there exists a larger number on the left side. If that larger number is chosen as a pivot while searching for nums[i], the algorithm will remove the pivot and everything to its right, which includes the target. The target is lost forever.

Similarly, suppose there exists a smaller number on the right side. If that smaller number becomes the pivot, the algorithm removes the pivot and everything to its left, again eliminating the target.

Therefore:

• nums[i] must be greater than all elements before it.
• nums[i] must be smaller than all elements after it.

This transforms the problem into a prefix/suffix comparison problem.

We can precompute:

• prefix_max[i] = maximum value from index 0 to i-1
• suffix_min[i] = minimum value from index i+1 to n-1

Then nums[i] is searchable if:

prefix_max[i] < nums[i] < suffix_min[i]

We can compute this in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Simulates all possible pivot selections
Optimal	O(n)	O(n)	Uses prefix maximums and suffix minimums

Algorithm Walkthrough

1. Create an array left_max where left_max[i] stores the maximum value appearing before index i.

This helps determine whether any larger value exists on the left side of nums[i]. 2. Traverse the array from left to right.

Maintain a running maximum called current_max.

For each index:

• Store current_max into left_max[i]
• Update current_max = max(current_max, nums[i])

3. Create an array right_min where right_min[i] stores the minimum value appearing after index i.

This helps determine whether any smaller value exists on the right side. 4. Traverse the array from right to left.

Maintain a running minimum called current_min.

For each index:

• Store current_min into right_min[i]
• Update current_min = min(current_min, nums[i])

5. Traverse the array one final time.

For each index i, check whether:

left_max[i] < nums[i] < right_min[i]

If true, increment the answer. 6. Return the final count.

Why it works

A target survives every possible pivot choice only if no incorrect pivot can eliminate it.

A larger value on the left can remove the target when chosen as pivot. A smaller value on the right can also remove the target. Therefore, the target is safe exactly when all left values are smaller and all right values are larger.

The prefix maximum captures whether a larger left element exists, and the suffix minimum captures whether a smaller right element exists. Together, they perfectly characterize searchable numbers.

Python Solution

from typing import List

class Solution:
    def binarySearchableNumbers(self, nums: List[int]) -> int:
        n = len(nums)

        left_max = [float("-inf")] * n
        current_max = float("-inf")

        for i in range(n):
            left_max[i] = current_max
            current_max = max(current_max, nums[i])

        right_min = [float("inf")] * n
        current_min = float("inf")

        for i in range(n - 1, -1, -1):
            right_min[i] = current_min
            current_min = min(current_min, nums[i])

        searchable_count = 0

        for i in range(n):
            if left_max[i] < nums[i] < right_min[i]:
                searchable_count += 1

        return searchable_count

The implementation follows the algorithm directly.

The first loop builds the left_max array. For each position, we store the largest value seen before the current index. Initially, there are no elements on the left, so negative infinity is used.

The second loop builds the right_min array. For each position, we store the smallest value seen after the current index. Positive infinity is used for the last position because no elements exist to its right.

The final loop checks whether the current value is larger than everything to its left and smaller than everything to its right. If both conditions hold, the number is guaranteed to be searchable.

Go Solution

func binarySearchableNumbers(nums []int) int {
	n := len(nums)

	leftMax := make([]int, n)
	currentMax := -(1 << 60)

	for i := 0; i < n; i++ {
		leftMax[i] = currentMax

		if nums[i] > currentMax {
			currentMax = nums[i]
		}
	}

	rightMin := make([]int, n)
	currentMin := 1 << 60

	for i := n - 1; i >= 0; i-- {
		rightMin[i] = currentMin

		if nums[i] < currentMin {
			currentMin = nums[i]
		}
	}

	answer := 0

	for i := 0; i < n; i++ {
		if leftMax[i] < nums[i] && nums[i] < rightMin[i] {
			answer++
		}
	}

	return answer
}

The Go implementation mirrors the Python solution closely.

Since Go does not provide built-in infinity values for integers, large sentinel values are used instead. The constraints guarantee values remain within [-10^5, 10^5], so using ±(1 << 60) is completely safe.

Slices are used for the prefix and suffix arrays, and the algorithm still runs in linear time.

Worked Examples

Example 1

Input:

nums = [7]

Building left_max

Index	nums[i]	left_max[i]	current_max after update
0	7	-inf	7

Building right_min

Index	nums[i]	right_min[i]	current_min after update
0	7	inf	7

Final Check

Index	Condition
0	-inf < 7 < inf, true

Answer:

1

Example 2

Input:

nums = [-1, 5, 2]

Building left_max

Index	nums[i]	left_max[i]
0	-1	-inf
1	5	-1
2	2	5

Building right_min

Index	nums[i]	right_min[i]
2	2	inf
1	5	2
0	-1	2

Final Check

Index	Condition	Searchable
0	-inf < -1 < 2	Yes
1	-1 < 5 < 2	No
2	5 < 2 < inf	No

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Three linear passes through the array
Space	O(n)	Two auxiliary arrays are stored

The algorithm performs constant work per element while constructing the prefix maximum and suffix minimum arrays. Since each pass is linear, the overall time complexity is O(n).

The additional space comes from storing the two helper arrays. Each has size n, so the total auxiliary space complexity is O(n).

Test Cases

sol = Solution()

assert sol.binarySearchableNumbers([7]) == 1
# Single element array

assert sol.binarySearchableNumbers([-1, 5, 2]) == 1
# Example from problem statement

assert sol.binarySearchableNumbers([1, 2, 3, 4, 5]) == 5
# Fully sorted array, every number searchable

assert sol.binarySearchableNumbers([5, 4, 3, 2, 1]) == 0
# Completely reversed array

assert sol.binarySearchableNumbers([1, 3, 2, 4, 5]) == 3
# Middle inversion removes some searchable values

assert sol.binarySearchableNumbers([2, 1, 3, 4]) == 2
# Prefix disorder affects early elements

assert sol.binarySearchableNumbers([1, 2, 5, 3, 4]) == 2
# Larger value before smaller suffix values

assert sol.binarySearchableNumbers([-5, -3, -1, 0, 2]) == 5
# Sorted array with negative numbers

assert sol.binarySearchableNumbers([10, 20, 5, 30, 40]) == 2
# Internal small element breaks guarantees

assert sol.binarySearchableNumbers([1]) == 1
# Minimum boundary size

assert sol.binarySearchableNumbers(list(range(1000))) == 1000
# Large sorted array stress test

Test	Why
[7]	Validates single-element behavior
[-1,5,2]	Verifies provided example
[1,2,3,4,5]	Every element should succeed in sorted order
[5,4,3,2,1]	No element survives all pivot choices
[1,3,2,4,5]	Tests local inversion
[2,1,3,4]	Tests left-side larger element
[1,2,5,3,4]	Tests right-side smaller element
[-5,-3,-1,0,2]	Confirms negative values work
[10,20,5,30,40]	Tests mixed ordering
[1]	Smallest valid input
range(1000)	Large input performance check

Edge Cases

A single-element array is an important edge case because the algorithm must correctly treat the only element as searchable. There are no left or right elements that could eliminate it. The implementation handles this naturally because the comparisons become -inf < value < inf.

A completely reversed array can easily expose incorrect logic. In such arrays, almost every pivot choice can eliminate targets incorrectly. The implementation correctly identifies that no element satisfies both prefix and suffix conditions.

Arrays containing negative numbers are another common source of mistakes, especially when sentinel values are used. The implementation avoids issues by using positive and negative infinity in Python and extremely large sentinel values in Go.

Another subtle edge case occurs when an element is larger than all previous elements but still has a smaller value somewhere to its right. A naive implementation that only checks prefix conditions would incorrectly count it as searchable. The suffix minimum array prevents this mistake.