Overlapping Intervals

Problem: Given a list of intervals, merge all overlapping ones and return the non-overlapping result. Touching intervals like [1,4] and [4,5] count as overlapping.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ intervals.length ≤ 10⁴ · intervals[i].length == 2 · 0 ≤ starti ≤ endi ≤ 10⁴

From brute force to the pattern: Comparing every pair and merging repeatedly until nothing changes is O(n²) or worse. Sorting by start puts every possible overlap next to each other, so one sweep merges everything: O(n log n).

Spot it: The word "merge" plus a list of ranges: this is the canonical problem of the pattern.

Key insight: Once sorted by start, an interval can only overlap the last merged block. Either stretch that block's end with max, or start a new block. (The first visualization above runs exactly this.)

Approach:

1. Sort the intervals by start.
2. Put a copy of the first interval into merged.
3. For each next [start, end]: if start ≤ last_block[1], they overlap, so set last_block[1] = max(last_block[1], end).
4. Otherwise there's a gap: append [start, end] as a new block.
5. Return merged.

from typing import List


def get_start(interval):
    # Sort key helper: the start of an interval is its first number.
    return interval[0]


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # Step 1: sort by start so overlapping intervals end up side by side.
        intervals.sort(key=get_start)

        # Step 2: the first interval opens the first merged block.
        # We build a NEW list [start, end] so that stretching the block
        # later never changes the caller's input list.
        first_start = intervals[0][0]
        first_end = intervals[0][1]
        merged = []
        merged.append([first_start, first_end])

        # Step 3: visit every other interval from left to right.
        for i in range(1, len(intervals)):
            start = intervals[i][0]
            end = intervals[i][1]
            last_block = merged[len(merged) - 1]    # block being built
            if start <= last_block[1]:
                # Overlap (touching counts): stretch the block's end.
                # max: [1,10] followed by [2,3] must stay [1,10].
                last_block[1] = max(last_block[1], end)
            else:
                # Gap: the old block is final; this interval opens a new one.
                merged.append([start, end])
        return merged

What the code is doing, line by line:

1. get_start returns an interval's first number. intervals.sort(key=get_start) uses it to sort by start time.
2. First block: we read the first interval's two ends and append a brand-new list [first_start, first_end] to merged. Making a new list (instead of reusing intervals[0]) means later stretching can't accidentally change the input.
3. The for loop starts at index 1 and reads each interval's start and end.
4. last_block is the last item of merged (index len(merged) - 1). Since the input is sorted, this is the only block the current interval could overlap.
5. If start <= last_block[1], the interval begins before the block ends (or exactly at its end), so they overlap. We stretch the block's end with max, which also handles an interval sitting fully inside the block.
6. Otherwise there is a gap, so we append [start, end] as a new block.
7. return merged.

Dry run on the example intervals = [[1,3],[2,6],[8,10],[15,18]] (already sorted; merged starts as [[1,3]]):

Answer: [[1,6],[8,10],[15,18]].

Edge cases to test:

• Touching intervals, e.g. [1, 4] and [4, 5] → [1, 5].
• One interval inside another, e.g. [1, 10] and [2, 3].
• Unsorted input.

Complexity: O(n log n) time, O(n) output space.

Problem: The intervals are already sorted and don't overlap. Insert newInterval, merging wherever needed, and return the result.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 0 ≤ intervals.length ≤ 10⁴ · intervals[i].length == 2 · 0 ≤ starti ≤ endi ≤ 10⁵ · intervals is sorted by starti in ascending order. · newInterval.length == 2 · 0 ≤ start ≤ end ≤ 10⁵

From brute force to the pattern: Appending newInterval and re-running Merge Intervals is O(n log n). Because the input is already sorted, one linear pass with three phases is O(n).

Spot it: It's sorted already, so don't re-sort. A single pass splits the list into three zones.

Key insight: (1) Copy intervals that end before the new one starts. (2) Absorb every interval that starts before the new one ends, growing it with min/max. (3) Copy the rest.

Approach:

1. Walk with an index i. While intervals[i] ends before the new interval starts, copy it to the output (zone 1).
2. While intervals[i] starts at or before the new interval's end, absorb it: new_start = min(new_start, …), new_end = max(new_end, …) (zone 2).
3. Append the grown [new_start, new_end].
4. Copy every remaining interval (zone 3).

from typing import List


class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        i = 0
        count = len(intervals)
        # The new interval may grow as it swallows neighbours, so keep its
        # two ends in variables we can update.
        new_start = newInterval[0]
        new_end = newInterval[1]

        # Zone 1: intervals that END before the new one STARTS.
        # They are entirely to the left, so copy them unchanged.
        while i < count and intervals[i][1] < new_start:
            result.append(intervals[i])
            i = i + 1

        # Zone 2: intervals that START at or before the new one ENDS.
        # They overlap, so absorb each one by widening the new interval.
        while i < count and intervals[i][0] <= new_end:
            new_start = min(new_start, intervals[i][0])
            new_end = max(new_end, intervals[i][1])
            i = i + 1

        # The (possibly grown) new interval goes in right here.
        result.append([new_start, new_end])

        # Zone 3: everything left is entirely to the right: copy it.
        while i < count:
            result.append(intervals[i])
            i = i + 1
        return result

What the code is doing, line by line:

1. Setup: result is the output list, i walks through intervals, and count is how many there are. new_start and new_end hold the new interval's ends, because they may grow.
2. Zone 1 loop: while the current interval ends before new_start, it can't touch the new one, so copy it and move on.
3. Zone 2 loop: while the current interval starts at or before new_end, it overlaps. Widen the new interval with min on the start and max on the end, then move on. The interval itself is not copied; it has been swallowed.
4. result.append([new_start, new_end]) places the merged new interval exactly between the left zone and the right zone.
5. Zone 3 loop: every remaining interval starts after new_end, so copy them all.

Dry run on the example intervals = [[1,3],[6,9]], newInterval = [2,5]:

Answer: [[1,5],[6,9]].

Edge cases to test:

• An empty list → [newInterval].
• newInterval before all or after all intervals.
• newInterval covering every interval.

Complexity: O(n) time, O(n) output space.

Problem: Return the minimum number of intervals to remove so the rest don't overlap. Touching ([1,2], [2,3]) is allowed.

Solve it on LeetCode ↗

Constraints: 1 ≤ intervals.length ≤ 10⁵ · intervals[i].length == 2 · -5 * 10⁴ ≤ starti < endi ≤ 5 * 10⁴

From brute force to the pattern: Trying every subset to remove is exponential; DP over sorted intervals is O(n²). Greedy by earliest end time is optimal (it leaves the most room for the rest): O(n log n).

Spot it: "remove the fewest" = "keep the most". That's the classic activity-selection greedy: sort by end.

Key insight: Always keep the interval that finishes earliest, because it leaves the most room for everything after it. Any later interval that starts before the kept end has to go.

Approach:

1. Sort by end time.
2. Track last_kept_end = end of the last interval you kept (start at −∞).
3. For each [start, end]: if start ≥ last_kept_end, keep it and set last_kept_end = end. Otherwise remove it (removed = removed + 1). It conflicts, and since it ends later than the one you kept, dropping it is never worse.
4. Return removed.

from typing import List


def get_end(interval):
    # Sort key helper: the end of an interval is its second number.
    return interval[1]


class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # Greedy: sort by END so the interval that finishes first comes first.
        intervals.sort(key=get_end)
        removed = 0
        last_kept_end = float("-inf")       # nothing kept yet

        for i in range(len(intervals)):
            start = intervals[i][0]
            end = intervals[i][1]
            if start >= last_kept_end:
                # Fits after the last kept interval (touching is allowed): keep it.
                last_kept_end = end
            else:
                # Starts before the kept one ends: conflict. It also ends
                # later (we sorted by end), so removing it is never worse.
                removed = removed + 1
        return removed

What the code is doing, line by line:

1. get_end returns an interval's end. Using it as the sort key orders intervals by finishing time.
2. removed = 0 counts deletions. last_kept_end = -inf means "nothing kept yet", so the first interval is always kept.
3. In the loop we read start and end of the current interval.
4. If start >= last_kept_end, it begins after (or exactly when) the last kept one ends, so we keep it and remember its end.
5. Otherwise it overlaps the last kept interval. Because we sorted by end, it finishes no earlier than the kept one, so it is the better one to throw away: removed = removed + 1.
6. return removed.

Dry run on the example intervals = [[1,2],[2,3],[3,4],[1,3]] (sorted by end: [[1,2],[2,3],[1,3],[3,4]]):

Answer: 1.

Edge cases to test:

• Touching intervals like [1, 2] and [2, 3] do not overlap.
• Identical intervals.
• Nothing overlaps → 0.

Complexity: O(n log n) time, O(1) extra space.

Problem: Given meeting times [start, end), return the minimum number of conference rooms needed.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ intervals.length ≤ 10⁴ · 0 ≤ startᵢ < endᵢ ≤ 10⁶

From brute force to the pattern: Checking, for every meeting, how many others overlap it is O(n²). Sorting by start and keeping room end times in a min-heap gives the maximum overlap in O(n log n) (or sort starts and ends separately and sweep).

Spot it: "minimum rooms" = the maximum number of meetings happening at the same moment.

Key insight: Sort by start. Keep a min-heap of end times for the rooms in use. If the earliest-ending room is free by the time the next meeting starts (ends[0] ≤ s), reuse it. Otherwise open a new room. The heap's final size is the answer. (See the second visualization above.)

Approach:

1. Sort meetings by start.
2. Keep a min-heap ends with the end time of every room in use.
3. For each meeting [s, e): if ends[0] ≤ s, the earliest-finishing room is free, so replace its end with e.
4. Otherwise push e. A new room opens.
5. The heap's size at the end is the number of rooms needed.

import heapq
from typing import List


def get_start(interval):
    # Sort key helper: the start of an interval is its first number.
    return interval[0]


class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        # heapq keeps a plain list arranged as a "min-heap":
        #   heapq.heappush(heap, x)  adds x
        #   heapq.heappop(heap)      removes and returns the smallest item
        #   heap[0]                  is always the smallest item
        intervals.sort(key=get_start)       # handle meetings in start order
        room_ends = []                      # end time of every busy room

        for i in range(len(intervals)):
            start = intervals[i][0]
            end = intervals[i][1]
            if len(room_ends) > 0 and room_ends[0] <= start:
                # The room that frees up first is already free: reuse it.
                # Take out its old end time, put in this meeting's end time.
                heapq.heappop(room_ends)
                heapq.heappush(room_ends, end)
            else:
                # Every room is busy right now: open a new room.
                heapq.heappush(room_ends, end)

        # One heap entry per room ever opened.
        return len(room_ends)

What the code is doing, line by line:

1. The heap comment explains the three heap operations we use. The key fact: room_ends[0] is always the earliest end time, which is the room that frees up first.
2. intervals.sort(key=get_start) processes meetings in the order they begin.
3. room_ends = []: no rooms are open yet.
4. In the loop we read the meeting's start and end.
5. If a room is free (the earliest end is <= start; meetings are half-open, so ending at 10 and starting at 10 is fine), we pop that old end time and push the new one. The room count stays the same. (The one-call shortcut for this is heapq.heapreplace.)
6. Otherwise every room is still in use, so we push the end time, which opens a new room.
7. return len(room_ends): rooms are reused but never removed, so the heap size equals the number of rooms needed.

Dry run on the example intervals = [[0,30],[5,10],[15,20]]:

Answer: len(room_ends) = 2.

Edge cases to test:

• A meeting ending exactly when another starts can reuse the room.
• All meetings overlap → n rooms.
• A single meeting → 1.

Complexity: O(n log n) time, O(n) space.

Problem: Each employee has a sorted list of non-overlapping working intervals. Return the finite intervals when all employees are free, in sorted order.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ schedule.length, schedule[i].length ≤ 50 · 0 ≤ schedule[i].start < schedule[i].end ≤ 10⁸

From brute force to the pattern: Marking every time unit as busy or free is impossible for times up to 10⁸. Sorting all intervals and sweeping once finds every gap in O(N log N); a heap over the employees' sorted lists makes it O(N log k).

Spot it: "Common free time" is the gaps between the merged busy blocks of everyone combined.

Key insight: Flatten all intervals, sort by start, and sweep while tracking the furthest end seen so far. Whenever the next start is strictly greater than end, the stretch [end, start] is a moment nobody is working. (A k-way heap merge gives O(n log k); plain sorting is simpler.)

Approach:

1. Flatten every employee's intervals into one list and sort it by start.
2. Set end = the first interval's end. This is the end of the current merged busy block.
3. For each next interval: if start > end, record the free gap [end, start].
4. Then extend the busy block: end = max(end, interval.end).
5. Return the recorded gaps.

"""
class Interval:
    def __init__(self, start=None, end=None):
        self.start = start
        self.end = end
"""


def get_interval_start(interval):
    # Sort key helper for Interval objects: use the .start field.
    return interval.start


class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        # Step 1: flatten. Put every employee's intervals into one list.
        all_intervals = []
        for employee_index in range(len(schedule)):
            employee_intervals = schedule[employee_index]
            for j in range(len(employee_intervals)):
                all_intervals.append(employee_intervals[j])

        # Step 2: sort that list by start time.
        all_intervals.sort(key=get_interval_start)

        # Step 3: sweep, remembering where the current busy block ends.
        free = []
        busy_until = all_intervals[0].end
        for i in range(1, len(all_intervals)):
            current = all_intervals[i]
            if current.start > busy_until:
                # Nobody is working between busy_until and current.start.
                free.append(Interval(busy_until, current.start))
            # Extend the busy block if this interval goes further right.
            busy_until = max(busy_until, current.end)
        return free

What the code is doing, line by line:

1. The docstring shows LeetCode's Interval class: each interval has .start and .end.
2. get_interval_start returns interval.start; we pass it to sort as the key.
3. Step 1 (two nested loops): the outer loop visits each employee, the inner loop visits that employee's intervals, and every interval is appended to all_intervals. Who worked doesn't matter, only when.
4. Step 2: sort everything by start time, exactly like Merge Intervals.
5. Step 3: busy_until is the end of the busy block we are building, starting with the first interval's end.
6. For each later interval: if it starts strictly after busy_until, there is a gap where nobody works, so we record Interval(busy_until, current.start). Either way we then stretch busy_until with max, just like merging.

Dry run on the example [[[1,3],[6,7]], [[2,4]], [[2,5],[9,12]]] (flattened and sorted: [1,3], [2,4], [2,5], [6,7], [9,12]; start with busy_until = 3):

Example: [[[1,3],[6,7]], [[2,4]], [[2,5],[9,12]]] → busy blocks [1,5], [6,7], [9,12] → free [[5,6],[7,9]].

Edge cases to test:

• Overlapping intervals from different employees.
• Intervals that touch (no gap between them).
• No common free time → [].

Complexity: O(n log n) time for n total intervals, O(n) space.

Problem: Given meeting times [start, end), can one person attend all of them?

Solve it on LeetCode ↗ (Premium)

Constraints: 0 ≤ intervals.length ≤ 10⁴ · 0 ≤ startᵢ < endᵢ ≤ 10⁶

From brute force to the pattern: Comparing every pair of meetings is O(n²). Sorting by start means only adjacent meetings can overlap, so one pass checks it: O(n log n).

Spot it: Possible exactly when no two meetings overlap. Sort by start, and any overlap has to show up between neighbors.

Approach:

1. Sort by start.
2. For each meeting after the first: if it starts before the previous one ends, return False.
3. Return True.

from typing import List


class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        # Sort by start time. Python sorts lists of lists by their first
        # number (then by the second number when the first ones tie).
        intervals.sort()

        # Compare every meeting with the one right before it.
        for i in range(1, len(intervals)):
            current_start = intervals[i][0]
            previous_end = intervals[i - 1][1]
            if current_start < previous_end:
                # It starts before the previous meeting ends: a clash.
                return False
        # No neighbours clash, so no meetings clash at all.
        return True

What the code is doing, line by line:

1. intervals.sort() sorts the meetings. A list of lists is sorted by first number, so this is "sort by start time".
2. The for loop starts at index 1, because meeting 0 has nobody before it to clash with.
3. current_start and previous_end name the two numbers we need to compare.
4. If current_start < previous_end, this meeting begins while the previous one is still going, so one person can't attend both: return False. (Equal is fine: [1,5) then [5,8) do not clash.)
5. return True: after sorting, any clash would have to be between neighbours, and we found none.

Dry run on the example intervals = [[0,30],[5,10],[15,20]] (already sorted):

Answer: False (the meeting at 5 starts while [0,30) is still running).

Edge cases to test:

• No meetings → True.
• Back-to-back meetings, e.g. [1, 2] and [2, 3] → True.
• Unsorted input.

Complexity: O(n log n) time, O(1) extra space.

Problem: Two lists of closed intervals are each sorted and internally disjoint. Return their intersection: every range that's covered by both lists.

Solve it on LeetCode ↗

Constraints: 0 ≤ firstList.length, secondList.length ≤ 1000 · firstList.length + secondList.length ≥ 1 · 0 ≤ starti < endi ≤ 10⁹ · endi < starti+1 · 0 ≤ startj < endj ≤ 10⁹ · endj < startj+1

From brute force to the pattern: Comparing every interval of A with every interval of B is O(m · n). Two pointers walk both sorted lists once, because the interval that ends first can't overlap anything later: O(m + n).

Spot it: Both lists are already sorted, so walk them together with Two Pointers. The overlap of two intervals is [max(starts), min(ends)] when that's non-empty.

Approach:

1. Start both pointers at 0: i = 0 (into firstList) and j = 0 (into secondList).
2. Compute overlap_start = max(firstList[i][0], secondList[j][0]) and overlap_end = min(firstList[i][1], secondList[j][1]). If overlap_start ≤ overlap_end, record [overlap_start, overlap_end].
3. Advance the pointer whose interval ends first. It can't overlap anything further in the other list.
4. Stop when either list runs out.

from typing import List


class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        i = 0                               # position in firstList
        j = 0                               # position in secondList
        result = []
        while i < len(firstList) and j < len(secondList):
            # The overlap starts at the LATER of the two starts ...
            overlap_start = max(firstList[i][0], secondList[j][0])
            # ... and ends at the EARLIER of the two ends.
            overlap_end = min(firstList[i][1], secondList[j][1])
            if overlap_start <= overlap_end:
                # Non-empty overlap: record it.
                result.append([overlap_start, overlap_end])
            # Whichever interval ends first cannot overlap anything else
            # in the other list, so move past it.
            if firstList[i][1] < secondList[j][1]:
                i = i + 1
            else:
                j = j + 1
        return result

What the code is doing, line by line:

1. i = 0, j = 0: one pointer per list, each on its first interval. result collects the overlaps.
2. The while loop runs as long as both pointers are still inside their lists. Once one list is used up, nothing else can overlap.
3. overlap_start is the later of the two starts and overlap_end is the earlier of the two ends. That is exactly the shared part of two intervals.
4. If overlap_start <= overlap_end the shared part is non-empty (a single point like [5,5] counts, since the intervals are closed), so we append it.
5. Moving a pointer: the interval that ends first is finished, because everything later in the other list starts even later. We step past it with i = i + 1 or j = j + 1.

Dry run on the example firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]:

Then i = 4 runs off the end. Result: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].

Edge cases to test:

• One list empty → [].
• Single-point overlaps, e.g. [5, 5].
• One interval covering many in the other list.

Complexity: O(m + n) time, O(1) extra space (besides the output).

Problem: Each balloon spans [x_start, x_end] on the x-axis. A vertical arrow shot at x bursts every balloon with start ≤ x ≤ end. What's the fewest arrows that burst them all?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ points.length ≤ 10⁵ · points[i].length == 2 · -2³¹ ≤ xstart < xend ≤ 2³¹ - 1

From brute force to the pattern: Trying arrow positions or subsets is far too slow. Greedy by earliest end is optimal: shooting at the smallest end bursts the most balloons that must be burst anyway. O(n log n).

Spot it: Same greedy as 435: sort by end. Shooting at the earliest end bursts the most balloons that are still standing. Touching counts as overlapping here.

Approach:

1. Sort balloons by end.
2. Keep arrow_x = position of the last arrow (start at −∞).
3. For each balloon: if start > arrow_x, the last arrow misses it, so shoot a new arrow at its end.
4. Return the arrow count.

from typing import List


def get_balloon_end(balloon):
    # Sort key helper: a balloon [x_start, x_end] ends at its second number.
    return balloon[1]


class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # Greedy: handle the balloon that ends first, first.
        points.sort(key=get_balloon_end)
        arrows = 0
        arrow_x = float("-inf")             # no arrow shot yet

        for i in range(len(points)):
            balloon_start = points[i][0]
            balloon_end = points[i][1]
            if balloon_start > arrow_x:
                # The last arrow is left of this balloon: it misses.
                # Shoot a new arrow at this balloon's END, as far right
                # as possible, so it also hits as many later balloons
                # as possible.
                arrows = arrows + 1
                arrow_x = balloon_end
            # Otherwise start <= arrow_x <= end: already burst.
        return arrows

What the code is doing, line by line:

1. get_balloon_end is a tiny helper that returns a balloon's end. Passing it as key= makes sort order balloons by end.
2. arrows = 0, arrow_x = -inf: no arrows yet, and the "last arrow" is infinitely far left so the first balloon always needs a new one.
3. In the loop we read the balloon's start and end by index.
4. If balloon_start > arrow_x, the last arrow passes to the left of this balloon. We shoot a new arrow at balloon_end; that is the rightmost spot that still hits this balloon, so it has the best chance of hitting later ones too.
5. Otherwise the balloon contains arrow_x (its end is at least arrow_x because we sorted by end), so it is already burst and we do nothing.

Dry run on the example points = [[10,16],[2,8],[1,6],[7,12]] (sorted by end: [[1,6],[2,8],[7,12],[10,16]]):

Answer: 2.

Edge cases to test:

• Touching balloons like [1, 2] and [2, 3] share one arrow.
• All balloons overlap → 1.
• Huge coordinates (sorting by end avoids overflow issues in other languages).

Complexity: O(n log n) time, O(1) extra space.

Problem: A car with capacity seats drives east. Trip [num, from, to] picks up num passengers at from and drops them off at to. Can every trip be served?

Solve it on LeetCode ↗

Constraints: 1 ≤ trips.length ≤ 1000 · trips[i].length == 3 · 1 ≤ numPassengersi ≤ 100 · 0 ≤ fromi < toi ≤ 1000 · 1 ≤ capacity ≤ 10⁵

From brute force to the pattern: Simulating each trip over every kilometre is O(n · distance). A difference array (or sorted events) adds each trip in O(1) and checks capacity in one sweep: O(n + max location).

Spot it: This is "how much overlaps at the busiest point", weighted by passengers. Use a sweep line: +num at pickup, −num at drop-off.

Approach:

1. Create events (from, +num) and (to, −num).
2. Sort them. At the same location, the negative drop-off sorts first, so seats free up before new riders board.
3. Sweep and keep a running load. If it ever exceeds capacity, return False.
4. Return True.

from typing import List


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # Turn every trip into two events (location, change in riders).
        events = []
        for i in range(len(trips)):
            passengers = trips[i][0]
            pickup = trips[i][1]
            dropoff = trips[i][2]
            events.append((pickup, passengers))      # riders get in
            events.append((dropoff, -passengers))    # riders get out

        # Sort by location. Tuples compare by the first item, then the
        # second, so at the same spot the negative drop-off comes first:
        # seats are freed before new riders board.
        events.sort()

        # Drive east, keeping a running count of riders in the car.
        load = 0
        for i in range(len(events)):
            change = events[i][1]
            load = load + change
            if load > capacity:
                return False                # too many riders at once
        return True

What the code is doing, line by line:

1. Building events: for each trip we read passengers, pickup and dropoff by index, then add two tuples: (pickup, +passengers) and (dropoff, -passengers).
2. events.sort() orders events by location. When two events share a location, the smaller second value wins, so a drop-off (negative) is processed before a pickup (positive). That frees seats first.
3. load = 0: the car starts empty.
4. The sweep loop reads each event's change, adds it to load, and returns False the moment load goes over capacity.
5. return True: we got through every event without overflowing.

Dry run on the example trips = [[2,1,5],[3,3,7]], capacity = 4:

Sorted events were [(1,2), (3,3), (5,-2), (7,-3)]; the last two are never reached. Answer: False.

Edge cases to test:

• A drop-off and a pickup at the same location: drop off first.
• A single trip over capacity → False.
• Trips that don't overlap at all.

Complexity: O(n log n) time, O(n) space. (A difference array over locations ≤ 1000 gives O(n + 1000).)

Problem: Implement book(start, end) for half-open events [start, end). Accept and store the booking only if it doesn't overlap any existing one.

Solve it on LeetCode ↗

Constraints: 0 ≤ start < end ≤ 10⁹ · At most 1000 calls will be made to book.

From brute force to the pattern: Checking all existing bookings is O(n) per call, which is fine for these limits. A sorted list with binary search (or a balanced BST) makes it O(log n) per call.

Spot it: Intervals arrive one at a time (online), so you can't sort once. Keep the bookings sorted, and a new booking only needs to be checked against its two neighbors. Find them with binary search.

Approach:

1. Keep two parallel sorted lists: starts and ends.
2. Binary-search starts for the first position whose start is greater than the new start. That position position is where the new booking would go (this is what bisect.bisect_right computes; here it is written out by hand).
3. Conflict with the left neighbor if ends[position−1] > start. Conflict with the right neighbor if starts[position] < end.
4. If there's no conflict, insert at position in both lists and return True.

class MyCalendar:
    def __init__(self):
        self.starts = []                    # booking starts, kept sorted
        self.ends = []                      # ends, same order as starts

    def book(self, start: int, end: int) -> bool:
        # Binary search: find the first position whose start is
        # GREATER than the new start. The new booking would go there,
        # so its neighbours are at position - 1 (left) and position (right).
        low = 0
        high = len(self.starts)
        while low < high:
            middle = (low + high) // 2
            if self.starts[middle] <= start:
                low = middle + 1            # answer is to the right of middle
            else:
                high = middle               # middle might be the answer
        position = low

        # Left neighbour: does it end after we start? Then it overlaps.
        if position > 0 and self.ends[position - 1] > start:
            return False
        # Right neighbour: does it start before we end? Then it overlaps.
        if position < len(self.starts) and self.starts[position] < end:
            return False

        # No clash: insert into both lists at the same position.
        # list.insert is O(n), which is fine for 1000 calls.
        self.starts.insert(position, start)
        self.ends.insert(position, end)
        return True

What the code is doing, line by line:

1. __init__ creates two empty lists. self.starts[k] and self.ends[k] together describe booking number k, and the bookings are kept sorted by start.
2. The binary search keeps a window [low, high). If the middle start is <= start, the answer must be to its right, so low = middle + 1. Otherwise the middle could be the answer, so high = middle. When low == high, that is position.
3. Left neighbour check: the booking just before position starts at or before us. If it ends after we start (ends[position - 1] > start), the two overlap, so we refuse.
4. Right neighbour check: the booking at position starts after us. If it starts before we end (starts[position] < end), they overlap, so we refuse.
5. Insert: no clash with either neighbour means no clash at all (the list is sorted and non-overlapping), so we insert into both lists at position and return True.

Dry run on the example book(10,20), book(15,25), book(20,30):

Edge cases to test:

• Back-to-back bookings, e.g. [10, 20) then [20, 30) → both allowed.
• A booking inside an existing one.
• A booking covering an existing one.

Complexity: O(log n) search + O(n) insert per booking, O(n) space. (A balanced BST / SortedList makes inserts O(log n).)

Problem: For each query point q, return the size (right − left + 1) of the smallest interval that contains q, or -1 if no interval does.

Solve it on LeetCode ↗

Constraints: 1 ≤ intervals.length ≤ 10⁵ · 1 ≤ queries.length ≤ 10⁵ · intervals[i].length == 2 · 1 ≤ lefti ≤ righti ≤ 10⁷ · 1 ≤ queries[j] ≤ 10⁷

From brute force to the pattern: For every query, scanning all intervals is O(n · q). Sorting both and using a min-heap of (size, end) answers each query in O(log n): O((n + q) log n).

Spot it: Answer the queries offline in sorted order. As q grows, intervals "start" (left ≤ q) and "expire" (right < q), which is a sweep. "Smallest live interval" → min-heap by size.

Approach:

1. Sort intervals by left end. Process the distinct queries in increasing order.
2. For each q, push (size, right) for every interval with left ≤ q.
3. Pop from the heap while its top has right < q. It has expired, and it will stay expired for every bigger query too.
4. The heap's top size (or -1) is the answer for q. Map answers back to the original query order.

import heapq
from typing import List


class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        # heapq keeps a plain list arranged as a "min-heap":
        #   heapq.heappush(heap, item) adds an item
        #   heapq.heappop(heap)        removes and returns the smallest item
        #   heap[0]                    is always the smallest item
        # Our items are tuples (size, right). Tuples compare by their
        # first value, so heap[0] is always the SMALLEST interval.

        # Sort intervals by their left end.
        intervals.sort()

        # Build the distinct query values in increasing order.
        sorted_queries = []
        for i in range(len(queries)):
            sorted_queries.append(queries[i])
        sorted_queries.sort()
        unique_queries = []
        for i in range(len(sorted_queries)):
            value = sorted_queries[i]
            if len(unique_queries) == 0 or unique_queries[len(unique_queries) - 1] != value:
                unique_queries.append(value)

        heap = []                           # (size, right) of started intervals
        answer_for = {}                     # query value -> answer
        next_interval = 0                   # first interval not yet pushed

        for q_index in range(len(unique_queries)):
            query = unique_queries[q_index]

            # Push every interval that has started (left <= query).
            while next_interval < len(intervals) and intervals[next_interval][0] <= query:
                left = intervals[next_interval][0]
                right = intervals[next_interval][1]
                size = right - left + 1
                heapq.heappush(heap, (size, right))
                next_interval = next_interval + 1

            # Throw away smallest intervals that ended before query.
            # Later queries are even bigger, so they stay useless.
            while len(heap) > 0 and heap[0][1] < query:
                heapq.heappop(heap)

            # The top of the heap is now the smallest interval holding query.
            if len(heap) > 0:
                answer_for[query] = heap[0][0]
            else:
                answer_for[query] = -1

        # Put the answers back in the ORIGINAL query order.
        result = []
        for i in range(len(queries)):
            result.append(answer_for[queries[i]])
        return result

What the code is doing, line by line:

1. The heap comment explains heappush, heappop and heap[0]. Each heap item is a tuple (size, right), and tuples compare by their first value, so the smallest interval is always on top.
2. intervals.sort() puts intervals in order of their left end, so we can add them one by one as the query grows.
3. Distinct sorted queries: we copy queries, sort the copy, then keep a value only if it differs from the last one we kept. That way each query value is answered once, from smallest to largest.
4. heap, answer_for, next_interval: the heap of started intervals, a dictionary from query value to its answer, and the index of the first interval not yet pushed.
5. First inner while: push every interval whose left end is <= query, with its size right - left + 1. Because queries only grow, an interval pushed once never has to be pushed again.
6. Second inner while: while the smallest interval ends before the query (right < query), it cannot contain this query or any later one, so pop it for good.
7. The if/else stores the top size as the answer, or -1 when the heap is empty.
8. Last loop: walk the original queries list and look each one up in answer_for, so the answers come back in the order they were asked.

Dry run on the example intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]:

Result in original order: [3, 3, 1, 4].

Edge cases to test:

• A query no interval contains → −1.
• Duplicate queries.
• Intervals of length 1 (start == end).

Complexity: O(n log n + q log q) time, O(n + q) space.

Problem: Buildings are [left, right, height] rectangles on the ground. Return the skyline's "key points": [x, height] wherever the outline's height changes.

Solve it on LeetCode ↗

Constraints: 1 ≤ buildings.length ≤ 10⁴ · 0 ≤ lefti < righti ≤ 2³¹ - 1 · 1 ≤ heighti ≤ 2³¹ - 1 · buildings is sorted by lefti in non-decreasing order.

From brute force to the pattern: Checking the height at every x coordinate is far too slow for large coordinates. A sweep over sorted edges with a max-heap (lazy removal) gives O(n log n).

Spot it: Sweep left to right over building edges. At each x, the skyline's height is the tallest building that is currently "live", so use a max-heap of live heights. When that maximum changes, record a key point.

Approach:

1. Make events: (left, −height, right) for starts and (right, 0, 0) for ends. Sorting puts taller starts first at the same x.
2. Keep a max-heap live of (−height, right), seeded with the ground (0, ∞).
3. At each event, push the building if it's a start. Then lazily pop tops whose right ≤ x.
4. If the current max height differs from the last key point's height, append [x, height].

import heapq
from typing import List


class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        # heapq is a MIN-heap: heapq.heappop(heap) removes the smallest
        # item and heap[0] is the smallest. We need the TALLEST building,
        # so we store heights as NEGATIVE numbers: the tallest building
        # then has the smallest (most negative) value and sits at heap[0].
        # This is the "negative-number max-heap trick".

        # Make two events per building.
        events = []
        for i in range(len(buildings)):
            left = buildings[i][0]
            right = buildings[i][1]
            height = buildings[i][2]
            # Start event: (x, -height, right). At the same x, a taller
            # building has a smaller -height, so it is handled first.
            events.append((left, -height, right))
            # End event: (x, 0, 0). It adds nothing; it just makes us
            # clean up buildings that have ended at this x.
            events.append((right, 0, 0))
        events.sort()

        result = []
        # Live buildings as (-height, right). The ground (height 0)
        # never ends, so the heap is never empty.
        live = []
        heapq.heappush(live, (0, float("inf")))

        for i in range(len(events)):
            event_x = events[i][0]
            negative_height = events[i][1]
            right = events[i][2]

            if negative_height != 0:
                # A building starts here: it becomes live.
                heapq.heappush(live, (negative_height, right))

            # Remove tallest buildings that already ended (right <= event_x).
            # We only need to clean the top, because only the top
            # decides the current height ("lazy deletion").
            while live[0][1] <= event_x:
                heapq.heappop(live)

            # Current skyline height = tallest live building.
            current_height = -live[0][0]

            # Record a key point only if the height changed.
            if len(result) == 0:
                result.append([event_x, current_height])
            elif result[len(result) - 1][1] != current_height:
                result.append([event_x, current_height])
        return result

What the code is doing, line by line:

1. The comment at the top explains the max-heap trick. Python's heapq only gives you the smallest item. Storing -height makes the tallest building the smallest number, so it sits at live[0].
2. Building the events: for each building we read left, right and height by index. A start event is (left, -height, right). An end event is (right, 0, 0). It carries no building; it just tells the sweep to stop at right and tidy up.
3. events.sort() orders the events left to right. Tuples compare item by item, so at the same x a taller start (more negative) comes first, and starts (negative) come before end markers (0).
4. live starts with the ground (0, inf). Its height is 0 and it never ends, so live[0] always exists.
5. In the loop we read the three fields of the event by index. If negative_height != 0, this is a start event, so we push the building into live.
6. The while loop pops the top building while it has already ended (right <= event_x). Ended buildings deeper in the heap can stay for now; they get removed later if they ever reach the top. That is called lazy deletion.
7. current_height = -live[0][0] flips the sign back to get the real height of the tallest live building.
8. Recording: if result is empty, or the last key point has a different height, the outline changed here, so we append [event_x, current_height]. Otherwise the height is unchanged and nothing is recorded.

Dry run on the example buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]:

Result: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]].

Edge cases to test:

• Buildings sharing an edge with the same height (don't emit duplicate points).
• Nested buildings.
• Adjacent buildings of different heights.

Complexity: O(n log n) time, O(n) space.

Problem: nums is sorted with unique values. Return the smallest list of ranges that covers all the numbers exactly: "a->b" for a run a..b, or "a" for a single number.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 0 ≤ nums.length ≤ 20 · -2³¹ ≤ nums[i] ≤ 2³¹ - 1 · All the values of nums are unique. · nums is sorted in ascending order.

From brute force to the pattern: This is already a linear scan; the only work is careful formatting: "a" for a single number and "a->b" for a range. O(n).

Spot it: The reverse of merging: build intervals. Consecutive numbers (next == current + 1) belong to the same interval, and any gap closes it.

Approach:

1. Walk with index i. Each run starts at start = nums[i].
2. While the next number is exactly one more than the current, extend the run.
3. Close the run: write "start" if it holds one number, otherwise "start->end".
4. Continue from the number after the run.

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        ranges = []
        i = 0
        while i < len(nums):
            start = nums[i]
            # extend the run while the numbers are consecutive
            while i + 1 < len(nums) and nums[i + 1] == nums[i] + 1:
                i = i + 1
            end = nums[i]
            if start == end:
                ranges.append(str(start))
            else:
                ranges.append(str(start) + "->" + str(end))
            # move to the first number of the next run
            i = i + 1
        return ranges

What the code is doing, line by line:

1. while i < len(nums): each pass of this loop produces one range.
2. start = nums[i]: the first number of the run.
3. Inner while i + 1 < len(nums) and nums[i + 1] == nums[i] + 1: keep stepping while the next number continues the run. The bounds check comes first so we never read past the end.
4. end = nums[i]: the last number of the run.
5. if start == end: a single number is written alone; otherwise use the "a->b" form.
6. i = i + 1: step past the run.

Dry run on the example:

nums = [0, 1, 2, 4, 5, 7] (LeetCode Example 1). Returns ["0->2", "4->5", "7"].

Edge cases to test:

• An empty array → [].
• A single number.
• Negative numbers, e.g. [-3, -2] → ["-3->-2"].

Complexity: O(n) time, O(1) extra space besides the output.

Problem: Split s into as many parts as possible so each letter appears in at most one part. Return the part sizes.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 500 · s consists of lowercase English letters.

From brute force to the pattern: Trying cut positions and checking that no letter crosses them is O(n²). Each letter's last index tells you exactly how far the current part must reach, so one pass finds every cut.

Spot it: Each letter occupies the interval from its first to its last occurrence. A part must contain whole intervals, so overlapping intervals merge, and a part ends exactly where the merged interval ends: Merge Intervals in disguise.

Why not another pattern? Trying every cut and checking letter sets is O(n²). Building explicit intervals and merging them is equivalent but the greedy scan is shorter.

Approach:

1. Record each letter's last index.
2. Scan s, extending end to the last index of every letter seen.
3. When i == end, the current part is complete: record its size and start a new part.

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}  # last index of each letter
        sizes = []
        start = 0
        end = 0  # the current part must reach at least here
        for i, c in enumerate(s):
            end = max(end, last[c])  # this letter forces the part to extend to its last occurrence
            if i == end:
                sizes.append(end - start + 1)  # every letter seen so far is finished
                start = i + 1
        return sizes

What the code is doing, line by line:

1. last[c]: the end of letter c's interval.
2. end is the end of the merged interval for the current part.
3. When the scan reaches end, no letter in the part appears later, so cutting here is safe and as early as possible.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All letters distinct → parts of size 1.
• One letter at both ends → a single part.
• A single character.

Complexity: O(n) time, O(1) space (26 letters).

Problem: Remove every interval that is covered by another (c ≤ a and b ≤ d). Return how many remain.

Solve it on LeetCode ↗

Constraints: 1 ≤ intervals.length ≤ 1000 · intervals[i].length == 2 · 0 ≤ li < ri ≤ 10⁵ · All the given intervals are unique.

From brute force to the pattern: Comparing every pair is O(n²). After sorting, one running maximum decides coverage for each interval: O(n log n).

Spot it: Interval relationships → sort by start; then a covering interval always comes before the intervals it covers.

Why not another pattern? Checking every pair is O(n²).

Approach:

1. Sort by start ascending and, for equal starts, by end descending (the longest first).
2. Scan, keeping max_end. An interval with end ≤ max_end is covered; otherwise it survives and updates max_end.

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key=lambda iv: (iv[0], -iv[1]))  # longest first on equal starts
        remaining = 0
        max_end = 0
        for start, end in intervals:
            if end > max_end:
                remaining = remaining + 1  # not covered by anything before it
                max_end = end
            # else: an earlier interval starts no later and ends no earlier: covered
        return remaining

What the code is doing, line by line:

1. After sorting, every earlier interval starts at or before the current one.
2. So the current interval is covered exactly when some earlier interval ends at or after it: end <= max_end.
3. Sorting equal starts by descending end makes the longer interval come first, so it correctly covers the shorter ones.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Identical intervals (one covers the other).
• Equal starts with different ends.
• No interval covers another.

Complexity: O(n log n) time, O(n) space for the sorted copy.

Problem: Track half-open ranges [left, right): addRange covers a range, removeRange uncovers it, and queryRange asks whether every number in a range is currently covered.

Solve it on LeetCode ↗

Constraints: 1 ≤ left < right ≤ 10⁹ · At most 10⁴ calls will be made to addRange, queryRange, and removeRange.

From brute force to the pattern: Marking every integer is impossible for ranges up to 10⁹. Keeping disjoint intervals means each operation only touches the intervals that overlap the given range.

Spot it: A set of numbers stored as disjoint, sorted intervals: adding merges overlapping intervals, removing splits them, and querying finds the one interval that could contain the range. That's interval merging plus binary search.

Why not another pattern? A boolean array over all numbers is impossible (up to 10⁹). A segment tree with lazy propagation works but is far more code.

Approach:

1. Store a sorted list of disjoint intervals.
2. addRange: drop every interval that overlaps or touches [left, right), extend the new range to cover them, insert it.
3. removeRange: drop overlapping intervals, but keep their parts sticking out on the left or right.
4. queryRange: binary-search the last interval starting at or before left; covered if it ends at or after right.

from bisect import bisect_right

class RangeModule:
    def __init__(self):
        self.intervals = []  # sorted, disjoint [start, end) pairs

    def addRange(self, left: int, right: int) -> None:
        kept = []
        for s, e in self.intervals:
            if e < left or s > right:
                kept.append([s, e])  # no overlap and not touching: keep as is
            else:
                left = min(left, s)  # merge it into the new range
                right = max(right, e)
        kept.append([left, right])
        kept.sort()
        self.intervals = kept

    def queryRange(self, left: int, right: int) -> bool:
        starts = [s for s, _ in self.intervals]
        i = bisect_right(starts, left) - 1  # last interval starting at or before left
        return i >= 0 and self.intervals[i][1] >= right

    def removeRange(self, left: int, right: int) -> None:
        kept = []
        for s, e in self.intervals:
            if e <= left or s >= right:
                kept.append([s, e])  # untouched
            else:
                if s < left:
                    kept.append([s, left])  # the part sticking out on the left
                if e > right:
                    kept.append([right, e])  # the part sticking out on the right
        self.intervals = kept

What the code is doing, line by line:

1. Intervals are half-open, so [10, 14) and [14, 20) touch; addRange merges touching intervals too (e < left is the strict test).
2. addRange grows [left, right) to swallow every overlapping interval, then inserts it and re-sorts.
3. queryRange: only the interval with the largest start ≤ left can contain left; the range is covered if that interval also reaches right.
4. removeRange keeps the parts of each overlapping interval that lie outside [left, right).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Adding a range that touches an existing one (merge them).
• Removing from the middle of an interval (it splits in two).
• Querying an empty module → False.

Complexity: O(n log n) per addRange, O(n) per removeRange, O(n) per queryRange here (the list of starts is rebuilt; a sorted container makes these O(log n) amortised).

Problem: For each interval, return the index of the interval with the smallest start ≥ its end (or −1).

Solve it on LeetCode ↗

Constraints: 1 ≤ intervals.length ≤ 2 * 10⁴ · intervals[i].length == 2 · -10⁶ ≤ starti ≤ endi ≤ 10⁶ · The start point of each interval is unique.

From brute force to the pattern: All pairs: O(n²); sort + binary search: O(n log n).

Spot it: An intervals question answered by sorting starts and binary search: for each end, find the first start at or after it.

Why not another pattern? Checking all pairs is O(n²).

Approach:

1. starts = sorted((start, index)).
2. For each interval: bisect_left(starts, (end, −1)); return that index or −1.

from bisect import bisect_left

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        starts = sorted((s, i) for i, (s, _) in enumerate(intervals))
        result = []
        for _, end in intervals:
            j = bisect_left(starts, (end, -1))  # first start >= end
            result.append(starts[j][1] if j < len(starts) else -1)
        return result

What the code is doing, line by line:

1. Starts are unique, so (end, −1) sorts before any (end, i), finding a start equal to end too.
2. An interval can be its own right interval when start == end.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Single interval.
• start == end (itself).
• No right interval → −1.

Complexity: O(n log n) time, O(n) space.

Problem: A pair [c, d] can follow [a, b] if b < c. Return the longest chain (pairs in any order).

Solve it on LeetCode ↗

Constraints: n == pairs.length · 1 ≤ n ≤ 1000 · -1000 ≤ lefti < righti ≤ 1000

From brute force to the pattern: LIS DP is O(n²); the greedy is O(n log n).

Spot it: It's interval scheduling: choose as many non-overlapping intervals as possible → sort by end and take greedily (like Non-overlapping Intervals).

Why not another pattern? The LIS-style DP is O(n²); the greedy is O(n log n).

Approach:

1. Sort by the second element.
2. Take a pair if its start is greater than the last taken end.

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        chain = 0
        end = float("-inf")
        for a, b in sorted(pairs, key=lambda p: p[1]):  # earliest end first
            if a > end:
                chain += 1  # it fits after the last chosen pair
                end = b
        return chain

What the code is doing, line by line:

1. Choosing the pair that ends earliest leaves the most room for the rest (exchange argument).
2. Strict > because the chain needs b < c.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Touching pairs (b == c) can't chain.
• Nested pairs.
• One pair.

Complexity: O(n log n) time, O(1) extra space.

Problem: Lamps light [position − range, position + range]. Return the smallest position with the most lamps lighting it.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ lights.length ≤ 10⁵ · lights[i].length == 2 · -10⁸ ≤ positioni ≤ 10⁸ · 0 ≤ rangei ≤ 10⁸

From brute force to the pattern: Checking every candidate against every lamp is O(n²); the sweep is O(n log n).

Spot it: Overlapping intervals → a sweep line over a difference map: +1 where a lamp starts, −1 just after it ends; scan the sorted points.

Why not another pattern? Checking each candidate position against every lamp is O(n²).

Approach:

1. delta[p − r] += 1, delta[p + r + 1] −= 1.
2. Sweep sorted keys with a running sum; keep the first position with the maximum.

from collections import Counter

class Solution:
    def brightestPosition(self, lights: List[List[int]]) -> int:
        delta = Counter()
        for p, r in lights:
            delta[p - r] += 1  # light starts here
            delta[p + r + 1] -= 1  # and stops after p + r
        best_pos, best = None, -1
        current = 0
        for x in sorted(delta):
            current += delta[x]
            if current > best:
                best, best_pos = current, x  # first (smallest) position with this brightness
        return best_pos

What the code is doing, line by line:

1. Brightness only changes at the stored points, so the maximum is reached at one of them.
2. Strict > keeps the smallest position on ties.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Range 0 (a single point).
• Ties (smallest position).
• Negative positions.

Complexity: O(n log n) time, O(n) space.