Making a slow solution fast

You have a correct answer that runs in O(n²), and the interviewer says, "Good. Can we do better?" This is where many candidates freeze, or start swapping in data structures at random and hoping one sticks. What works better is an argument: a reason the current code is slow, and a change that removes that reason. One problem runs through this page, rewritten three times on the way from O(n²) to O(n), and each rewrite comes with a reason you could say out loud in the room. The reasons carry over to problems you haven't seen, and so does knowing when to stop.

The plain version, and where its time goes

A service logs the second at which each request arrives, as a sorted list times. Given a window length w, return the largest number of requests that fall inside any w-second window [start, start + w). With w = 60, requests at seconds 0 and 59 share a window, and requests at 0 and 60 don't. A busiest window can always slide right until its left edge sits on a request without losing anything, so trying each request as a start is enough.

def busiest_window_slow(times, w):
    best = 0
    for start in times:                   # n starts
        inside = 0
        for t in times:                   # n checks for every start
            if start <= t < start + w:
                inside += 1
        best = max(best, inside)
    return best                           # O(n²) time, O(1) extra space

Price each line by how often it runs. The outer loop runs n times, where n is the number of requests. The comparison inside runs n times for each of those, n² in all. Everything else is O(n) or less. So the inner count is where the time goes, and it is the only line worth changing: a faster max or a few skipped starts still leave O(n²). (If pricing lines is new, Big O as you'd say it in an interview comes first.)

When you price lines, watch for ones that look like a single step and hide a loop. A filter that checks if ip in blocked: scans every entry when blocked is a list, and drops to O(1) on average once you build set(blocked) one time up front. .index(), .pop(0), slices and sum() all walk their data the same way, and sorted() costs O(n log n), so price each as the loop it is.

Sorted input turns each count into a search

Here is a quick test for whether the code is ignoring something the prompt gave you: would it still be right if that fact were false? busiest_window_slow returns the same answer if you shuffle times. It pays for an order it never uses.

Sorted order means the requests inside start, start + w) sit next to each other, from the start's own position up to the first timestamp at or past start + w. So the count for a start is the distance to that boundary, and binary search finds the boundary in O(log n). [Sorting and binary search shows how to write one; here the standard library does it:

from bisect import bisect_left


def busiest_window_sorted(times, w):
    best = 0
    for i, start in enumerate(times):
        end = bisect_left(times, start + w)   # first index at or past start + w
        best = max(best, end - i)
    return best                               # O(n log n) time, O(1) extra space

That is n binary searches at O(log n) each: O(n log n) time, still O(1) extra space. Nothing else changed. The expensive line got cheaper because the code finally used the order it was handed.

Whole seconds in one day: count per second

Now suppose you ask, and the interviewer confirms that timestamps are whole seconds within a single day. That caps the possible values at T = 86,400, which a busy service passes in requests before lunch. A value range that small can be used as array positions. Count the requests at each second, then keep running totals over the seconds, where prefix[s] is the number of requests before second s. These running totals are called prefix sums, and with them any window's count is one subtraction:

def busiest_window_by_second(times, w, day=86_400):
    """times are whole seconds in [0, day); day is T, the number of possible values."""
    per_second = [0] * day
    for t in times:                            # n requests
        per_second[t] += 1
    prefix = [0]
    for count in per_second:                   # T seconds
        prefix.append(prefix[-1] + count)      # prefix[s] = requests before second s
    best = 0
    for start in range(day):                   # T possible starts
        end = min(start + w, day)
        best = max(best, prefix[end] - prefix[start])
    return best                                # O(n + T) time, O(T) memory

This costs O(n + T) time and O(T) memory. It trades memory for time: the totals are computed once and then read T times instead of being recounted. Whether the trade is good depends on numbers you should state. With ten million requests in a day it is excellent. With millisecond timestamps across a year, T runs into the tens of billions and the array no longer fits. The same running totals answer any "total over a range of positions" question in O(1), but only while the data holds still: one corrected count shifts every total after it.

A right edge that only moves forward

Go back to the sorted version and watch it run on a dozen requests, with w = 10:

1, 4, 5, 9, 12, 13, 14, 18, 21, 22, 30, 31

The boundaries its searches find, one per start, are 4, 6, 7, 8, 9, 10, 10, 10, 11, 12, 12, 12. They never go down, and they can't: as the start moves right, start + w moves right with it, so the first timestamp at or past it can only stay put or move later. Each binary search starts from scratch to find a position at or after the last one, which is work you can skip. Carry the boundary from one start to the next and nudge it forward:

def busiest_window(times, w):
    best = 0
    end = 0                                   # first index at or past start + w
    for i, start in enumerate(times):
        while end < len(times) and times[end] < start + w:
            end += 1                          # end only ever moves forward
        best = max(best, end - i)
    return best                               # O(n) time, O(1) extra space

end is running state: it survives from one start to the next instead of being found again. Most sliding-window questions turn on the same thing. You keep a small summary of the current window, such as a count, a sum or a dictionary of counts, and update it as elements enter and leave instead of rebuilding it at every position. The Blind 75 sliding window set has more to practice on.

What the interviewer sees. A candidate writes this and calls it O(n²) because a while sits inside a for. Nested loops multiply only when the inner one starts over. Here end never moves back, so across the whole run it advances at most n times, and the total is n outer steps plus at most n inner ones. The opposite slip costs more: a candidate resets end to i at the top of each pass, and the code is O(n²) again while looking like the fast version.

"The right edge only moves forward, so over the whole loop it takes at most n steps, and the outer loop takes n. That's O(n) time and O(1) extra space."

O(n) is as low as it goes

Any single request could change the answer, so every correct solution has to read all n timestamps. No answer can beat O(n). That bound is the floor, and the pointer version sits on it, so the time question is closed. Say so, and stop:

"I have to read every timestamp anyway, so time can't go lower than this. I'm happy to look at memory or a streaming version next."

Work out the floor before the first rewrite, not after the last. At the start, the gap between O(n²) and O(n) said there was room to improve. Later, it tells you there is none left, which saves you from chasing a speedup that cannot exist. When the output itself is large, for example every pair of something, its size sets the floor instead.

If you are stuck above the floor, put the costly step into words as a question ("how many timestamps lie in this range?") and ask which structure answers that question fast. If that turns up nothing, a dozen made-up values on paper often show you which work repeats.

Practicing with these questions

For each question on this page, write two things before any code: the cost of the plain solution and the floor. Then find the line where the time goes and ask why it is expensive, and stop when you reach the floor or the interviewer is satisfied, saying which. Find Maximum Window Sum is the gentlest start: write the slow version first and price it before changing anything.