Batched Binary Search
Easy About 10 min Free, no account needed
Answer twenty thousand membership queries against a sorted array.
The brief
Given a sorted integer array nums and an array queries, return how
many queries are present in nums.
The obvious approach scans the whole array for every query, O(q * n). The hidden test runs 20,000 queries against 200,000 elements, and half the queries are absent (a full scan each). The array is sorted, so each query should cost far less than a full scan; the whole batch needs to fall from billions of comparisons to a few hundred thousand.
Starter code
using System;
public class Solution
{
// TODO: return how many of the queries appear in the sorted array nums.
public int CountFound(int[] nums, int[] queries)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Binary search
- Halve a sorted search space, with exact boundaries and no off-by-one drift.
Related katas
- Kth Missing Positive Number Easy Free Find the k-th positive integer the sorted array skipped.
- Longest Increasing Subsequence Medium Free Length of the longest strictly increasing subsequence - faster than the quadratic DP.
- Minimum Travel Pass Cost Medium Free Cover sparse travel dates with overlapping pass durations while paying for no unnecessary calendar state.
- Weighted Reservation Schedule Hard Free Choose a maximum-value set of nonoverlapping reservations with a mandatory cleanup gap.