Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
A notification fires when today's spend ≥ 2× the median of the trailing d days. The trick is the median: because expenditures are bounded (0..200), keep a counting-sort frequency array over the trailing-d window and read the median in O(1) per day by walking the 201 buckets. Slide the window day by day for O(n) overall (O(n·200) = O(n)).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you spot that the bounded value range (0..200) lets you replace a per-day sort with a counting-sort frequency array, getting the rolling median in O(1) and the whole problem in O(n).
Where candidates slip
Sorting the trailing window every day (O(n·d log d), times out), or mishandling the even-length median by using floating point and hitting rounding/`.5` bugs in the `≥ 2×median` test.
How to stand out
Avoid floats entirely: compute a doubled median (2×median) as an integer, and maintain the counting array with two O(1) updates per slide instead of rebuilding it.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewRolling median over a trailing d-day windowAre values bounded?NoYes (0..200)Explore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Sort the Trailing Window Each Day
1Hint 1Explore hintHide hint
For each day from index d onward, you need the median of the previous d days. What's the most direct way to get a median?
2Hint 2Explore hintHide hint
Copy the trailing d days, sort them, read the middle (or the average of the two middles), double it, and compare to today's spend.
3Hint 3Explore hintHide hint
This is correct but you re-sort a length-d window every single day. Where is the wasted work, and what about the values lets you avoid sorting at all?
A · Core idea
For every day i ≥ d, take the slice expenditure[i-d .. i-1], sort it, and read the median: the middle element for odd d, or the average of the two middle elements for even d. If today's spend is at least twice that median, count a notification.
Why it's the faithful baseline. It mirrors the definition word for word — 'median of the trailing d days' becomes 'sort those d days and look at the middle'. There's no cleverness to get wrong, so it's the correctness reference the optimal solution must match.
Why doubling the median dodges a bug. For even d the median is (m1 + m2)/2, a value that may end in .5. Comparing spend ≥ 2 × median in floating point invites rounding error right at the boundary. Instead compute the doubled median as an integer — 2·m for odd d, m1 + m2 for even d — and compare spend ≥ doubledMedian. No floats, no rounding, exact boundary behaviour.
Where the waste is. Consecutive windows overlap in d − 1 of their d elements, yet we throw the sorted order away and rebuild it from scratch every day. That redundant sorting is the whole inefficiency. At n = 2·10⁵ and large d, O(n · d log d) is billions of operations — too slow.
The hint the constraints scream. Expenditures are bounded to 0..200. A bounded value range is the textbook signal for counting sort, which sorts (and thus medians) in linear time without comparisons — and, crucially, supports O(1) incremental updates as the window slides.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
d = 3, expenditure = [10, 20, 30, 100]day 3, spend 100
trailing [10,20,30] sorted → median 20
doubled median = 401C · Code with teaching comments
Reference implementation previewpublic int notifications(int[] expenditure, int d) { int n = expenditure.length; int notifications = 0; for (int i = d; i < n; i++) { int[] window = Arrays.copyOfRange(expenditure, i - d, i);Explore the full codeHide the full code
D · Why it works and complexityO(n · d log d) timeO(d) spaceOpen the invariant and proofExplore the proofHide the proof
Overlapping windows mean 99% of each day's sort is repeated work. The fix isn't a faster sort — it's to maintain a structure that updates in O(1) as the window moves. Bounded values make that structure a counting array.
ComplexityO(n · d log d) time, O(d) space — For each of the ~n days we copy and sort d elements in O(d log d), giving O(n · d log d). The scratch window uses O(d) space.
E · Edge cases and pitfalls3Re-sorting the whole window every day — O(n·d log d) times out for large inputs.Explore edge casesHide edge cases
Pitfalls
- Re-sorting the whole window every day — O(n·d log d) times out for large inputs.
- Using floating-point median — rounding errors at the ≥ boundary on even windows.
- Including today (index i) in the trailing window — the median must be of the PREVIOUS d days.
Approach 2 of 2 · Optimal
Counting-Sort Frequency Window (Optimal)
1Hint 1Explore hintHide hint
Expenditures only range 0..200. What sorting technique exploits a small bounded value range and runs in linear time?
2Hint 2Explore hintHide hint
Keep a 201-element frequency array for the current trailing window. The median is the value at rank d/2 (and d/2+1 for even d) — find it by walking the buckets and accumulating counts until you pass the rank.
3Hint 3Explore hintHide hint
Slide the window in O(1): when you move to the next day, decrement the bucket of the day leaving the window and increment the bucket of the day entering it. Never rebuild the array.
A · Core idea
Maintain a frequency array count[0..200] describing the current trailing-d-day window. Seed it with the first d days. Then for each day i from d to n−1: read the doubled median from count in O(1), test the notification, then slide the window by decrementing the bucket of the day leaving (expenditure[i-d]) and incrementing the day entering (expenditure[i]).
Why counting sort is the right hammer. The values are confined to 0..200. A counting (bucket) sort represents a multiset of such values as 201 counters, and it sorts in linear time without comparisons. More importantly for us, it supports incremental updates: adding or removing one value is a single increment or decrement. That's exactly what a sliding window needs.
How the median falls out of the buckets — rank walking. Sorted order over a counting array is implicit: bucket 0's items come first, then bucket 1's, and so on. To find the value at a given rank k (1-indexed), walk the buckets from 0, accumulating a running total seen += count[v]; the first bucket where seen ≥ k holds the rank-k value. For odd d the median is the value at rank d/2 + 1. For even d it's the average of ranks d/2 and d/2 + 1; we sum those two values to get the doubled median and keep everything integer. Each walk touches at most 201 buckets — a constant — so it's O(1).
Why the doubled-median test avoids floats. The condition spend ≥ 2 × median becomes spend ≥ doubledMedian, where doubledMedian is 2·v (odd) or v1 + v2 (even). Both are integers, so the boundary case (e.g. spend exactly equal to twice the median) is decided exactly, with no rounding. Floating point here is a classic source of off-by-epsilon wrong answers.
Why sliding is O(1), not O(d). Consecutive windows differ by exactly two elements: one leaves the left edge, one enters at the right. So we don't rebuild the 201 buckets — we apply two updates. This is the entire reason the algorithm is linear instead of O(n·d). Decrement the leaving day's bucket and increment the arriving day's; forgetting either corrupts the window.
Why we read the median before sliding. The notification on day i is judged against the previous d days, so the median query must happen while count still reflects days i−d .. i−1. Only after testing do we slide today's value in. Swapping the order leaks today's spend into its own median window — a subtle correctness bug.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
d = 5, expenditure = [2, 3, 4, 2, 3, 6, 8, 4, 5]Array state
day 5
window=[2,3,4,2,3], 2×median=6, spend 6 ≥ 6 → notify
2C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Bounded values convert an order-statistic query into a fixed-width bucket walk, and a sliding window converts a full rebuild into two counter updates. Together they drop O(n·d log d) to O(n). Whenever you see a small value bound next to repeated order-statistic queries, reach for a counting array — the same idea powers rolling-mode and bounded-range top-k problems.
ComplexityO(n) time, O(1) space — Initial fill is O(d). Each of the ~n days does one median query (a walk over ≤ 201 buckets, O(1) since the bound is constant) plus two O(1) bucket updates. Total O(n · 201) = O(n); the 201-entry array is O(1) space.
E · Edge cases and pitfalls6d = 4, expenditure = [1, 2, 3, 4, 4] — Even window [1,2,3,4]: doubled median = 2 + 3 = 5; spend 4 < 5 → no notification. Integer doubling handles the 2.5 median exactly.Explore edge casesHide edge cases
Edge cases handled
d = 4, expenditure = [1, 2, 3, 4, 4]Even window [1,2,3,4]: doubled median = 2 + 3 = 5; spend 4 < 5 → no notification. Integer doubling handles the 2.5 median exactly.all equal spends, e.g. [50,50,50,50]Median 50, doubled 100; spend 50 < 100 → never notifies.d = nNo day has a full trailing window (notifications start at index d = n, loop never runs) → 0.
Pitfalls
- Sliding before reading the median — leaks today's spend into its own window.
- Forgetting one of the two slide updates — the window desynchronises and medians go wrong.
- Using a floating-point median instead of the doubled integer median — rounding bugs on even windows.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int notifications(int[] expenditure, int d) { int n = expenditure.length; int[] count = new int[201]; for (int i = 0; i < d; i++) { count[expenditure[i]]++;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Floating-point median on even windows
For even d the median can end in .5; a float comparison at the ≥ boundary can round the wrong way. Doubling keeps it exact.
Explore the code comparisonHide the code comparison
Floating-point median on even windows
For even d the median can end in .5; a float comparison at the ≥ boundary can round the wrong way. Doubling keeps it exact.
Don't write this
median = (window[d // 2 - 1] + window[d // 2]) / 2
if expenditure[i] >= 2 * median:
count += 1Write this instead
doubled_median = window[d // 2 - 1] + window[d // 2]
if expenditure[i] >= doubled_median:
count += 12Sliding the window before reading the median
The notification is judged against the PREVIOUS d days. Updating the counts first contaminates the window with today's spend.
Explore the code comparisonHide the code comparison
Sliding the window before reading the median
The notification is judged against the PREVIOUS d days. Updating the counts first contaminates the window with today's spend.
Don't write this
count[expenditure[i - d]]--;
count[expenditure[i]]++;
int doubledMedian = doubledMedian(count, d);
if (expenditure[i] >= doubledMedian) notifications++;Write this instead
int doubledMedian = doubledMedian(count, d);
if (expenditure[i] >= doubledMedian) notifications++;
count[expenditure[i - d]]--;
count[expenditure[i]]++;3Rebuilding the frequency array each day
Re-counting all d elements every day is O(n·d) and defeats the purpose. Consecutive windows differ by two elements — apply two updates instead.
Explore the code comparisonHide the code comparison
Rebuilding the frequency array each day
Re-counting all d elements every day is O(n·d) and defeats the purpose. Consecutive windows differ by two elements — apply two updates instead.
Don't write this
for i in range(d, n):
count = [0] * 201
for v in expenditure[i - d:i]:
count[v] += 1
# ... query median ...Write this instead
for i in range(d, n):
# ... query median ...
count[expenditure[i - d]] -= 1
count[expenditure[i]] += 1Revise
Carry the pattern into the interview
Pattern to remember
Sliding window + counting-sort median on a bounded value range
Code pattern to memorize
fill count[] with first d days
for i from d to n-1:
med2 = doubledMedian(count, d) # 2 * median, integer-only
if spend[i] >= med2: notifications++
count[spend[i-d]]--; count[spend[i]]++ # slide the windowRules to remember
- 1Compare against 2 × median, not the median — and keep it integer by computing a doubled median to dodge the even-length
.5case. - 2Values are bounded
0..200, so a 201-bucket counting-sort array gives the median in O(1) per day — no per-day sort needed. - 3Median of
ditems: oddd→ the single middle (rankd/2 + 1); evend→ average of ranksd/2andd/2 + 1. Double it to stay in integers. - 4Slide the window with two updates per day: decrement the leaving day's bucket, increment the arriving day's — never rebuild the array.
- 5Start counting notifications only from day index
d(you need a full trailing window first). Use along/intcarefully — count can reach ~n.
Use this pattern when
- Repeated median / order-statistic queries over a sliding window of fixed size
- Values come from a small bounded range (counting sort applies)
- A streaming 'compare today to a rolling statistic' rule
- You need O(1) amortised per-window statistic, not a per-window sort
Choose another pattern when
- Values are unbounded / real numbers → counting sort fails; use two heaps or an order-statistics tree
- Window size changes per query → fixed-window counting trick doesn't directly apply
- You need an exact running median over the whole stream → two-heap median, not a bucket array
- The statistic isn't an order statistic (e.g. variance) → different structure
Interview takeaway
When you need a rolling median and the values are bounded, a counting-sort frequency array turns each median query into an O(1) bucket walk. 'Bounded values → counting sort → O(1) order statistic' is the move that collapses an O(n·d log d) solution to O(n).
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternSliding window + counting-sort order statistic on bounded values. Recognise it when a rolling median/percentile is needed and values are small-bounded — a frequency array gives O(1) queries and O(1) slides. Without the bound, switch to a two-heap or balanced-BST rolling median.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Sliding Window MedianComing soonUnbounded values — use two heaps or an order-statistics tree for the rolling median.
- Find Median from Data StreamComing soonMaintain a running median with a max-heap/min-heap pair.
- Sliding Window MaximumComing soonRolling extremum via a monotonic deque — the max cousin of this rolling-statistic family.
- Sort ColorsComing soonCounting sort on a tiny value range (0,1,2) — the same bounded-values idea.