Problem

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:

1
2
3
4
5
6
7
8

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 areguaranteed to be found using the function, for every possible pivot selection.

Examples

Example 1:

1
2
3
4
5

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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.

Follow-up: If nums has duplicates , would you modify your algorithm? If so, how?

Solution

Method 1 – Prefix and Suffix Arrays

Intuition

A number is binary searchable if all elements to its left are less than or equal to it, and all elements to its right are greater than or equal to it. We can precompute prefix maximums and suffix minimums to check this efficiently for each index.

Approach

  1. Compute prefix maximums: for each index, store the maximum value from the start up to that index.
  2. Compute suffix minimums: for each index, store the minimum value from that index to the end.
  3. For each index, check if the prefix max up to the previous index is <= current value, and the suffix min from the next index is >= current value.
  4. Count the number of such indices.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int binarySearchableNumbers(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n), suf(n);
        pre[0] = nums[0];
        for (int i = 1; i < n; ++i) pre[i] = max(pre[i-1], nums[i]);
        suf[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; --i) suf[i] = min(suf[i+1], nums[i]);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if ((i == 0 || pre[i-1] <= nums[i]) && (i == n-1 || suf[i+1] >= nums[i])) ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func binarySearchableNumbers(nums []int) int {
    n := len(nums)
    pre := make([]int, n)
    suf := make([]int, n)
    pre[0] = nums[0]
    for i := 1; i < n; i++ {
        if pre[i-1] > nums[i] {
            pre[i] = pre[i-1]
        } else {
            pre[i] = nums[i]
        }
    }
    suf[n-1] = nums[n-1]
    for i := n-2; i >= 0; i-- {
        if suf[i+1] < nums[i] {
            suf[i] = suf[i+1]
        } else {
            suf[i] = nums[i]
        }
    }
    ans := 0
    for i := 0; i < n; i++ {
        if (i == 0 || pre[i-1] <= nums[i]) && (i == n-1 || suf[i+1] >= nums[i]) {
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int binarySearchableNumbers(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n], suf = new int[n];
        pre[0] = nums[0];
        for (int i = 1; i < n; ++i) pre[i] = Math.max(pre[i-1], nums[i]);
        suf[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; --i) suf[i] = Math.min(suf[i+1], nums[i]);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if ((i == 0 || pre[i-1] <= nums[i]) && (i == n-1 || suf[i+1] >= nums[i])) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun binarySearchableNumbers(nums: IntArray): Int {
        val n = nums.size
        val pre = IntArray(n)
        val suf = IntArray(n)
        pre[0] = nums[0]
        for (i in 1 until n) pre[i] = maxOf(pre[i-1], nums[i])
        suf[n-1] = nums[n-1]
        for (i in n-2 downTo 0) suf[i] = minOf(suf[i+1], nums[i])
        var ans = 0
        for (i in 0 until n) {
            if ((i == 0 || pre[i-1] <= nums[i]) && (i == n-1 || suf[i+1] >= nums[i])) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def binarySearchableNumbers(self, nums: list[int]) -> int:
        n = len(nums)
        pre = [0]*n
        suf = [0]*n
        pre[0] = nums[0]
        for i in range(1, n):
            pre[i] = max(pre[i-1], nums[i])
        suf[-1] = nums[-1]
        for i in range(n-2, -1, -1):
            suf[i] = min(suf[i+1], nums[i])
        ans = 0
        for i in range(n):
            if (i == 0 or pre[i-1] <= nums[i]) and (i == n-1 or suf[i+1] >= nums[i]):
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn binary_searchable_numbers(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut pre = vec![0; n];
        let mut suf = vec![0; n];
        pre[0] = nums[0];
        for i in 1..n {
            pre[i] = pre[i-1].max(nums[i]);
        }
        suf[n-1] = nums[n-1];
        for i in (0..n-1).rev() {
            suf[i] = suf[i+1].min(nums[i]);
        }
        let mut ans = 0;
        for i in 0..n {
            if (i == 0 || pre[i-1] <= nums[i]) && (i == n-1 || suf[i+1] >= nums[i]) {
                ans += 1;
            }
        }
        ans
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each pass over the array is linear.
  • 🧺 Space complexity: O(n) — For prefix and suffix arrays.