1966. Binary Searchable Numbers in an Unsorted Array

this one is quite hard to understand the meaning of question.

T :O(n)

S: O(n)

class Solution {
    public int binarySearchableNumbers(int[] nums) {
        int n = nums.length;
        int[] prevLargerNumber = new int[n];
        int[] nextSmallerNumber = new int[n];
        Arrays.fill(prevLargerNumber, -1);
        Arrays.fill(nextSmallerNumber, n);
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                nextSmallerNumber[stack.peek()] = nums[i];
                stack.pop();
            }
            stack.push(i);
        }
        
        stack.clear(); 
        
        // 4 3 2 1
        for (int i = n-1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                prevLargerNumber[stack.peek()] = nums[i];
                stack.pop();
            }
            stack.push(i);
        }
        
        int count = 0;
        for (int i = 0; i < n; i++) {
            // don't have any prevLargerNumber, nextSmallerNumber is what we want. so the default value doesn't change
            if (prevLargerNumber[i] == -1 && nextSmallerNumber[i] == n) {
                count++;
            }
        }
        return count;
    }
}

/*
return the number of values that are guaranteed to be found using the function, for every possible pivot selection.

how many number are guaranteed to be found?


[-1,5,2]
else if pivot < target, remove pivot and all elements to its left from the sequence
    else, remove pivot and all elements to its right from the sequence

case1
target = -1
a. pivot is -1, pivot == target, return true
b. pivot is 5, 5 > -1, remove pivot & right part [5, 2], left is [-1], so finally find -1, return true
c. pivot is 2, 2 > -1, remove pivot & right part [2], left array is [-1, 5], 
c-1: choose 5 => 5 > -1, remove pivot & right part [5] => remain -1 => ... return true
c-2: choose -1 => -1 == -1 => return true

so all conditions are true, -1 is gauranteed to be found, so result is [-1], size = 1

case 2
target = 5
2 is pivot, pivot < target => pivot and all left will be reomoved, so result is empty[], can't find 5

case 3
target = 2

5 is pivot, [5, 2] will be removed (pivot > target)
left [-1], cant find 2


if in a unsorted array,
so in which condition, the left part will be removed?
when pivot < target , left part of pivot and pivot will be removed, so if there are larger numbers in left part, they will be removed, but these larger numbers maybe are our target candidate...

in contrast,
when pivot > target, right part of the pivot and pivot...
so if there are "smaller" numbers in right part, they will be removed, but these smaller numbers maybe are our target candidate...


so we can conclude, for a pivot, if there are a prevLargerNumber of this pivot "or" a nextSmallerNumber of this pivot

this pivot can't be found at last. (prevLargerNumber or nextSmallerNumber)



for example: [-1, 2], no prevLargerNumber, nextSmallerNumber

for target -1
pivot -1 => return true
pivot 2 => return true 

for target 2
pivot -1, left [2], return true
pivot 2, => return true

[-1,5,2] => 5 has nextSmallerNumber, 2 has prevLargerNumber

-1 don't have any , so -1 is ok


5 has nextSmallerNumber so right part and 5 itself will be removed in this round
2 has prevLargerNumber so left part and 2 itself will be removed in this round

*/