Problem statement

https://binarysearch.com/problems/Randomized-Binary-Search/

Solution

Variation of Leetcode 1966 Binary Searchable Numbers in an Unsorted Array, but here we need to have strict inequlity.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums):
        t1 = list(accumulate(nums, max))
        t2 = list(accumulate(nums[::-1], min))[::-1]
        n, ans = len(nums), 0
        for i in range(n):
            lft = t1[i - 1] if i else -float("inf")
            rgh = t2[i + 1] if i + 1 < n else float("inf")
            ans += int(lft < nums[i] < rgh)
        return ans