Binary Searchable Numbers in an Unsorted Array

Problem Description

Ah, the classic dilemma of finding “binary searchable numbers” in an unsorted array. It’s like trying to find a needle in a haystack, but the haystack is also moving, and the needle is hiding under a pile of other needles. The problem is simple yet perplexing: given an unsorted array of integers, we need to identify how many numbers are “binary searchable.”

A number is considered binary searchable if it is greater than all the numbers to its left and less than all the numbers to its right. Imagine you’re at a party, and you want to find the coolest person in the room. You need to ensure that everyone to your left is less cool than you, and everyone to your right is cooler. If you can find such a person, congratulations! You’ve found a binary searchable number!

Solution Links

Before we dive into the code, here are some handy buttons for you to explore solutions in other languages:

C++ Solution |
Java Solution

Code Solution


class Solution:
    def binarySearchableNumbers(self, nums: list[int]) -> int:
        n = len(nums)
        # prefixMaxs[i] := max(nums[0..i))
        prefixMaxs = [0] * n
        # suffixMins[i] := min(nums[i + 1..n))
        suffixMins = [0] * n

        # Fill in `prefixMaxs`.
        prefixMaxs[0] = -math.inf
        for i in range(1, n):
            prefixMaxs[i] = max(prefixMaxs[i - 1], nums[i - 1])

        # Fill in `suffixMins`.
        suffixMins[n - 1] = math.inf
        for i in range(n - 2, -1, -1):
            suffixMins[i] = min(suffixMins[i + 1], nums[i + 1])

        return sum(prefixMaxs[i] < nums[i] < suffixMins[i] for i in range(n))

Approach Explanation

The approach taken in this solution is quite elegant. We create two auxiliary arrays: prefixMaxs and suffixMins.

Prefix Maximums: For each index i, prefixMaxs[i] holds the maximum value from the start of the array up to i-1. This helps us determine if the current number is greater than all numbers to its left.
Suffix Minimums: Conversely, suffixMins[i] holds the minimum value from i+1 to the end of the array. This tells us if the current number is less than all numbers to its right.

Finally, we iterate through the array and count how many numbers satisfy the condition of being greater than the prefix maximum and less than the suffix minimum.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array. We traverse the array a couple of times, but it’s still linear.
Space Complexity: O(n) due to the additional space used for the prefixMaxs and suffixMins arrays.

Real-World Example

Imagine you’re at a concert, and you want to find the best spot to enjoy the music. You want to be in a position where everyone behind you is shorter (prefix max) and everyone in front of you is taller (suffix min). If you find such a spot, you can enjoy the concert without any obstructions. This is essentially what the binary searchable number is trying to achieve in the array!