Binary Searchable Numbers in an Unsorted Array

Medium

Asked by:

8 views

Topics:

Arrays

You are given an unsorted array of integers, nums.

A number x is binary searchable if, after sorting the subarray of nums that contains only x and its surrounding elements, the position of x in the sorted subarray is the same as its position in the original array nums.

More formally, a number nums[i] is binary searchable if:

Let subarray = sorted([nums[j] for j in range(max(0, i - k), min(len(nums), i + k + 1))]) for some k >= 0.
Then, subarray.index(nums[i]) == i - max(0, i - k).

Return the number of binary searchable elements in nums.

Example 1:

Input: nums = [1,5,4,3,2]
Output: 0
Explanation: No element is binary searchable.

Example 2:

Input: nums = [1,4,2,3]
Output: 1
Explanation: Only 4 is binary searchable:
- Consider the subarray containing 4 and its surrounding elements: [1,4,2].
- If we sort it: [1,2,4].
- The index of 4 in both arrays is 1.

Example 3:

Input: nums = [1,2,3,4,5]
Output: 5
Explanation: Every element is binary searchable.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values in the input array? Can I assume they fit within a standard integer type?
Can the input array be empty or null?
By "binary searchable," do you mean that if I were to search for the number using binary search on the entire unsorted array, it would correctly find the element's index if the array were sorted? (I.e., arr[i] == sorted(arr)[i])?
If there are multiple numbers that are "binary searchable", should I return all of them, or just the count?
Can there be duplicate values in the array, and if so, how should they be handled regarding whether they're considered binary searchable?

Brute Force Solution

Approach

To find numbers that could be found using a perfect guessing game strategy, we'll just look at each number in the collection, one at a time. For each number, we'll check if it satisfies the conditions to be found this way, and keep a count of those that do.

Here's how the algorithm would work step-by-step:

Pick a number from the collection.
Imagine that you are trying to guess that number.
Check if all the numbers to the left of it are smaller or equal to it.
Also check if all the numbers to the right of it are bigger or equal to it.
If both of these conditions are true, then that number could be found using the perfect guessing game strategy. Mark it as 'searchable'.
Repeat this process for every number in the collection.
Finally, count how many numbers were marked as 'searchable'. That's our answer.

Code Implementation

def find_searchable_numbers(number_collection):
    searchable_number_count = 0

    for current_index in range(len(number_collection)):
        is_searchable = True
        current_number = number_collection[current_index]

        # Check if all numbers to the left are smaller or equal
        for left_index in range(current_index):
            if number_collection[left_index] > current_number:
                is_searchable = False
                break

        if not is_searchable:
            continue

        # Check if all numbers to the right are bigger or equal
        for right_index in range(current_index + 1, len(number_collection)):
            if number_collection[right_index] < current_number:
                is_searchable = False
                break

        if is_searchable:
            # Increment counter if it meets the criteria
            searchable_number_count += 1

    return searchable_number_count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the input array. For each element, it checks all elements to its left and all elements to its right. This requires, in the worst case, iterating through all n elements again for each of the n elements in the original array. Thus, the total number of operations approximates n * n, which simplifies to O(n²).

Space Complexity

O(1) – The provided plain English explanation outlines an algorithm that iterates through the input collection of N numbers and performs comparisons. It does not describe the creation of any auxiliary data structures like lists, hash maps, or sets to store intermediate results. The algorithm only needs to keep track of a few variables (e.g., current number, searchable count) during the process. Therefore, the space required remains constant irrespective of the input size N, resulting in O(1) space complexity.

Optimal Solution

Approach

The key is to realize a number is 'binary searchable' if and only if all numbers to its left are smaller, and all numbers to its right are larger. We can efficiently determine these conditions by pre-computing running maximums from the left and running minimums from the right, then checking each number.

Here's how the algorithm would work step-by-step:

First, create a list of the largest number we've seen so far as we move from left to right through the original list. This way, for each spot, we know the biggest number to its left.
Next, create another list of the smallest number we've seen as we move from right to left through the original list. Now, for each spot, we know the smallest number to its right.
Now, go through the original list and check each number. A number is 'binary searchable' if it's greater than or equal to the largest number to its left (from our first list), AND it's less than or equal to the smallest number to its right (from our second list).
Count how many numbers meet this requirement. That's your answer.

Code Implementation

def find_binary_searchable_numbers(number_list):
    list_length = len(number_list)
    if list_length == 0:
        return 0

    left_running_maximums = [0] * list_length
    right_running_minimums = [0] * list_length

    # Need maximum from the left to compare
    left_running_maximums[0] = number_list[0]
    for i in range(1, list_length):
        left_running_maximums[i] = max(left_running_maximums[i - 1], number_list[i])

    # Need minimum from the right to compare
    right_running_minimums[list_length - 1] = number_list[list_length - 1]
    for i in range(list_length - 2, -1, -1):
        right_running_minimums[i] = min(right_running_minimums[i + 1], number_list[i])

    binary_searchable_count = 0
    for i in range(list_length):
        # Check if number is binary searchable
        if number_list[i] >= left_running_maximums[i] and number_list[i] <= right_running_minimums[i]:
            binary_searchable_count += 1

    return binary_searchable_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n three times. The first iteration calculates the running maximums from left to right, taking O(n) time. The second iteration calculates the running minimums from right to left, which also takes O(n) time. The final iteration checks each element against the precomputed maximums and minimums, again taking O(n) time. Since these are sequential operations, the overall time complexity is O(n) + O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm uses two auxiliary lists: one to store the running maximums from left to right and another to store the running minimums from right to left. Both of these lists have the same size as the input array, which we denote as N. Therefore, the auxiliary space used is proportional to the size of the input array, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list immediately to avoid null pointer exceptions or invalid operations.
Array with a single element	Return an empty list as a single element cannot be 'binary searchable'.
Array sorted in descending order	The binary search logic must account for this reversal, potentially by reversing the comparison direction.
Array with all identical elements	The solution should correctly identify that only the first element is binary searchable.
Array with very large numbers (potential for integer overflow)	Use appropriate data types (e.g., long) or validate intermediate calculations to prevent overflow.
Presence of duplicate binary searchable numbers	Return all occurrences of valid binary searchable numbers, or specify that only unique instances are required.
Very large array (performance considerations)	Ensure the algorithm has a time complexity no worse than O(n log n) to avoid timeouts.
Array containing negative numbers and/or zero	The solution should handle negative numbers and zero correctly, without any special treatment needed if using standard comparison operators.

Null or empty input array

How to Handle:

Return an empty list immediately to avoid null pointer exceptions or invalid operations.

Array with a single element

How to Handle:

Return an empty list as a single element cannot be 'binary searchable'.

Array sorted in descending order

How to Handle:

The binary search logic must account for this reversal, potentially by reversing the comparison direction.

Array with all identical elements

How to Handle:

The solution should correctly identify that only the first element is binary searchable.

Array with very large numbers (potential for integer overflow)

How to Handle:

Use appropriate data types (e.g., long) or validate intermediate calculations to prevent overflow.

Presence of duplicate binary searchable numbers

How to Handle:

Return all occurrences of valid binary searchable numbers, or specify that only unique instances are required.

Very large array (performance considerations)

How to Handle:

Ensure the algorithm has a time complexity no worse than O(n log n) to avoid timeouts.

Array containing negative numbers and/or zero

How to Handle:

The solution should handle negative numbers and zero correctly, without any special treatment needed if using standard comparison operators.