0649HardArrayHash TableBinary SearchSortingPrefix SumOrdered Set

Stalls Trading When the Visitor Arrives

Tracked in this browser only

Trains the technique from

LeetCode 2251Number of Flowers in Full Bloom

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A night market runs on a single long clock measured in whole minutes. stalls[i] = [open_i, shut_i] says that stall i is trading during every minute from open_i to shut_i, and both of those minutes count: the stall is trading at minute open_i and still trading at minute shut_i.

arrivals[j] is the minute at which visitor j walks in.

Return a list answer where answer[j] is the number of stalls trading at minute arrivals[j]. Keep the answers in the same order as arrivals. Several visitors may arrive in the same minute.

Examples

Example 1

Input: stalls = [[3, 7], [5, 9], [8, 8]], arrivals = [3, 7, 8, 9, 10, 2]
Output: [1, 2, 2, 1, 0, 0]

At minute 3 only the first stall has opened. At minute 7 the first and second are both trading. At minute 8 the first has shut but the second and third are trading. At minute 9 only the second is left, and at minutes 10 and 2 nothing is trading.

Example 2

Input: stalls = [[4, 4]], arrivals = [4, 3, 5]
Output: [1, 0, 0]

The single stall opens and shuts within minute 4, so it is trading for the visitor who arrives then and for nobody else.

Example 3

Input: stalls = [[2, 6], [3, 5], [4, 4]], arrivals = [4, 6, 2, 1]
Output: [3, 1, 1, 0]

Minute 4 falls inside all three trading spans. Minute 6 is the last minute of the first stall only, minute 2 is the first minute of the first stall only, and minute 1 is before every stall opens.

Constraints

1 <= stalls.length <= 5 * 10^4
stalls[i].length == 2
1 <= stalls[i][j] <= 10^9
A stall never shuts before it opens.
1 <= arrivals.length <= 5 * 10^4
1 <= arrivals[i] <= 10^9

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def stalls_open(stalls: list[list[int]], arrivals: list[int]) -> list[int]:

Java

public int[] stallsOpen(int[][] stalls, int[] arrivals)

The intended approach

Time O(n log n + m log n): sorting the two end lists, then two binary searches per visitor.Space O(n) for the two sorted lists, beyond the returned answers.

A stall is trading at a minute when its opening minute is at most that minute and its shutting minute is not earlier than it. So the count for minute `t` is the number of opening minutes at most `t` minus the number of shutting minutes strictly below `t`. Pull the opening minutes and the shutting minutes into two separately sorted lists, then answer each visitor with two binary searches, one using an at-most test and one using a strictly-below test so that the inclusive endpoints come out right.

Pythonentry point: stalls_open

def stalls_open(stalls, arrivals):
    # A stall is trading at minute t exactly when it opened at or before t and
    # closes at or after t. Counting "opened by t" and subtracting "already shut
    # before t" needs only the two sorted end lists, never the pairs themselves.
    # O((n + m) log n) time, O(n) space.
    n = len(stalls)
    opens = sorted(s[0] for s in stalls)
    closes = sorted(s[1] for s in stalls)

    def upto(arr, t):
        # how many entries of arr are <= t
        lo, hi = 0, n
        while lo < hi:
            mid = (lo + hi) // 2
            if arr[mid] <= t:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def below(arr, t):
        # how many entries of arr are < t
        lo, hi = 0, n
        while lo < hi:
            mid = (lo + hi) // 2
            if arr[mid] < t:
                lo = mid + 1
            else:
                hi = mid
        return lo

    out = []
    for t in arrivals:
        out.append(upto(opens, t) - below(closes, t))
    return out

The obvious version

For each visitor, walk the whole stall list and count the stalls whose opening minute is not after the arrival and whose shutting minute is not before it.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_stalls_open(stalls, arrivals):
    out = []
    for t in arrivals:
        hits = 0
        for s in stalls:
            if s[0] <= t and t <= s[1]:
                hits += 1
        out.append(hits)
    return out

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in