We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Searchable Numbers in an Unsorted Array

Number: 2111

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an unsorted array of unique integers (nums), we need to count how many values are “binary searchable”. A value is binary searchable if, when using the following modified binary search procedure (with a random pivot at each step), the search for that value is guaranteed to succeed regardless of the pivot choices made:

  1. While the sequence is not empty, randomly choose an element as the pivot.
  2. If the pivot equals the target, return true.
  3. If the pivot is less than the target, remove the pivot and all elements to its left.
  4. If the pivot is greater than the target, remove the pivot and all elements to its right.
  5. If the while loop finishes without finding the target, return false.

When the array is sorted, the procedure always finds the target. For an unsorted array, however, only some target values are “protected” against all bad pivot choices. We must count how many numbers in nums are guaranteed to be found regardless of how pivots are selected.

Key Insights

  • For a value to be binary searchable, it must never be accidentally removed by the elimination rule no matter which pivot is chosen.
  • If a candidate value at index i has any number to its left that is greater than it, then that number could be chosen as a pivot and, being greater than the candidate, remove the candidate along with everything on its right.
  • Similarly, if there is any number to the right of the candidate that is smaller than it, then that number might cause the candidate’s removal.
  • Thus, the candidate nums[i] is binary searchable if and only if every element to the left of it is strictly smaller and every element to the right of it is strictly larger.
  • In other words, nums[i] must be the maximum value among all elements from the start up to i and the minimum value among all elements from i to the end.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution involves two passes:

  1. A left-to-right pass that tracks the maximum value seen so far. For each index i, we note that nums[i] is “left valid” if it is greater than all elements to its left.
  2. A right-to-left pass that tracks the minimum value seen so far. For each index i, nums[i] is “right valid” if it is smaller than all elements to its right.

A number is binary searchable if it satisfies both conditions:

  • For index 0, the left condition is trivially true.
  • For index n-1, the right condition is trivially true.

We then count all indices where both conditions hold.

In the follow-up with duplicates, the strict inequalities may need to be relaxed (or carefully handled) based on whether removal rules consider equality. One possible approach is to adjust the algorithm such that a candidate is valid only if all elements to its left are less than or equal to it and all to its right are greater than or equal to it, while also considering that duplicates might result in ambiguous removals.

Code Solutions

# Python solution with line-by-line comments
def countBinarySearchable(nums):
    n = len(nums)
    # Edge case: if nums is empty, return 0
    if n == 0:
        return 0
    
    # Initialize arrays to hold the max seen so far from the left
    left_max = [0] * n
    # For the first element, it is trivially the max so far
    left_max[0] = nums[0]
    for i in range(1, n):
        # Update left_max[i] as the max of left_max[i-1] and current element
        left_max[i] = max(left_max[i-1], nums[i])
    
    # Initialize arrays to hold the min seen so far from the right
    right_min = [0] * n
    # For the last element, it is trivially the min so far
    right_min[n-1] = nums[n-1]
    for i in range(n-2, -1, -1):
        # Update right_min[i] as the min of right_min[i+1] and current element
        right_min[i] = min(right_min[i+1], nums[i])
    
    count = 0
    for i in range(n):
        # For index 0, no left elements; for index n-1, no right elements.
        # Check if the current element is greater than (or equal for boundary cases) the left block
        # and less than (or equal for boundary cases) than the right block.
        if (i == 0 or nums[i] > left_max[i-1]) and (i == n-1 or nums[i] < right_min[i+1]):
            count += 1
    return count

# Example usage:
print(countBinarySearchable([-1, 5, 2]))  # Output: 1
← Back to All Questions