Intervals & Greedy Problems

Ten classic interview problems — Merge Intervals, Insert Interval, Non-overlapping Intervals, Meeting Rooms I and II, Maximum Subarray, Jump Game I and II, Gas Station and Hand of Straights — solved from zero with two ideas. Intervals: sort them, then walk once from left to right while remembering only the block you are building. Greedy: at every step make the choice that looks best right now, and check with a simple swap argument that it can never hurt. For each problem you will see the slow obvious idea, the insight, the pseudocode, the Dart code and an animation you can feed your own input. You will also see a case where greedy gives the wrong answer, so you know when to reach for something else.

Intervals, sweep lines and greedy choices

Open a paper diary with one line per hour. Every appointment is a coloured strip from its start hour to its end hour. To see which appointments collide, you do not compare every strip with every other strip — you read the day from top to bottom and notice when a new strip begins before the strip you are in has ended. Reading the day in order is the whole trick behind interval problems.

Some words first:

An interval is a stretch of a number line from a start to an end, written [start, end]. In Dart we store it as a list of two whole numbers, for example [2, 6], and a list of intervals as List<List<int>>.
Two intervals overlap when they share some part of the line. [1, 4] and [3, 7] share [3, 4]; [1, 2] and [5, 6] share nothing.
Touching endpoints are the tricky case: [1, 3] and [3, 5] meet at the single point 3. Whether that counts as overlapping depends on the story. Every problem below says which rule it uses — read that sentence first, it changes one comparison from < to ≤.
A closed interval includes both ends ([1, 3] contains 3), so touching ones overlap. A half-open interval [start, end) includes the start but not the end, like a meeting from 9:00 to 10:00 that lets the next meeting start at 10:00 — touching ones do not overlap.
O(n log n) is the cost of sorting n items (see C02 · Merge Sort); O(n) means one pass over the input.

The overlap test

Two intervals a and b overlap exactly when each one starts no later than the other one ends: a.start ≤ b.end and b.start ≤ a.end. Why? They fail to overlap only if one lies completely to the left of the other — a.end < b.start or b.end < a.start. The test is just "neither of those is true". For half-open meetings replace both ≤ with <.

Sort first

Comparing every pair of intervals costs about n²/2 checks. Sorting them by start lines them up like the diary: once they are in order, an interval can only overlap the block you are building right now, never one you finished earlier — the next interval starts at or after everything you have seen. So one pass after the sort is enough (Merge Intervals, Meeting Rooms I). Some problems sort by end instead (Non-overlapping Intervals): when you want to keep as many intervals as possible, the interval that finishes first leaves the most room for the rest. Dart sorts a list of pairs with list.sort((a, b) => a[0].compareTo(b[0])) (see D26 · List methods).

The sweep line: +1 at a start, −1 at an end

Imagine a vertical line moving from left to right across the number line. It only needs to stop where something changes: at a start (one more interval is open) and at an end (one fewer). Turn every interval into two events, (start, +1) and (end, −1), sort the events by time, and keep a running total. The biggest total is the largest number of intervals open at the same moment. When an end and a start happen at the same time, the order of the two events encodes the touching rule: putting −1 first means "a meeting that ends at 4 has left before the one starting at 4 arrives".

Greedy: take the best-looking step, then prove it cannot hurt

A greedy algorithm builds the answer one decision at a time and never takes a decision back. At each step it makes the locally best choice: the meeting that ends first, the cheapest station, the farthest jump. Greedy code is short and fast — usually one sort and one pass. The hard part is being sure it is right.

The usual proof is an exchange argument, and it fits in plain words: "Take any best answer that does not use my greedy choice. Swap my choice into it. The result is still allowed, and it is no worse. So some best answer does use my greedy choice, and I can safely make it and move on to the smaller problem that remains." For example, among intervals you want to keep without overlaps, swapping the one that ends earliest into any best selection never creates a new overlap — it ends even sooner than the one it replaces. You will see this argument again in every problem below.

When greedy fails

Greedy is not always right. Making change with the fewest coins is the classic warning. With coins 1, 5, 10 and 25, "always take the biggest coin that fits" is optimal. But with coins 1, 3 and 4 and the amount 6, greedy takes 4 + 1 + 1 = three coins, while 3 + 3 is only two. Taking the 4 looked best but blocked the better plan, and greedy never goes back. The exchange argument breaks: you cannot swap a 4 into the answer 3 + 3 without making it worse. When this happens, the fix is dynamic programming — try every last coin and reuse the best answers for smaller amounts. That is taught in C15 · Dynamic Programming and practised in Step 13.11 · Dynamic Programming Problems.

For an interval problem, ask: (1) Does touching count as overlapping here? (2) Should I sort by start (to merge or to scan in time order) or by end (to keep as many as possible)? (3) What is the one thing I must remember while walking — the end of the current block, the last kept end, the number of rooms in use? For a greedy problem, ask: what is the locally best choice, and can I swap it into any best answer without making it worse? If you cannot argue the swap, test small cases against a slow exact method before trusting the greedy.

Common traps. (1) Forgetting to sort: a one-pass merge on unsorted input swallows intervals that are far apart (question p10-q13 shows it). (2) Using the wrong touching rule: < versus ≤ is the most common off-by-one in this whole topic. (3) Sorting the caller's list in place when they did not ask for it — copy first. (4) Trusting a greedy because it worked on two examples: always look for a small counterexample, like the coins above.

Merge Intervals

The task. You get a list of intervals in any order. Combine every group of overlapping intervals into one interval that covers the whole group, and return the combined intervals sorted by start. Touching counts as overlapping: [1, 3] and [3, 5] become [1, 5].

Example 1

Input: intervals = [[4, 7], [1, 3], [2, 5], [9, 11], [10, 12]]

Output: [[1, 7], [9, 12]]

Why: [1, 3], [2, 5] and [4, 7] chain together into [1, 7]; [9, 11] and [10, 12] share [10, 11].

Example 2

Input: intervals = [[5, 6], [1, 5]]

Output: [[1, 6]]

Why: they touch at 5, and touching counts here.

Example 3

Input: intervals = [[2, 9], [3, 4], [5, 7]]

Output: [[2, 9]]

Why: both smaller intervals sit inside [2, 9] (they are nested), so the end stays 9.

Constraints

0 ≤ n ≤ 10⁴
0 ≤ start ≤ end ≤ 10⁴

Speed you need: joining pairs until nothing changes is O(n³) = 10¹² steps → sort and one pass: O(n log n) time, O(n) space for the output.

Lay paper strips on a ruler, sorted by where they begin. Pick up the first strip. For each next strip: if it starts before the end of what is in your hand (or exactly at it), tape it on and your piece reaches as far as the longer of the two. If it starts after a gap, put your piece down — it is finished — and pick up the new strip.

Brute force. Keep looking for any two blocks that overlap and join them, until no pair overlaps. Each pass checks every pair, and there can be up to n passes: O(n³).

Key insight. After sorting by start, the intervals that belong to one block come one after another. So you only ever compare the next interval with the last block you built: if it starts at or before that block's end, it joins (the end becomes the larger of the two ends — a nested interval does not shrink it); otherwise there is a gap, and since every later interval starts even later, the last block can never grow again.

An edge case with three traps at once: a long interval with a short one nested inside, an interval that only touches the block's end, and a single point [14, 14]. An empty list returns an empty list right away (line 1).

Complexity. Time O(n log n) for the sort plus O(n) for the pass. Space O(n) for the sorted copy and the output.

Common mistakes. (1) Setting last.end = intervals[i].end instead of the maximum: a nested interval would cut the block short ([2, 9] then [3, 4] would become [2, 4]). (2) Using < instead of ≤: [1, 3] and [3, 5] would stay apart, which breaks this problem's touching rule. (3) Forgetting the empty list: intervals[0] would crash. (4) Comparing with the previous input interval instead of the last merged block: after [1, 10], [2, 3], the interval [5, 6] must be compared with end 10, not with 3.

Follow-ups interviewers ask. The total length covered by all intervals (p10-q13's cousin p10-q5). The common part of two interval lists (p10-q7). Free time shared by several people (p10-q19). Intervals arriving one at a time: keep them in a sorted map from start to end, or use Insert Interval below for each new one.

The ideas underneath: sorting (C02 · Merge Sort, C07 · Quicksort) and "remember only the last block", the same spirit as the running answer in Step 13.3 · Buy and Sell Stock.

Insert Interval

The task. You get a list of intervals that is already sorted by start, with a gap between every two neighbours (no two overlap or touch). Add one new interval, merging it with every interval it overlaps, and return the new list — still sorted, still with gaps. Touching counts as overlapping, as in Merge Intervals.

Example 1

Input: intervals = [[1, 2], [4, 6], [7, 8], [11, 14]], newInterval = [5, 9]

Output: [[1, 2], [4, 9], [11, 14]]

Why: [5, 9] overlaps [4, 6] and [7, 8], so all three become [4, 9].

Example 2

Input: intervals = [[3, 5], [9, 12]], newInterval = [6, 7]

Output: [[3, 5], [6, 7], [9, 12]]

Why: it fits into the gap between 5 and 9 without touching anything.

Example 3

Input: intervals = [], newInterval = [2, 4]

Output: [[2, 4]]

Why: an empty list just receives the new interval.

Constraints

0 ≤ n ≤ 10⁴
0 ≤ start ≤ end ≤ 10⁵
intervals sorted by start, neighbours separated by a gap

Speed you need: the input is already sorted, so re-sorting (O(n log n)) is wasted work → one pass: O(n) time, O(n) space for the output.

A bookshelf where each book is an interval, already in order with space between them. A new, wide book arrives. Walk along the shelf: books that end before the new one starts stay where they are. Books that the new one touches get glued to it — it grows to cover them. Once you reach a book that starts after the (grown) new book ends, put the new book down; everything after it stays as it was.

Brute force. Append the new interval and run Merge Intervals again: O(n log n). It works, but it ignores that the list is already sorted.

Key insight. Because the list is sorted with gaps, it splits into three runs: intervals entirely before the new one (their end < new start), intervals that overlap it (their start ≤ new end), and intervals entirely after it. Three short loops, one after another, each move i forward and never back. The middle loop swallows each overlapping interval by stretching the new one to the smaller start and the larger end.

An edge case: the new interval covers everything. The first loop stops at once, the second loop swallows every interval, and the result has a single interval.

Complexity. Time O(n) — i visits each interval once across the three loops. Space O(n) for the output (O(1) besides it). Finding where the overlap begins could use binary search, O(log n), but copying the output is still O(n).

Common mistakes. (1) Writing the first loop's test as end ≤ newStart: with touching counting as overlap, [1, 3] and the new [3, 4] must merge, so "before" means strictly end < newStart. (2) Updating only the end in the middle loop: an overlapping interval can start earlier than the new one ([4, 6] with new [5, 9] gives start 4). (3) Forgetting to add the new interval when nothing overlaps (Example 2) or when the list is empty (Example 3). (4) Modifying the input list while looping over it — build a new list.

Follow-ups interviewers ask. Removing an interval instead of adding one (cut the overlapping ones into at most two pieces each). Many insertions online: keep a sorted map from start to end and only touch the neighbours (p10-q15 and p10-q28 are calendar versions).

The idea underneath: a sorted list lets you skip whole runs at once — the same reason Step 13.5 · Binary Search is fast.

Non-overlapping Intervals

The task. Return the smallest number of intervals to remove so that no two of the remaining intervals overlap. Here touching is fine: [1, 2] and [2, 3] may both stay.

Example 1

Input: intervals = [[1, 4], [2, 3], [3, 6], [5, 7], [6, 8]]

Output: 2

Why: keep [2, 3], [3, 6] and [6, 8] (they only touch); remove [1, 4] and [5, 7].

Example 2

Input: intervals = [[1, 2], [2, 3], [3, 4]]

Output: 0

Why: neighbours only touch, which is allowed.

Example 3

Input: intervals = [[1, 5], [1, 5], [1, 5]]

Output: 2

Why: three copies of the same interval — only one can stay.

Constraints

1 ≤ n ≤ 10⁵
−5·10⁴ ≤ start < end ≤ 5·10⁴

Speed you need: trying every subset to keep is 2ⁿ → sort by end and one pass: O(n log n) time, O(n) space for the sorted copy.

One meeting room, many requests, and you want to say yes to as many as possible. Which request do you accept first? Not the earliest to start and not the shortest — the one that finishes first. It hands the room back soonest, so it leaves the most time for everyone else. Then repeat with the requests that start after it ends. Removing as few as possible is the same as keeping as many as possible.

Brute force. Try every subset of intervals to keep, check that no two overlap, and remember the biggest: 2ⁿ subsets. The verify file uses exactly this to check the fast answer on small inputs.

Key insight — and why sorting by end is safe. Sort by end. Walk through and keep an interval whenever it starts at or after the end of the last kept one; otherwise remove it. The exchange argument in plain words: take any best set of kept intervals. Its interval that ends first can be swapped for the interval that ends earliest overall — that one ends no later, so it cannot overlap anything the swapped-out interval did not already avoid. The set stays valid and the same size. So keeping the earliest-ending interval is always part of some best answer; after that, the same reasoning applies to the intervals that start after it. Sorting by start would fail: one long interval that starts first (like [1, 10]) would block many short ones.

An edge case where touching decides everything: [1, 2], [2, 3] and [3, 4] only touch and all stay, while [1, 3] overlaps two of them.

Complexity. Time O(n log n) for the sort, O(n) for the pass. Space O(n) for the sorted copy (O(1) if sorting in place is allowed).

Common mistakes. (1) Sorting by start and keeping the first: [1, 10], [2, 3], [4, 5] would keep only [1, 10] and remove 2 instead of 1. (2) Using > instead of ≥: touching intervals would be removed, against this problem's rule. (3) Starting lastEnd at 0: intervals with negative starts would be removed by mistake — start below every possible value. (4) Counting kept intervals and forgetting the question asks for removed ones (n − kept).

Follow-ups interviewers ask. Minimum arrows to burst balloons — the same sort by end, but touching balloons share an arrow (p10-q8). If each interval has a profit, greedy breaks and you need dynamic programming with binary search (p10-q27). Return which intervals to keep: record them in the "keep" branch.

This is the activity-selection problem from C16 · Greedy Algorithms, where the same exchange argument is shown step by step.

Meeting Rooms I and II

The tasks. Each meeting is [start, end): a meeting that ends at 10 lets another start at 10 in the same room (touching is fine). Part I: can one person attend every meeting (no two clash)? Return true or false. Part II: what is the smallest number of rooms that can hold all the meetings?

Example 1 · Part I

Input: meetings = [[9, 10], [13, 15], [10, 12]]

Output: true

Why: sorted they are [9, 10], [10, 12], [13, 15]; the first two only touch at 10.

Example 2 · Part I

Input: meetings = [[1, 5], [4, 6]]

Output: false

Why: the second starts at 4, before the first ends at 5.

Example 3 · Part II

Input: meetings = [[0, 6], [1, 3], [4, 8], [5, 9], [8, 10]]

Output: 3

Why: at time 5, [0, 6], [4, 8] and [5, 9] are all running.

Example 4 · Part II

Input: meetings = [[2, 4], [4, 6], [6, 8]]

Output: 1

Why: back to back — each one ends exactly when the next begins.

Constraints

0 ≤ n ≤ 10⁴
0 ≤ start < end ≤ 10⁶

Speed you need: comparing every pair is 5·10⁷ and checking every moment of the day is n · 10⁶ = 10¹⁰ → sort: O(n log n) time, O(n) space.

Part I is reading your diary in order and asking, at each appointment, "did the previous one finish before this one starts?". Part II is a receptionist with a stack of room keys. People arrive in order of start time. When someone arrives, the receptionist checks the earliest checkout time among the rooms in use: if that meeting has already ended, its key is handed to the newcomer; if not, a new room must be opened. The number of keys ever handed out is the answer.

Part I. Brute force compares every pair, O(n²). Sorting by start makes it one pass: the first clash, if there is one, is always between neighbours in start order. Suppose meeting i clashes with some earlier meeting k that is not its neighbour. Meeting k is still running when i starts, and meeting k + 1 starts between them — so k + 1 starts while k is still running, and k and k + 1 already clash. Following that chain, some neighbour pair clashes earlier, and the loop returns false there.

Part II — brute force. Check every whole-number moment of the day and count the meetings running at that moment (start ≤ t < end). The biggest count is the answer, but the cost depends on how long the day is, not on how many meetings there are.

Part II — key insight. We do not care which meeting is in which room, only how many are running. Put all start times in one sorted list and all end times in another. Walk the starts in order with i, and keep a second pointer j at the earliest end time that has not yet freed a room. If the next start comes before ends[j], nobody has left yet, so a new room opens. Otherwise the meeting ending at ends[j] has left (touching is fine, so equal times free the room), its room is reused, and j moves on. This is the sweep line from the opening, with the two event lists kept apart. A min-heap of end times (p10-q18, heaps in C06 · Priority queues) gives the same answer and can also tell you which room each meeting gets.

An edge case: back-to-back meetings. Each start is equal to the earliest end, so the room is reused every time and one room is enough.

Complexity. Part I: time O(n log n), space O(n) for the sorted copy. Part II: time O(n log n) for the two sorts plus O(n) for the walk, space O(n) for the two lists.

Common mistakes. (1) Using ≤ in starts[i] < ends[j]: back-to-back meetings would each get a new room. (2) Sorting starts and ends together as pairs and walking only one list: you lose the "earliest end" information. (3) Thinking Part II needs rooms to go down when a meeting ends: in this version a reused room simply does not count again, so rooms is the number of rooms ever opened, which equals the busiest moment. (4) In Part I, comparing only with the very first meeting instead of the previous one.

Follow-ups interviewers ask. Which room does each meeting get? Use a min-heap of (end time, room number). Car pooling, where each trip carries several passengers (p10-q14). Booking one meeting at a time and rejecting clashes (p10-q15), or allowing double but not triple bookings (p10-q28). How many intervals cover a given moment (p10-q23).

The ideas underneath: sorting and two pointers walking two sorted lists, as in Step 13.2 · Two Sum II, and priority queues from C06 · Heapsort.

Maximum Subarray (Kadane's algorithm)

The task. Given a list of whole numbers (some may be negative), return the largest sum of a subarray — a run of neighbouring numbers with nothing skipped. The run must contain at least one number, so for a list of only negative numbers the answer is the least negative one.

Example 1

Input: nums = [3, -4, 5, -1, 2, -6, 4]

Output: 6

Why: the run 5, −1, 2 (positions 2 to 4) adds up to 6.

Example 2

Input: nums = [-4, -2, -7, -3]

Output: -2

Why: every number is negative, so the best run is the single number −2.

Example 3

Input: nums = [8]

Output: 8

Why: one number is its own only run.

Constraints

1 ≤ n ≤ 10⁵
−10⁴ ≤ nums[i] ≤ 10⁴

Speed you need: every (start, end) pair is n² = 10¹⁰ → O(n) time, O(1) extra space; sums stay within ±10⁹, far inside Dart's 64-bit int.

You walk along a road picking up coins (positive numbers) and paying tolls (negative numbers). Your pocket holds the total since the place you started. If your pocket ever goes below zero, you are carrying a debt: anything you collect from now on would be worth more without it. So you throw the debt away and start a fresh walk from the next step. Along the way you write down the best pocket total you have ever had.

Brute force. Try every start, and for each start extend the end one step at a time with a running sum: O(n²).

Key insight — why resetting at a negative running sum is safe. Let cur be the best sum of a run that ends just before position i. Any run that ends at i either starts at i or extends the best run ending at i − 1. If cur is negative, extending it can only make things smaller than starting fresh — cur + nums[i] < nums[i] — so the best choice is to drop it (set cur to 0). If cur is zero or positive, keeping it never hurts. That is the greedy choice, made at every step, and it never needs undoing because the decision at i depends only on cur. This method is called Kadane's algorithm. Starting best at nums[0] (not 0) handles the all-negative case.

An edge case: every number is negative. The running sum goes below zero after every number, so each step starts fresh, and best ends as the largest single number.

Complexity. Time O(n) — one look at each number. Space O(1) — two numbers.

Common mistakes. (1) Starting best at 0: for [−4, −2, −7, −3] you would return 0, the sum of an empty run, which is not allowed. (2) Resetting when nums[i] is negative instead of when the running sum is negative: in [5, −1, 2] the −1 is worth keeping because 5 − 1 is still positive. (3) Updating best before adding nums[i]: the last number would never be counted. (4) Mixing this up with Buy and Sell Stock: that one needs a running minimum of prices; this one a running sum — though the stock problem is Kadane on the day-to-day differences.

Follow-ups interviewers ask. Return the start and end of the best run (remember where the last reset happened). The largest product instead of sum — keep both the biggest and the smallest product, because a negative number flips them (p10-q16). A circular list where the run may wrap around the end (p10-q20). Allow deleting one number from the run (p10-q31). A 2D grid: fix two rows and run Kadane on column sums, O(rows² · columns).

The ideas underneath: a running answer that depends only on the previous step — a tiny dynamic programme (C15 · Dynamic Programming) — and the "drop what can only hurt" move of Step 13.3 · Buy and Sell Stock.

Jump Game I and II

The tasks. You stand on index 0 of a list of whole numbers that are 0 or more. nums[i] is the longest jump you may make from index i — you may also jump shorter, or onto any index in between. Part I: can you reach the last index? Part II: what is the smallest number of jumps to reach it? (If it cannot be reached, our version returns −1.) If the list has one number you are already at the end: true, and 0 jumps.

Example 1 · Part I

Input: nums = [2, 3, 0, 1, 4]

Output: true

Why: jump 0 → 1, then index 1 lets you jump 3 steps straight to index 4.

Example 2 · Part I

Input: nums = [2, 1, 0, 3]

Output: false

Why: every path lands on index 2, whose value 0 lets you go nowhere.

Example 3 · Part II

Input: nums = [1, 4, 1, 1, 2, 1, 3]

Output: 3

Why: 0 → 1 → 4 → 6; index 0 only reaches index 1, and index 1 does not reach the end.

Example 4 · Part II

Input: nums = [6]

Output: 0

Why: you start on the last index.

Constraints

1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ 10⁵

Speed you need: breadth-first search tries every jump from every index, up to n² = 10⁸ steps → one pass: O(n) time, O(1) extra space.

Stepping stones across a river, each with a number painted on it: how far you may leap from there. For Part I you do not plan a route at all — you walk forward stone by stone and keep a flag at the farthest stone any stone so far can reach. If you ever stand on a stone beyond the flag, you could not have got there: stuck. For Part II think of ripples: all stones reachable with 0 jumps, then all reachable with 1 jump, then with 2, … The number of ripples it takes to touch the last stone is the answer.

Brute force. Breadth-first search: from each index, try every jump length. It finds the fewest jumps (and whether the end is reachable at all), but each index can try up to n jumps: O(n²). The page's tests use it as the reference for both parts.

Part I — key insight. The reachable indexes always form one unbroken block from 0 to some reach: if you can get to index k, you can get to every index before it (jumps may be shorter). So you only need that one number. Walk i from left to right; if i > reach, index i is unreachable and so is everything after it. Otherwise stretch reach to i + nums[i]. The greedy choice is "always remember the farthest point" — no route is ever stored, because any index inside the block is reachable somehow.

An edge case: a zero in the way. Every route lands on index 2, whose value is 0, and reach stops growing there.

Part II — key insight. This is breadth-first search without a queue. The indexes reachable with exactly jumps jumps form a block ending at end. While scanning that block, keep far, the farthest index any of them reaches — that is the end of the next block. When i reaches end, the current block is used up: one more jump is needed, and the new block ends at far. Greedy part: you never decide which index to jump from; you only count blocks. If far is still i when a block is used up, nothing reaches further: return −1.

An edge case: you start on the last index. The loop runs for i from 0 to n − 2, which is no steps at all, and the answer is 0 jumps.

Complexity. Both parts: time O(n), space O(1).

Common mistakes. (1) In Part II, looping i up to n − 1 instead of n − 2: when end lands exactly on the last index you would count one extra jump. (2) Always jumping the full nums[i] ("jump as far as you can"): in [2, 3, 1, 1, 4]-style lists a shorter first jump onto a bigger number wins. Count blocks instead. (3) In Part I, checking i ≥ reach instead of i > reach: index reach itself is reachable. (4) Writing it recursively, "try every jump": that is exponential without memoisation.

Follow-ups interviewers ask. Watering a garden with the fewest taps — turn each tap into "from here you can reach there" and it becomes Part II (p10-q22). Jumps that may go left or right (then it is a graph: C22 · BFS). Minimum refuelling stops on a road — greedy with a heap (p10-q30).

The ideas underneath: breadth-first search in layers (C22 · BFS, DFS) squeezed into two numbers because the layers are contiguous blocks.

Gas Station

The task. n gas stations stand on a circular road. At station i you can fill up gas[i] litres, and driving from station i to station i + 1 (the last one leads back to station 0) uses cost[i] litres. Your tank starts empty and has no limit. Return the index of the station where you can start and drive once around the whole circle, or −1 if no start works. When an answer exists, return the smallest such index.

Example 1

Input: gas = [3, 1, 2, 5, 4], cost = [4, 2, 1, 2, 3]

Output: 2

Why: from station 2 the tank holds 1, 4, 5, 4, 3 after each leg — never negative.

Example 2

Input: gas = [2, 2, 2], cost = [3, 2, 2]

Output: -1

Why: the loop has 6 litres of gas but costs 7.

Example 3

Input: gas = [5], cost = [5]

Output: 0

Why: one station: fill 5, drive the loop for 5, arrive with 0 — that is allowed.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ gas[i], cost[i] ≤ 10⁴

Speed you need: driving the loop from every start is n² = 10¹⁰ → one pass: O(n) time, O(1) extra space.

Each station gives you a gain: gas you get there minus gas the next leg costs. You try a start and drive. If the tank goes below zero on the way to some station, the trip failed — and so would every trip that started between your start and that point, because those trips skip the stations you passed, and each of those stations had left you with a tank of zero or more. Starting later only throws that gas away. So jump your start straight past the failure.

Brute force. Simulate the full loop from each start and return the first that never runs dry: O(n²).

Key insight — why the start after the last failure works. Two facts. (1) Skipping is safe. Start at s and suppose the tank first goes negative on the leg after station k. For any station t between s and k, the part of the trip from s to t − 1 ended with a tank of zero or more (it had not failed yet). Starting at t instead begins with an empty tank — no more gas than before — so it also fails by station k. All of s … k are ruled out, and the next candidate is k + 1. Question p10-q24 checks this numerically. (2) The total decides. If the sum of all gains is negative, no start can work: the loop as a whole loses gas. If it is zero or more, the last candidate start works: from start to the end of the list the tank never went negative, and the stations before start add up to a loss of at most the gain collected from start to the end (because the total is not negative), so the tank survives the wrap-around.

An edge case: the loop does not have enough gas in total. The walk still finds a candidate, but the final check total < 0 returns −1.

Complexity. Time O(n) — one pass. Space O(1) — three numbers.

Common mistakes. (1) Moving start only to start + 1 after a failure: correct but O(n²) in the worst case — the whole point is jumping to i + 1. (2) Forgetting the total check and returning the last candidate even when the loop loses gas. (3) Resetting total together with tank: total must count every station. (4) Treating a tank of exactly 0 as a failure: arriving with an empty tank is fine; only below 0 fails.

Follow-ups interviewers ask. A tank with a capacity limit (then simulate with the limit, the skip argument changes). Fewest refuelling stops on a straight road (p10-q30). The same "running sum goes negative → restart after it" move appears in Kadane above — compare the two animations.

The idea underneath: prefix sums of gains — the start is right after the position where the running sum is lowest. Running sums were met in Step 13.1 · Product Except Self.

Hand of Straights

The task. You hold cards with whole numbers on them and a group size size. Can you split all the cards into groups of exactly size cards, where each group is a run of consecutive numbers (like 4, 5, 6)? Duplicate cards are allowed and each card goes into exactly one group.

Example 1

Input: hand = [5, 1, 3, 2, 4, 6, 7, 2, 3], size = 3

Output: true

Why: [1, 2, 3], [2, 3, 4] and [5, 6, 7].

Example 2

Input: hand = [1, 2, 3, 4, 5], size = 2

Output: false

Why: 5 cards cannot be cut into groups of 2.

Example 3

Input: hand = [4, 4, 5, 6, 6, 7], size = 3

Output: false

Why: both 4s must start a run 4, 5, 6, but there is only one 5.

Constraints

1 ≤ n ≤ 10⁴
0 ≤ hand[i] ≤ 10⁹
1 ≤ size ≤ n

Speed you need: trying every way to group the cards is exponential → count, sort the distinct values, one pass: O(n log n) time, O(n) space.

Spread the cards on a table in piles by number. Look at the smallest pile. Those cards have no smaller neighbour, so each of them can only be the first card of a run. If the smallest pile has 2 cards, you must build 2 runs starting there, taking 2 cards from each of the next size − 1 piles. If a pile is too small, it is impossible. Then look at the new smallest non-empty pile and repeat.

Brute force. Try every way to choose a group for the first card, recurse on the rest — exponential. The verify file uses this on small hands as the reference.

Key insight. The smallest remaining value v must start every group that contains it — nothing smaller is left to come before it. That is a forced choice, and greedy simply makes it: remove count[v] runs v, v + 1, …, v + size − 1 at once. If any of those values has fewer than count[v] cards, the hand cannot be split. A quick check first: if n is not a multiple of size, the answer is false.

An edge case: duplicates that cannot all start runs. The two 4s need two 5s.

Complexity. Time O(n log n) to sort the distinct values; the inner loop removes whole piles, so the total work after sorting is O(n · size) in the worst case, and O(n) when counts are removed in bulk as here. Space O(n) for the counts map.

Common mistakes. (1) Starting runs from an arbitrary card instead of the smallest: from 2 in [1, 2, 3, 2, 3, 4] you might take 2, 3, 4 and leave 1, 2, 3 — fine here, but in general an arbitrary start can strand a smaller card. (2) Removing one run at a time and re-sorting each time: O(n² log n). (3) Forgetting values that are missing entirely: count[w] is null in Dart, so use ?? 0. (4) Skipping the divisibility check is not wrong, but it is a free early exit.

Follow-ups interviewers ask. Groups of at least 3 consecutive cards instead of exactly size (p10-q25 — extend an existing run if you can, otherwise start a new one). The same idea on a sorted array of numbers.

The ideas underneath: counting with a map (Step 13.1 · Top K Frequent) and sorting the keys (D27 · Set & Map methods).

Quiz

Interview questions

Variations and follow-ups of the problems above — the questions interviewers move to once you have solved the classic version — plus a few where greedy is not enough. Every solution is tested in Dart on its examples and on hundreds of random inputs against a slow exact reference.

Cheat sheet

Problem	Touching rule	Sort / walk	Time	Space	The move and why it is safe
Merge Intervals	overlap	by start, one pass	O(n log n)	O(n)	start ≤ last end → extend to max; later intervals start even later
Insert Interval	overlap	already sorted, three runs	O(n)	O(n)	before (end < s) · swallow (start ≤ e) · after
Non-overlapping Intervals	fine	by end, keep if start ≥ last end	O(n log n)	O(n)	the earliest end can be swapped into any best set
Meeting Rooms I	fine	by start, neighbours	O(n log n)	O(n)	the first clash is always between neighbours
Meeting Rooms II	fine	starts and ends sorted apart	O(n log n)	O(n)	start < ends[j] → new room, else reuse and j + 1
Maximum Subarray	—	one pass	O(n)	O(1)	running sum < 0 → drop it; it can only lower later sums
Jump Game I	—	one pass	O(n)	O(1)	reachable indexes are one block [0, reach]
Jump Game II	—	one pass	O(n)	O(1)	count BFS layers: at i = end, jump and end ← far
Gas Station	—	one pass	O(n)	O(1)	tank < 0 at i → start ← i + 1; total ≥ 0 decides
Hand of Straights	—	count + sorted keys	O(n log n)	O(n)	the smallest value must start count[v] runs

Tool	Shape	Use when
Overlap test	a.start ≤ b.end and b.start ≤ a.end (use < for half-open)	any two intervals
Sort by start + last block	compare with merged.last only	merging, covering, free time
Sort by end + last kept end	keep if start ≥ lastEnd	keep the most / remove the fewest / fewest points to hit all
Sweep line	(start, +1), (end, −1), sorted; ties decide touching	"how many at once", rooms, car pooling
Exchange argument	swap the greedy choice into any best answer; still valid, no worse	to trust a greedy
Counterexample hunt	compare greedy with brute force on small inputs	before trusting a greedy (coins 1, 3, 4 and amount 6)

Greedy fails when an early choice blocks a better plan later (coin systems like 1, 3, 4; whole-item knapsack; intervals with profits). Then use dynamic programming — C15 · Dynamic Programming and Step 13.11 · Dynamic Programming Problems. Background for every greedy proof on this page: C16 · Greedy Algorithms.