Teaching Kids Programming – K Numbers Greater Than or Equal to K using Binary Search

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of non-negative integers nums. If there are exactly k numbers in nums that are greater than or equal to k, return k. Otherwise, return -1.

Constraints
1 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [5, 3, 0, 9]
Output
3
Explanation
There are exactly 3 numbers that’s greater than or equal to 3: [5, 3, 9].

Hint #1
Bucket sort, or can you binary search K?
Hint #2
sort the array then do binarysearch on k

Binary Search Algorithm: K Numbers Greater Than or Equal to K

We need to define a function to compute the number of elements that are greater than or equal to K. We can do this linear time:

def f(k, nums): # O(N)
  ans = 0
  for i in nums:
    if i >= k:
      ans += 1
  return ans

Can we do better? We can sort and search in the reverse direction – exit the for check if the number is smaller than K – however, the complexity is still O(N) as it is still linear scan.

nums.sort()  # O(NLogN)
def f(k, nums):
  ans = 0
  for i in range(len(nums) - 1, -1, -1):
     if nums[i] < k:
        break
     ans += 1
  return ans

We can binary search using bisect_left to find out the insertion position/index if K is to insert in the list, and then compute the number of elements that are greater or equal to K. The time complexity is O(LogN).

nums.sort()
def f(k):
  return len(nums) - bisect.bisect_left(nums, k)

With this in mind, we can then binary search the K value:

class Solution:
    def solve(self, nums):
        nums.sort()
        left, right = 1, max(nums)
        def f(k):
            return len(nums) - bisect.bisect_left(nums, k)
        while left <= right:
            mid = (left + right) // 2
            cur = f(mid)
            if cur == mid:
                return mid
            if cur < mid:
                right = mid - 1
            else:
                left = mid + 1
        return -1

The overall complexity is O(LogN+LogMLogN) where N is the number of length in the array, and M is the max(nums).

–EOF (The Ultimate Computing & Technology Blog) —