0057MediumArrayStackMonotonic Stack

Nights Until a Fuller House

Tracked in this browser only

Trains the technique from

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 repertory theatre keeps a run log: occupancy[i] is the percentage of seats sold on the i-th night of the run, in performance order.

The manager wants to know, for every night, how soon the house got fuller than it was that night. Build an array waits of the same length where waits[i] counts the nights between night i and the earliest night after it whose percentage is strictly above occupancy[i]. Nights that tie do not count as fuller. Put 0 in waits[i] when no later night in the run beats night i.

Examples

Example 1

Input: occupancy = [64, 71, 68, 68, 95, 84, 100]
Output: [1, 3, 2, 1, 2, 1, 0]

Night 1 already beats night 0, so the first entry is 1. Night 2 and night 3 both sold the same 68 percent, so night 2 has to skip past night 3 and wait for the 95 percent night.

Example 2

Input: occupancy = [88, 76, 55]
Output: [0, 0, 0]

The run only thins out, so no night is ever followed by a fuller one.

Example 3

Input: occupancy = [45, 45, 45]
Output: [0, 0, 0]

Every night sells the same share of the house, and an equal night is not a fuller night.

Constraints

1 <= occupancy.length <= 10^5
30 <= occupancy[i] <= 100

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 nights_until_fuller(occupancy: list[int]) -> list[int]:

Java

public int[] nightsUntilFuller(int[] occupancy)

The intended approach

Time O(n)Space O(n)

Sweep the run once, holding a stack of nights that are still waiting for a fuller house. The percentages of the waiting nights never climb as you go up the stack, so a new night settles every waiting night it beats, starting from the most recent, and the gap for each of those is the difference between the two positions. Once the new night stops beating the top of the stack it joins the stack itself. Whatever is still stacked at the end was never beaten and keeps the zero it started with, and each night is stacked and unstacked at most once.

Pythonentry point: nights_until_fuller

def nights_until_fuller(occupancy):
    waits = [0] * len(occupancy)
    pending = []
    for night, filled in enumerate(occupancy):
        while pending and occupancy[pending[-1]] < filled:
            earlier = pending.pop()
            waits[earlier] = night - earlier
        pending.append(night)
    return waits

The obvious version

For each night, walk forward through the rest of the run until a strictly higher percentage turns up, recording the gap or zero. Quadratic and stackless.

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_nights_until_fuller(occupancy):
    n = len(occupancy)
    waits = []
    for i in range(n):
        gap = 0
        for j in range(i + 1, n):
            if occupancy[j] > occupancy[i]:
                gap = j - i
                break
        waits.append(gap)
    return waits

How this problem was checked

Reference solution executed against 12 test cases — 12 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