CODEWITHSUNDEEP
arraysalgorithmbinary-search
Ohhh
Ohhh

Reputation: 435

Given an unsorted integer array find numbers that are not searchable

Interview question from a friend

Given an unsorted integer array, how many number are not able to find using binary search?

For example, [2, 3, 4, 1, 5], only the number 1 can't be find using binary search, hence count = 1

[4,2,1,3,5] 4 and 4 and 2 are not searchable => binarySearch(arr, n) return a number that is not equal to num

Expected run time is O(n)

Can't think of an algorithm that can achieve O(n) time :(

Thought about building min and max arr, however, woudln't work as the subarray can mess it out again.

Already knew the O(nlogn) approach, it was obvious, just call binary search for each number and check.

Upvotes: 0

Views: 693

Answers (3)

prashant
prashant

Reputation: 348

Idea: Problem can be reworded as - find the count of numbers in the array which are greater than all numbers to their left and smaller than all numbers to their right. Further simplified, find the count of numbers which are greater than the max number to their left and smaller than the minimum number to their right.

Code: Java 11 | Time/Space: O(n)/O(n)

int binarySearchable(int[] nums) {
    var n = nums.length;
   
    var maxToLeft = new int[n + 1];
    maxToLeft[0] = Integer.MIN_VALUE;
   
    var minToRight = new int[n + 1];
    minToRight[n] = Integer.MAX_VALUE;
   
    for (var i = 1; i < n + 1; i++) {
        maxToLeft[i] = Math.max(maxToLeft[i - 1], nums[i - 1]);
        minToRight[n - i] = Math.min(minToRight[n  + 1 - i], nums[n - i]);
    }

    for (var i = 0; i < n; i++)
        if (nums[i] >= maxToLeft[i + 1] && nums[i] <= minToRight[i + 1])
            count++;
    return count;
}

Upvotes: 0

ForbesLindesay
ForbesLindesay

Reputation: 10702

I believe this code works fine. It does one single walk of each value in the list, so it is O(n).

function CountUnsearchable(list, minValue = -Infinity, maxValue=Infinity) {
  if (list is empty) return 0;
  let midPoint = mid point of "list"
  let lowerCount = CountUnsearchable(left half of list, minValue, min(midPoint, maxValue));
  let upperCount = CountUnsearchable(right half of list, max(minValue, midPoint), maxValue);
  let midPointUnsearchable = 1 if midPoint less than minValue or greater than maxValue, otherwise 0;
  return lowerCount + upperCount + midPointUnsearchable;
}

It works, because we walk the tree a bit like we would in a binary search, except at each node we take both paths, and simply track the maximum value that could have led us to take this path, and the minimum value that could have led us to take this path. That makes it simple to look at the current value and answer the question of whether it can be found via a binary search.

Upvotes: 2

btilly
btilly

Reputation: 46389

Try to create the following function:

def count_unsearchable(some_list, min_index=None, max_index=None, min_value=None, max_value=None):
    """How many elements of some_list are not searchable in the
       range from min_index to max_index, assuming that by the time
       we arrive our values are known to be in the range from
       min_value to max_value.  In all cases None means unbounded."""
    pass #implementation TBD

It is possible to implement this function in a way that runs in time O(n). The reason why it is faster than the naive approach is that you are only making the recursive calls once per range, instead of once per element in that range.

Upvotes: 0

Related Questions