Problem statement

https://leetcode.com/problems/binary-searchable-numbers-in-an-unsorted-array/

Solution 1

For the algorithm given in problem description to work, we need the following condition: given target, we want only smaller elements before it and bigger elements after it. For example for [1, 4, 2, 6, 9, 7, 8] we have element 6 like this and element 1 like this. So, for each element we need to find the closest smaller element to the right and closest bigger element to the right: if both of them was not found we are happy.

Complexity

Time complexity is O(n), space complexity is also O(n).

Code

class Solution:
    def binarySearchableNumbers(self, nums):
        n = len(nums)
        lft, rgh = [-1] * n, [n] * n
        
        stack = []
        for i in range(n):
            while stack and nums[i] > nums[stack[-1]]: stack.pop()
            if stack: lft[i] = stack[-1]
            stack.append(i)
            
        stack = []
        for i in range(n - 1, -1, -1):
            while stack and nums[i] < nums[stack[-1]]: stack.pop()
            if stack: rgh[i] = stack[-1]
            stack.append(i)
            
        return sum(x == -1 and y == n for x, y in zip(lft, rgh))

Solution 2

Actually, we do not really need to find the places of closest smaller element to the right: we just need to check if we have any. So, we can use accumulate maximum from left to right and accumulate minimum from right to left and take only those elements which are equal.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def binarySearchableNumbers(self, nums):
        t1 = list(accumulate(nums, max))
        t2 = list(accumulate(nums[::-1], min))[::-1]
        return sum(x == y for x, y in zip(t1, t2))