Problems
Start at the top. The first group is the merge sweep itself - sort by start, extend the last interval when the next one touches it, append otherwise - and every group after it is that identical loop with a different thing measured at the end. Learn the sweep once and the rest of the page is deciding what to do with merged.
Merge overlapping
The merged list itself is the answer, so this is the loop worth memorising. Everything below reuses it verbatim.
56. Merge Intervals
Sort the intervals by start time first - once sorted, every interval that overlaps the most recently merged interval (merged[-1]) is guaranteed to appear immediately after it, so a single left-to-right scan is enough. Two helper lambdas name the two operations: doesIntersect(a, b) is the overlap test (a[1] >= b[0] and b[1] >= a[0]), and getMerged(a, b) is the union of two overlapping intervals (min of the starts, max of the ends). For each inter, if it intersects merged[-1], replace it with getMerged(merged[-1], inter). Otherwise inter starts a new, disjoint run - append it to merged as-is.
- Time
- O(n + n log n)
- A single
O(n)merge scan, plusO(n log n)to sort first -n + n log n. - Space
- O(sort + n)
mergedholds up tonintervals in the worst case, when nothing overlaps at all, on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
57. Insert Interval
The input is already sorted and disjoint, so newInterval needs to be merged into at most one contiguous run - no full sort is needed, just a single left-to-right scan. Three helper lambdas name the operations: doesIntersect(a, b) tests overlap, getMerged(a, b) returns the union of two overlapping intervals, and isInGapStrictly(left, right, a) checks whether a fits entirely in the gap between left and right without touching either. For each inter, if it overlaps newInterval, fold newInterval into it via getMerged; otherwise, if newInterval fits in the gap before inter, insert it ahead of inter. Either way, inter (possibly just merged with newInterval) is then merged into merged[-1] if it overlaps, or appended as a new run. A trailing check after the loop catches newInterval landing entirely after the last interval.
- Time
- O(n)
- A single left-to-right scan over
intervals, with each lambda doingO(1)work. - Space
- O(n)
mergedholds up ton + 1intervals in the worst case, whennewIntervaldoesn't overlap anything.
228. Summary Ranges
nums is already sorted and distinct, so this reuses the same doesIntersect/getMerged interval-merge machinery as [[56. Merge Intervals]] by treating each value i as the half-open interval [i-1, i] - two values land in the same run exactly when their intervals touch, which happens precisely when they're consecutive integers. Walk nums once: fold inter into merged[-1] via getMerged whenever it intersects, otherwise start a new [i, i] run. A second pass formats each run - a single-element run (i == j) prints as just the number, anything wider prints as "i->j".
- Time
- O(2n)
- One
O(n)pass to buildmerged, oneO(n)pass to formatres-2n. No sorting needed sincenumsis already sorted. - Space
- O(n)
mergedandreseach hold up tonentries, when every value starts its own run.
Do any overlap
Now throw the list away and keep a boolean. Because merged only ever grows when the next interval doesn't touch the last one, "did anything overlap" is just "did the merged list come out shorter than the input" - which means you can answer it without building the list at all, bailing out the first time the sweep would have merged. With only two intervals the sweep collapses to a single disjoint test.
2446. Determine if Two Events Have Conflict
The overlap test is symmetric - doesIntersect(a, b) is a[1] >= b[0] and b[1] >= a[0] - so no swapping or fixed ordering is needed. toMinutes converts each "HH:MM" bound into a single comparable integer; mapping it over event1 and event2 turns them into [start, end] integer pairs a and b, which doesIntersect compares directly. Using >= rather than > means touching endpoints (one event ending exactly when the other starts) count as a conflict.
- Time
- O(1)
- Every event has exactly two fixed-length
"HH:MM"strings - parsing and comparing them is a constant number of operations regardless of input. - Space
- O(1)
- Only two fixed-size, 2-element lists (
a,b) are held at once.
252. Meeting Rooms
Sort by start, then merge exactly like [[56. Merge Intervals]], but with a strict overlap test - doesIntersectStrictly(a, b) = a[1] > b[0] and b[1] > a[0] - so meetings that merely touch at an endpoint ([1,5] then [5,10]) don't count as conflicting. If inter intersects merged[-1], fold it in via getMerged; otherwise inter starts a new run and gets appended as-is. If no two meetings ever overlapped, every interval became its own run, so merged ends up exactly as long as intervals. Any overlap collapses at least two entries into one, shrinking merged - comparing the two lengths is enough to answer.
- Time
- O(n + n log n)
- A single
O(n)merge scan, plusO(n log n)to sort first -n + n log n. - Space
- O(sort + n)
mergedholds up tonintervals in the worst case, when nothing overlaps at all, on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
729. My Calendar I
self.intervals is kept sorted and disjoint at all times, so a booking is accepted exactly when it fits into one of the gaps between consecutive stored intervals. The [-1, -1] sentinel at the front means every real interval has a left neighbour, so the scan can start at i = 1 and compare the pair (intervals[i-1], intervals[i]) without a special case for the front. Bookings are half-open - [10, 20) and [20, 30) do not conflict - which is why the gap test is the inclusive isInGap (>=, <=) and the overlap test is the strict doesIntersectStrictly (>). Walking left to right, the first gap that swallows newInterval wins and it is spliced in there; if instead newInterval strictly overlaps intervals[i], the booking is rejected. Reaching the end of the loop means it sits past every stored interval, so it is appended.
- Time
- O(2n)
bookscans up tonstored intervals, and the acceptinginsertshifts up tonof them - two linear passes over the list per call.nis the number of bookings already accepted, soncalls costO(n^2)overall.- Space
- O(n)
self.intervalsholds one entry per accepted booking, plus the sentinel.
Count the merged groups
A step further than a plain overlap flag: instead of stopping at the first merge, run the whole sweep and count how many disjoint groups merged ends up with. Each group is independent of every other, so a question like "how many ways can you 2-color the ranges so no overlapping pair shares a color" is just 2 raised to that group count.
2580. Count Ways to Group Overlapping Ranges
Run the same merge sweep as Merge Intervals: sort by start, and for each inter, merge it into merged[-1] when it intersects, otherwise append it as a new run. Every group in merged is independent of every other group, so each one can go into group 1 or group 2 on its own - 2^len(merged) total assignments, taken mod 1e9 + 7.
- Time
- O(n + n log n)
- A single
O(n)merge scan, plusO(n log n)to sort first -n + n log n. - Space
- O(sort + n)
mergedholds up tonintervals in the worst case, when nothing overlaps at all, on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
How much is covered
Same idea, but the measurement is a number rather than a flag: the union's total length, how many integer points it contains, or whether it swallows a given target range. As above, nothing is returned, so each of these has a version that never allocates a list and just accumulates while merging.
495. Teemo Attacking
Each attack at time i poisons the inclusive window [i, i + duration - 1] - the same shape as Merge Intervals, just with the interval computed on the fly instead of given directly, using the same doesIntersect/getMerged helpers. If the next attack's window intersects the currently open one, fold it in via getMerged; otherwise it opens a new, disjoint window. Once merged holds only disjoint windows, a second pass sums each window's length with intervalSize(a) = a[1] - a[0] + 1.
- Time
- O(2n)
- Two full linear passes: one to merge (
O(n)), one to sum the merged windows (O(n)) -2n. No sort needed at all -timeSeriesis already non-decreasing, unlike the general interval-merge problems this technique is borrowed from. - Space
- O(n)
mergedholds up tondisjoint windows in the worst case, when no two attacks' windows touch.
2848. Points That Intersect With Cars
First merge overlapping intervals exactly as in Merge Intervals: sort by start, then fold inter into merged[-1] via getMerged whenever doesIntersect says the two overlap, otherwise append it as a new run. Once merged holds only disjoint runs, a second pass adds up how many integer points each run covers - j - i + 1, since both endpoints are inclusive.
- Time
- O(2n + n log n)
- Two separate linear passes - one to merge (
O(n)), one to sum the merged runs (O(n)) - plusO(n log n)to sort first:2n + n log n. - Space
- O(sort + n)
mergedholds up tondisjoint intervals in the worst case, on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
1893. Check if All the Integers in a Range Are Covered
Sort ranges and merge overlapping ones via doesIntersect/getMerged exactly as in [[56. Merge Intervals]], except each inter is first widened to [inter[0]-1, inter[1]] so that touching ranges (e.g. [1,2] and [3,4]) merge into one run instead of staying separate - the -1 closes the one-unit gap between consecutive integer ranges. Once merged holds only disjoint (widened) runs, a second pass checks each one: shifting back to [i, j] = [inter[0]+1, inter[1]] undoes the widening, and [left, right] is covered exactly when some run's [i, j] contains it entirely - left >= i and right <= j.
- Time
- O(2n + n log n)
- Two separate linear passes - one to merge (
O(n)), one to check every merged run for containment (O(n)) - plusO(n log n)to sort first:2n + n log n. - Space
- O(sort + n)
mergedholds up tondisjoint runs in the worst case, on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
452. Minimum Number of Arrows to Burst Balloons
Sort the balloons by start so overlapping runs sit next to each other. Two lambdas name the two checks: doesIntersect(a, b) tests overlap (a[1] >= b[0] and b[1] >= a[0]), and getIntersection(a, b) shrinks the overlap window to (max of starts, min of ends). For each inter, if it overlaps the last entry in intersection, one arrow already covers both - narrow that entry's window instead of adding a new one. Otherwise inter needs its own arrow - append it. The final arrow count is len(intersection).
- Time
- O(n + n log n)
- A single
O(n)scan over the sorted points, plusO(n log n)to sort first -n + n log n. - Space
- O(sort + n)
intersectionholds up tonwindows in the worst case, when no balloons overlap at all, on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
435. Non-overlapping Intervals
Sort by start, then sweep. doesIntersectStrictly(a, b) treats touching endpoints as fine - only a true overlap (a[1] > b[0] and b[1] > a[0]) counts. When inter overlaps the last kept interval, one of the two has to be removed - shrink the kept slot to getIntersection(intersection[-1], inter) (the narrower of the two end points, min(a[1], b[1]), survives), since that leaves the most room for what comes next, and bump count. Otherwise inter is disjoint from everything kept so far - append it. count ends up as the minimum number of removals.
- Time
- O(n + n log n)
- A single
O(n)scan over the sorted intervals, plusO(n log n)to sort first -n + n log n. - Space
- O(sort + n)
intersectionholds up tonkept intervals in the worst case, when nothing overlaps at all, on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
1288. Remove Covered Intervals
Sort by start ascending, breaking ties by end descending (-i[1]) so that when two intervals share a start, the longer one is considered first - guaranteeing any interval that follows with the same start is trivially contained. doesContain(a, b) returns whether a fully covers b (a[0] <= b[0] and b[1] <= a[1]). Sweep the sorted intervals: if the last kept interval already contains inter, skip it (nothing to do, hence the ... no-op); otherwise append inter to merged, since it introduces coverage nothing kept so far provides. merged ends up holding only the intervals that survive, so its length is the answer.
- Time
- O(n + n log n)
- A single
O(n)scan over the sorted intervals, plusO(n log n)to sort first -n + n log n. - Space
- O(sort + n)
mergedholds up tonkept intervals in the worst case, when nothing is covered, on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
What is not covered
The complement. Merge as usual, but report the gaps between consecutive merged intervals rather than the intervals themselves. The only real work beyond the previous group is the two boundary gaps: one before the first interval and one after the last, both clipped to whatever outer range the problem gives you.
163. Missing Ranges
nums is already sorted and distinct, so this reuses the [i-1, i] trick from [[228. Summary Ranges]]: each value n becomes the interval [n-1, n], and two values fall in the same covered run exactly when they're consecutive. Bracket the whole range with two sentinel points, [lower-1, lower-1] before lower and [upper, upper] after upper, so a gap at either edge of [lower, upper] is found by the exact same logic as a gap in the middle. Merge overlapping intervals via doesIntersect/getMerged exactly as in [[56. Merge Intervals]]. Once merged holds only disjoint covered runs (plus the two sentinels), a second pass checks every adjacent pair: the missing range between them is [merged[i][1]+1, merged[i+1][0]], kept only when that start doesn't exceed that end.
- Time
- O(2n)
- Two separate linear passes - one to merge (
O(n)), one to scan adjacent merged pairs for gaps (O(n)) -2n. No sort needed sincenumsis already sorted. - Space
- O(n)
mergedholds up tondisjoint runs plus the two sentinels, andansholds up to as many gaps, both in the worst case.
2655. Find Maximal Uncovered Ranges
ranges covers parts of [0, n-1], so sort by start and merge overlapping ranges via doesIntersect/getMerged exactly as in [[56. Merge Intervals]]. Bracket the covered runs with two sentinel ranges, [-1, -1] before 0 and [n, n] after n-1, so an uncovered stretch at either edge of [0, n-1] is found by the exact same logic as one in the middle. Once merged holds only disjoint covered runs (plus the two sentinels), a second pass checks every adjacent pair: the uncovered range between them is [merged[i][1]+1, merged[i+1][0]-1], kept only when that start doesn't exceed that end.
- Time
- O(2n + n log n)
- Two separate linear passes - one to merge (
O(n)), one to scan adjacent merged pairs for gaps (O(n)) - plusO(n log n)to sort first:2n + n log n. - Space
- O(sort + n)
mergedholds up tondisjoint runs plus the two sentinels, andansholds up to as many gaps, both in the worst case, on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
3169. Count Days Without Meetings
Bracket the whole range with two sentinel meetings, [0, 0] before day 1 and [days+1, days+1] after the last day, so the free stretch before the first real meeting and after the last one falls out of the same logic as every gap in between. Merge overlapping meetings exactly as in [[56. Merge Intervals]]: sort by start, then fold inter into merged[-1] whenever they intersect, otherwise append it as a new run. Once merged holds only disjoint runs (plus the two sentinels), a second pass sums the free days strictly between every adjacent pair - getGap(a, b), i.e. max(a0, b0) - min(a1, b1) - 1.
- Time
- O(2n + n log n)
- Two separate linear passes - one to merge (
O(n)), one to sum the gaps between merged runs (O(n)) - plusO(n log n)to sort first:2n + n log n. - Space
- O(sort + n)
mergedholds up tondisjoint intervals plus the two sentinels in the worst case, on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
3964. Minimum Lights to Illuminate a Road
Every working light at index i with range v illuminates [i - v, i + v], clipped to the road [0, n-1]; a sentinel [n, n] is appended so the sweep always closes out the final gap. doesIntersect checks whether an interval touches the last merged span, and getMerged extends that span when it does. When the next interval is disjoint, getGap measures the dark stretch between the last merged span and it; a single new light of range 1 covers 3 positions, so (gap + 2) // 3 new lights are needed to close it before the sweep starts a fresh merged span.
- Time
- O(n + n log n)
- Building
intervalsis a singleO(n)pass overlights, plusO(n log n)to sort them, plus anotherO(n)sweep to merge and count gaps -n + n log nafter collapsing the two same-ordernpasses into2n, written here alongside the sort term. - Space
- O(sort + n)
intervalsandmergedeach hold up ton + 1entries in the worst case, on top of the sort's own working memory.- Python's
list.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
759. Employee Free Time
Flatten every employee's schedule into one list of (start, end) tuples and sort it into busy. Merge overlapping intervals via doesIntersect/getMerged exactly as in [[56. Merge Intervals]]. Once merged holds only the disjoint busy runs across the whole company, a second pass walks every adjacent pair and reports the gap between them as an Interval via getGapInterval.
- Time
- O(2n + n log n)
busyis built and sorted over allnintervals across every employee -O(n log n).- One linear pass merges
busyintomerged(O(n)), and a second linear pass overmergedreports the gaps (O(n)) - two separate linear passes:2n + n log n. - Space
- O(sort + n)
busyandmergedeach hold up tonintervals in the worst case, on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()/sorted()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
Peak concurrent overlap
Not merge-based at all: turning each interval into a +1 at its start and a -1 at its end and sweeping the sorted events gives a running count of how many intervals are active at any instant. The maximum that count ever reaches is the answer whenever the question is "how many things overlap at once", rather than "do any overlap" or "what's covered".
253. Meeting Rooms II
Instead of merging intervals, turn each one into two timestamped events - (start, +1) and (end, -1) - and sort all 2n of them by point. Sweeping left to right and accumulating active tracks exactly how many meetings are in progress at that instant; because a (point, -1) sorts before a (point, +1) at the same tick, a meeting ending at 5 frees its room before one starting at 5 claims it, so touching meetings never double-count. maxi is the largest active ever reaches, which is the fewest rooms that can cover every meeting simultaneously.
- Time
- O(2n + n log n)
- Building the
2nevents and the final scan over them are each a singleO(n)pass, which combine into2n- plusO(n log n)to sort the events. - Space
- O(sort + n)
eventsholds2ntuples, which isO(n), on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
1094. Car Pooling
1094Car Pooling
Same sweep as [[253. Meeting Rooms II]], but the delta carried by each event is the passenger count instead of a flat ±1: every trip becomes a (start, +num) and an (end, -num). Sweeping the sorted events and accumulating active tracks exactly how many passengers are in the car at that instant - a passenger's seat frees up at their drop-off point before a new pickup at that same point claims it, since -num sorts before +num at equal points. The moment active exceeds capacity the car is already overfull, so return False immediately rather than waiting to find a peak.
- Time
- O(2n + n log n)
- Building the
2nevents and the final scan over them are each a singleO(n)pass, which combine into2n- plusO(n log n)to sort the events. - Space
- O(sort + n)
eventsholds2ntuples, which isO(n), on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
2406. Divide Intervals Into Minimum Number of Groups
Same sweep as [[253. Meeting Rooms II]], but each interval here is inclusive on both ends, so two intervals that only touch ([1, 3] and [3, 5]) still intersect at the shared point 3 and need separate groups. That's why the end event fires at b+1 rather than b: pushing the -1 one point past the interval's own end keeps it active through its last point instead of releasing early at a tick another interval might still be occupying. Sweeping the sorted events and accumulating active then tracks how many intervals are simultaneously open at that instant, and the largest active ever reaches is the minimum number of groups needed.
- Time
- O(2n + n log n)
- Building the
2nevents and the final scan over them are each a singleO(n)pass, which combine into2n- plusO(n log n)to sort the events. - Space
- O(sort + n)
lineholds2npairs, which isO(n), on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
1419. Minimum Number of Frogs Croaking
Each 'c' opens a new frog's croak and each 'k' closes one, so buckets[idx] records +1/-1 at the index where that happens and active accumulates it into a running count of frogs mid-croak - maxi is the largest that count ever reaches. Alongside that, counter tallies how many of each letter have been seen, and the string is only a valid sequence of croaks if those tallies stay non-increasing in the order c >= r >= o >= a >= k at every prefix - a 'r' can't appear before its 'c', an 'o' before its 'r', and so on. Any violation returns -1 immediately, and a mismatched final c/k count (a croak left open) also returns -1.
- Time
- O(n)
- A single pass over
croakOfFrogs, doingO(1)work per character, wheren = len(croakOfFrogs). - Space
- O(n)
bucketsis allocated to lengthneven though only the current index is ever read or written.counterholds at most the 5 fixed keys of"croak", independent ofn.
1854. Maximum Population Year
Same sweep as [[253. Meeting Rooms II]]: every [start, end) log becomes a (start, +1) and an (end, -1), and sweeping the sorted events tracks how many people are alive at that instant. Sorting the raw tuples puts a tie's -1 before its 1 at the same year, so a death is processed before a birth landing on the same year - the running active never briefly double-counts. maxi starts at (-1, 1930) below any possible population, and is only replaced the moment active beats the current best, so the first year to reach the peak wins ties.
- Time
- O(2n + n log n)
- Building the
2nevents and the final scan over them are each a singleO(n)pass, which combine into2n- plusO(n log n)to sort the events. - Space
- O(sort + n)
lineholds2npairs, which isO(n), on top of the sort's own working memory.- Sorting algorithms are typically
O(log n)space (in-place, recursion-stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
370. Range Addition
Same sweep as [[253. Meeting Rooms II]], but instead of a flat ±1 the delta is each update's own weight, and instead of one running peak the running active value has to be written into every position of the output, not just checked at a point. Every update becomes a (start, +weight) and an (end+1, -weight) (the +1 makes the range inclusive of end), and the sorted events are swept in order. Between two consecutive event points the value never changes, so before applying the next event's delta, res[prev:point+1] is backfilled with the active value that was already in force across that whole flat stretch; only after that does active pick up curr and res[point] get overwritten with the new value that starts exactly there.
- Time
- O(2n + n log n + length)
- Building the
2nevents and sweeping all of them is oneO(n)pass each -2ncombined - plusO(n log n)to sort the events. - The inner
forloop never revisits an index: across the whole sweep it backfills every position ofresfrom0tolengthexactly once, anO(length)pass on top. - Space
- O(sort + n + length)
lineholds2npairs,O(n).resislength + 1elements,O(length).- Sorting algorithms are typically
O(log n)space (in-place, recursion-stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
2381. Shifting Letters II
Same difference array as [[370. Range Addition]], but the delta at each index is a shift direction instead of an arbitrary weight: direction is normalized to -1/+1, added at start and subtracted at end+1. A single left-to-right scan over buckets then accumulates active into the net number of forward shifts every character has accumulated by that index - every shift whose range covers point and hasn't ended yet contributes its direction. Each original character is looked up in alphabet_map, shifted by active positions, and wrapped with %26 before being appended to ans.
- Time
- O(4n + m + 26)
- Allocating
bucketsis oneO(n)pass; slicingbuckets[:-1]copies anotherO(n); the scan over that slice is a thirdO(n)pass;"".join(ans)is a fourthO(n)pass -4ncombined, wheren = len(s). - Building
bucketsfrom the shifts is a separateO(m)pass, wherem = len(shifts). alphabet_mapis built once from the 26-character alphabet,O(26), independent of bothnandm.- Space
- O(2n + 26)
bucketsandansare eachO(n).alphabet_mapholds exactly the 26 letters of the alphabet,O(26), independent ofn.
2237. Count Positions on Street With Required Brightness
Same fixed-size difference array as [[370. Range Addition]]: each light illuminates [center - range, center + range], clipped to the street's own bounds [0, n-1] first, and that clipped interval becomes a +1 at start and a -1 at end+1 in buckets. A single left-to-right scan then accumulates active into the actual brightness at every position, and a position counts the moment its brightness meets or beats requirement[point].
- Time
- O(3n + m)
- Allocating
bucketsis oneO(n)pass; slicingbuckets[:-2]copies anotherO(n); the accumulating scan over that slice is a thirdO(n)pass -3ncombined. - Building
bucketsfrom the lights is a separateO(m)pass, wherem = len(lights). - Space
- O(n)
bucketsis allocated ton + 2elements, independent ofm.
2779. Maximum Beauty of an Array After Applying Operation
Every i in nums can be replaced by anything in [i-k, i+k], so streamEvents turns each element into a +1 event at i-k and a -1 event at i+k+1 - the interval of values it could become, made half-open so the endpoint itself still counts. Sweeping the sorted events, active is the number of elements whose ranges cover the current point at once, and the highest active ever gets is the largest group that can all be turned into the same value.
- Time
- O(2n + n log n)
streamEventsbuilds2nevents from thenelements ofnums, then sorts them -O(n log n).- The sweep loop then walks all
2nevents once - a second linear pass overn:2n + n log n. - Space
- O(sort + n)
streamEventsbuilds alineof2nevents before sorting it -O(n)- on top of the sort's own working memory.
Weighted concurrent sum
Same +1/-1 sweep, but each event carries a weight instead of a flat unit, so the running total is a sum rather than a count - and every distinct stretch between consecutive event points, not just the peak, is reported alongside whatever that sum was during it.
1943. Describe the Painting
streamEvents turns every [start, end, weight] segment into a +weight event at its start and a -weight event at its end, sorted into one timeline - the running total is now a color sum rather than a plain overlap count. Sweeping that timeline: whenever the point moves (point != prev) and the sum so far (active) is non-zero, [prev, point, active] is emitted as one mixed segment before prev advances to point and active picks up the new event's weight.
- Time
- O(2n + n log n)
streamEventsbuilds2nevents from thensegments, then sorts them -O(n log n).- The sweep loop then walks all
2nevents once - a second linear pass overn:2n + n log n. - Space
- O(sort + n)
streamEventsbuilds alineof2nevents before sorting it -O(n)- on top of the sort's own working memory.
Concurrent count at query points
Same +1/-1 sweep as above, but instead of the single overall peak, the running count is needed at several specific instants - one per query point. Sort the queries too, and drain every query that falls before the current event point as the sweep passes it, recording whatever active is at that moment.
2251. Number of Flowers in Full Bloom
Same +1/-1 sweep as [[253. Meeting Rooms II]], but instead of tracking a single peak, the running active count is needed at several specific instants - each person's arrival time. Turn every flower into (start, +1) and (end+1, -1) (the +1 on the end makes the interval inclusive), sort those 2n events, and sort people too so both walks move only forward. Before each event's point advances active, drain every still-pending person (prev <= people_sorted[finder] < point) and record the current active as their answer - that person arrived before this event changed anything, so the count is still accurate for them. finder never resets, so each person is visited exactly once across the whole sweep.
- Time
- O(2n + 2m + n log n + m log m)
- Building the
2nevents is oneO(n)pass; sweeping all of them is anotherO(n)pass -2ncombined. - Every person is drained by the inner
whileexactly once across the whole sweep, and the final list comprehension is another single pass overpeople-2mcombined. - Sorting the
2nevents costsO(n log n), and sortingpeoplecostsO(m log m). - Space
- O(sort + n + m)
- The events list built inside
streamEventsholds2ntuples,O(n). people_sortedandansare eachO(m).- Sorting algorithms are typically
O(log n)space (in-place, recursion-stack only), but Python'slist.sort()is Timsort, which allocates up toO(n)auxiliary space in the worst case - that's whatsortstands for here.
Two sorted lists
The one group that abandons the sweep. When the input arrives as two already-sorted lists there is nothing to sort and nothing to merge - you walk both with two pointers, emit the shared stretch of the current pair if there is one, and advance whichever interval ends first, because it can never intersect anything later.
986. Interval List Intersections
Both lists are already sorted and disjoint within themselves, so a single two-pointer sweep is enough - no sorting needed. At each step, look at a = firstList[i] and b = secondList[j]: if they overlap, their intersection is [max(a[0], b[0]), min(a[1], b[1])]. Whichever of the two intervals ends first can never overlap anything further in the other list (everything past it starts later), so its pointer is the one that advances - i if a ends first, otherwise j.
- Time
- O(n + m)
- Each step advances
iorjby one, and the loop stops once either pointer runs out - at mostn + mtotal advances across both lists. - Space
- O(k)
commonholds thekintersections found; no extra structure scales with the input beyond the output itself.