Skip to content

1966. Binary Searchable Numbers in an Unsorted Array 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  int binarySearchableNumbers(vector<int>& nums) {
    const int n = nums.size();
    int ans = 0;
    // prefixMaxs[i] := max(nums[0..i))
    vector<int> prefixMaxs(n);
    // suffixMins[i] := min(nums[i + 1..n))
    vector<int> suffixMins(n);

    // Fill in `prefixMaxs`.
    prefixMaxs[0] = INT_MIN;
    for (int i = 1; i < n; ++i)
      prefixMaxs[i] = max(prefixMaxs[i - 1], nums[i - 1]);

    // Fill in `suffixMins`.
    suffixMins[n - 1] = INT_MAX;
    for (int i = n - 2; i >= 0; --i)
      suffixMins[i] = min(suffixMins[i + 1], nums[i + 1]);

    for (int i = 0; i < n; ++i)
      if (prefixMaxs[i] < nums[i] && nums[i] < suffixMins[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
class Solution {
  public int binarySearchableNumbers(int[] nums) {
    final int n = nums.length;
    int ans = 0;
    // prefixMaxs[i] := Math.max(nums[0..i))
    int[] prefixMaxs = new int[n];
    // suffixMins[i] := Math.min(nums[i + 1..n))
    int[] suffixMins = new int[n];

    // Fill in `prefixMaxs`.
    prefixMaxs[0] = Integer.MIN_VALUE;
    for (int i = 1; i < n; ++i)
      prefixMaxs[i] = Math.max(prefixMaxs[i - 1], nums[i - 1]);

    // Fill in `suffixMins`.
    suffixMins[n - 1] = Integer.MAX_VALUE;
    for (int i = n - 2; i >= 0; --i)
      suffixMins[i] = Math.min(suffixMins[i + 1], nums[i + 1]);

    for (int i = 0; i < n; ++i)
      if (prefixMaxs[i] < nums[i] && nums[i] < suffixMins[i])
        ++ans;

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def binarySearchableNumbers(self, nums: list[int]) -> int:
    n = len(nums)
    # prefixMaxs[i] := max(nums[0..i))
    prefixMaxs = [0] * n
    # suffixMins[i] := min(nums[i + 1..n))
    suffixMins = [0] * n

    # Fill in `prefixMaxs`.
    prefixMaxs[0] = -math.inf
    for i in range(1, n):
      prefixMaxs[i] = max(prefixMaxs[i - 1], nums[i - 1])

    # Fill in `suffixMins`.
    suffixMins[n - 1] = math.inf
    for i in range(n - 2, -1, -1):
      suffixMins[i] = min(suffixMins[i + 1], nums[i + 1])

    return sum(prefixMaxs[i] < nums[i] < suffixMins[i] for i in range(n))