Binary Searchable Numbers in an Unsorted Array

Binary Searchable Numbers in an Unsorted Array - Problem

Given an integer array nums with unique elements that may or may not be sorted, determine how many numbers are guaranteed to be found by a modified binary search algorithm.

The algorithm works as follows:

Randomly select a pivot element from the remaining sequence
If pivot equals target, return true
If pivot < target, remove pivot and all elements to its left
If pivot > target, remove pivot and all elements to its right
Repeat until sequence is empty or target is found

A number is binary searchable if it can be found regardless of which pivot is chosen at each step. Return the count of such numbers.

Input & Output

Example 1 — Mixed Array

$ Input: nums = [1, 3, 2, 4, 5]

› Output: 3

💡 Note: Numbers 1, 4, and 5 are binary searchable. Number 1 is the minimum, so it will always be found. Number 4 is greater than all elements to its left (1, 3, 2) and smaller than elements to its right (5). Number 5 is the maximum, so it will always be found. Numbers 3 and 2 are not binary searchable because they don't maintain the required ordering property.

Example 2 — Already Sorted

$ Input: nums = [1, 2, 3, 4, 5]

› Output: 5

💡 Note: When the array is already sorted, all elements are binary searchable because each element is greater than all elements to its left and smaller than all elements to its right, which guarantees the modified binary search will find them regardless of pivot selection.

Example 3 — Reverse Sorted

$ Input: nums = [5, 4, 3, 2, 1]

› Output: 1

💡 Note: In a reverse sorted array, only the minimum element (1) is binary searchable. Since 1 is smaller than all other elements, any pivot selection will eventually eliminate all larger elements, leaving 1 to be found.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹
All elements in nums are unique

Visualization

Tap to expand

Understanding the Visualization

Input Array

Unsorted array with unique elements

Analyze Positions

Check max-left and min-right conditions for each element

Count Searchable

Elements that satisfy the binary search property

Key Takeaway

🎯 Key Insight: Elements are binary searchable when they maintain proper ordering relative to their neighbors

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is that a number is binary searchable if it's greater than or equal to all elements to its left AND less than or equal to all elements to its right. Best approach uses max-left min-right analysis in O(n) time with O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Maximum Left, Minimum Right Analysis	O(n)	O(n)	A number is binary searchable if it's the maximum of all elements to its left and minimum of all elements to its right
Stack-based Monotonic Property	O(n)	O(n)	Use stack to efficiently find elements that maintain the binary search property
Brute Force Simulation	O(n × 2^n)	O(n)	Simulate the search algorithm for each number as target with all possible pivot sequences

Maximum Left, Minimum Right Analysis — Algorithm Steps

For each position, compute the maximum element in the left subarray
For each position, compute the minimum element in the right subarray
Count positions where nums[i] >= maxLeft[i] and nums[i] <= minRight[i]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int size) {
    if (size <= 1) return size;
    
    int* maxLeft = (int*)malloc(size * sizeof(int));
    int* minRight = (int*)malloc(size * sizeof(int));
    
    // Compute maximum element to the left
    maxLeft[0] = INT_MIN;
    for (int i = 1; i < size; i++) {
        maxLeft[i] = (maxLeft[i-1] > nums[i-1]) ? maxLeft[i-1] : nums[i-1];
    }
    
    // Compute minimum element to the right
    minRight[size-1] = INT_MAX;
    for (int i = size-2; i >= 0; i--) {
        minRight[i] = (minRight[i+1] < nums[i+1]) ? minRight[i+1] : nums[i+1];
    }
    
    int count = 0;
    for (int i = 0; i < size; i++) {
        if (nums[i] >= maxLeft[i] && nums[i] <= minRight[i]) {
            count++;
        }
    }
    
    free(maxLeft);
    free(minRight);
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    
    char* start = strchr(line, '[') + 1;
    char* end = strchr(start, ']');
    *end = '\0';
    
    char* token = strtok(start, ",");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",");
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to compute max left, single pass for min right, single pass to count

✓ Linear Growth

Space Complexity

O(n)

Two arrays to store maximum left and minimum right values for each position

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen