Opening Bell Batch
Largest equal-length prefixes with one array's minimum ≥ the other's maximum
A stock exchange is preparing a batch of trades for its opening auction. Each buy order and each sell order covers exactly one share.
You receive two arrays of prices in integer ticks:
bidscontains the maximum price each buyer will pay, sorted in non-increasing order.askscontains the minimum price each seller will accept, sorted in non-decreasing order.
For a batch of size k, the exchange selects the first k buy orders and the first k sell orders. All selected trades must use one common price p. The batch is feasible if there is an integer p that is no greater than every selected buyer's bid and no less than every selected seller's ask.
Return the largest feasible batch size. A batch of size zero is always feasible. Orders cannot be used more than once, and the batch cannot exceed the length of either array.
Examples
Example 1
Input: bids = [12,10,8,6], asks = [3,7,9] Output: 2
The first two buyers bid 12 and 10, while the first two sellers ask 3 and 7. These orders can share a price between 7 and 10. Adding the third pair would require a price at least 9 and at most 8, which is impossible.
Example 2
Input: bids = [5,5,5], asks = [5,5,5,6] Output: 3
All three selected buyers and sellers can trade at price 5. Repeated prices represent separate one-share orders.
Example 3
Input: bids = [], asks = [2,4] Output: 0
There are no buy orders, so no positive-size batch can be formed.
Constraints
- 0 <= bids.length, asks.length <= 8000
- 1 <= bids[i], asks[i] <= 10^9
- bids is sorted in non-increasing order.
- asks is sorted in non-decreasing order.
The intended solution takes O(log(min(bids.length, asks.length) + 1)) time and O(1) auxiliary space. Input arrays must not be modified.
Hints
Show hint 1Hint 1
For a positive batch size k, which selected buyer and seller impose the tightest limits on the common price?
Show hint 2Hint 2
If a batch size is infeasible, can any larger batch be feasible? Use this ordering to search the possible sizes.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return the smallest valid common price for the maximum-size batch, using -1 when the batch is empty?
- If the two arrays arrive unsorted, how would your algorithm and its time complexity change?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem