Values Safe Under Every Search Pivot
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
The unique integers in `nums` need not be sorted. A search repeatedly chooses any element of the remaining contiguous sequence as pivot. Equality with the target succeeds. A smaller pivot discards itself and everything to its left; a larger pivot discards itself and everything to its right. An empty sequence means failure. Count the input values for which this procedure succeeds for every possible sequence of pivot choices.
```cpp
class Solution {
public:
int binarySearchableNumbers(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
nums = [1,4,3,6]
Output: 2
Explanation: Values 1 and 6 survive every other pivot. Pivot 3 can discard 4, and pivot 4 can discard 3.
```
**Example 2:**
```text
nums = [3,2,1]
Output: 0
Explanation: Each target has another pivot that immediately discards it.
```
### Constraints
- `1 <= nums.length <= 10^5`.
- `-10^5 <= nums[i] <= 10^5`; values are unique.
### Clarifying Questions
The requested count is deterministic; there is no random-output API. Every pivot sequence is quantified, not sampled.
```hint Inspect the structure
Which values on either side can discard a target before it is selected?
```
### Reasoning checkpoints
- Apply the guarantee to every possible pivot sequence rather than to sampled or typical searches.
- Explain when a target can be discarded and prove that the returned count includes exactly the values that can never be lost before success.
### Optional extensions
If duplicates are permitted, what changes? State whether the count is over distinct target values or array entries, and distinguish finding a value from finding one particular occurrence.
Overview: Values Safe Under Every Search Pivot. The array nums has unique integers and may be unsorted. Consider a search that repeatedly chooses any pivot in the remaining contiguous sequence. It succeeds on equality; a smaller pivot discards itself and everything to its left, while a larger pivot discards itself and everything to its right. Emptying the sequence means failure. Count input values guaranteed to be found for every possible pivot choice.