Welcome to Subscribe On Youtube
1966. Binary Searchable Numbers in an Unsorted Array
Description
Consider a function that implements an algorithm similar to Binary Search. The function has two input parameters: sequence
is a sequence of integers, and target
is an integer value. The purpose of the function is to find if the target
exists in the sequence
.
The pseudocode of the function is as follows:
func(sequence, target) while sequence is not empty randomly choose an element from sequence as the pivot if pivot = target, return true 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 end while return false
When the sequence
is sorted, the function works correctly for all values. When the sequence
is not sorted, the function does not work for all values, but may still work for some values.
Given an integer array nums
, representing the sequence
, that contains unique numbers and may or may not be sorted, return the number of values that are guaranteed to be found using the function, for every possible pivot selection.
Example 1:
Input: nums = [7] Output: 1 Explanation: Searching for value 7 is guaranteed to be found. Since the sequence has only one element, 7 will be chosen as the pivot. Because the pivot equals the target, the function will return true.
Example 2:
Input: nums = [1,5,2] Output: 1 Explanation: Searching for value 1 is guaranteed to be found. If 1 was chosen as the pivot, the function would return true. If 5 was chosen as the pivot, 5 and 2 would be removed. In the next loop, the sequence would have only 1 and the function would return true. If 2 was chosen as the pivot, 2 would be removed. In the next loop, the sequence would have 1 and 5. No matter which number was chosen as the next pivot, the function would find 1 and return true. Searching for value 5 is NOT guaranteed to be found. If 2 was chosen as the pivot, 1, 5 and 2 would be removed. The sequence would be empty and the function would return false. Searching for value 2 is NOT guaranteed to be found. If 5 was chosen as the pivot, 5 and 2 would be removed. In the next loop, the sequence would have only 1 and the function would return false. Because only 1 is guaranteed to be found, you should return 1.
Constraints:
1 <= nums.length <= 10^{5}
10^{5} <= nums[i] <= 10^{5}
 All the values of
nums
are unique.
Followup: If nums
has duplicates, would you modify your algorithm? If so, how?
Solutions

class Solution { public int binarySearchableNumbers(int[] nums) { int n = nums.length; int[] ok = new int[n]; Arrays.fill(ok, 1); int mx = 1000000, mi = 1000000; for (int i = 0; i < n; ++i) { if (nums[i] < mx) { ok[i] = 0; } mx = Math.max(mx, nums[i]); } int ans = 0; for (int i = n  1; i >= 0; i) { if (nums[i] > mi) { ok[i] = 0; } mi = Math.min(mi, nums[i]); ans += ok[i]; } return ans; } }

class Solution { public: int binarySearchableNumbers(vector<int>& nums) { int n = nums.size(); vector<int> ok(n, 1); int mx = 1000000, mi = 1000000; for (int i = 0; i < n; ++i) { if (nums[i] < mx) { ok[i] = 0; } mx = max(mx, nums[i]); } int ans = 0; for (int i = n  1; i >= 0; i) { if (nums[i] > mi) { ok[i] = 0; } mi = min(mi, nums[i]); ans += ok[i]; } return ans; } };

class Solution: def binarySearchableNumbers(self, nums: List[int]) > int: n = len(nums) ok = [1] * n mx, mi = 1000000, 1000000 for i, x in enumerate(nums): if x < mx: ok[i] = 0 else: mx = x for i in range(n  1, 1, 1): if nums[i] > mi: ok[i] = 0 else: mi = nums[i] return sum(ok)

func binarySearchableNumbers(nums []int) (ans int) { n := len(nums) ok := make([]int, n) for i := range ok { ok[i] = 1 } mx, mi := 1000000, 1000000 for i, x := range nums { if x < mx { ok[i] = 0 } else { mx = x } } for i := n  1; i >= 0; i { if nums[i] > mi { ok[i] = 0 } else { mi = nums[i] } ans += ok[i] } return }