Problem Solving: Advanced

A two-pointer solution keeps 2 indexes into one sequence and moves them based on the values they point at. Neither pointer ever reverses direction. Starting from opposite ends, left only rises while right only falls. Each step shrinks the gap between them by at least 1, so on a list of n items the loop ends within n - 1 steps. The skill lies in proving that each move discards only values that can't be part of the answer.

A palindrome reads the same in both directions: character 0 must equal the last character, character 1 must equal the second to last, and so on inward. Put left at the start and right at the end, compare the 2 characters, then step both pointers toward the middle. The first mismatch ends the check, and if the pointers meet without one, every mirrored pair matched.

On "racecar" the loop starts by comparing indexes 0 and 6, then moves inward 1 step at a time to 1 and 5 and finally to 2 and 4. After that left and right both sit at 3, the while test fails, and the middle e needs no partner. On "hello" the very first comparison of h against o returns False. The 3 letters between them are never read.

A list of track lengths in minutes is sorted ascending, and a 10-minute ad-free gap should be filled by exactly 2 tracks. Start left at the shortest track and right at the longest, then add them. A total below the target can only grow if left moves up to a longer track, and a total above it can only shrink if right moves down to a shorter one.

Every step removes one value with proof that it cannot be in any valid pair, which is why the input must be sorted. On unsorted values values[left] is no longer guaranteed to be the shortest track still in play. Without that guarantee the loop can walk past a pair that exists.

Pointers can also travel in the same direction. To remove duplicates from a sorted list in place, a read index visits every item while a write index marks where the next distinct value goes. Sorting already put equal values next to each other, so a value is new exactly when it differs from the last value written.

Trace it on [1, 1, 2, 3, 3, 3, 5]. Both indexes start at 1. The 1 at position 1 equals the last value written, values[0], so it's skipped and only read advances. The 2 at position 2 differs, so it's copied to position 1 and write becomes 2. The first 3 lands at position 2, the next 2 copies of 3 match it and are skipped, and 5 lands at position 3. write ends at 4, and del values[write:] cuts the 3 stale items at positions 4 to 6. write never passes read, so a copy never overwrites a value that hasn't been read yet.

Each branch moves the pointer whose value caused the miss. A total below the target means the smaller value is too small, so left steps up to a larger one; a total above it means the larger value is too big, so right steps down. Swap the 2 moves and the walk heads away from the answer: on [2, 3, 4, 6, 7, 9] with a target of 10, the first total of 11 moves left up to the 3, and the totals climb to 12 and 13, then to 15 and 16, until the pointers meet and the function returns None.

Starting the inner loop at i + 1 tries each pair once, yet the count of pairs grows with the square of the list length: double the list and the worst case roughly quadruples.

For any number, its partner is fully decided: it must equal target - num. The question 'which number pairs with this one?' becomes 'have I already seen the value target - num?' A dict answers that with one hash lookup, and the cost of a lookup stays flat whether the dict holds 4 keys or 4 million. The keys are values seen so far, and each maps to the position where it appeared.

At position 0 the loop needs 7, which is not in the dict yet, so it stores {2: 0}. At position 1 it needs 2, which is a key, so it returns [0, 1] and never reads 11 or 15. On a list with no answer, each number is looked up once and stored once, so the work is one pass plus one dict entry per item.

The list [5, 3, 8] has no pair that sums to 10, yet the function reports positions 0 and 0: the 5 at position 0 found itself in the dict. Checking first means seen holds only earlier positions when the lookup runs. Repeated values still work in that order: on [5, 5] with a target of 10, position 1 needs 5, finds the 5 stored at position 0, and returns [0, 1].

When the answer needs only whether a value appeared, the positions stored in the dict go unused, and a set does the same work with keys alone. x in seen is the same flat-cost hash lookup, and seen.add(x) records a value. Finding the first track id played a second time is the two-sum loop with a set: if the current id is already in seen, print it and stop; if not, add it. The order matters for the same reason as before: add first, and every id finds itself on its first visit.

Plenty of questions want one winner: the busiest day, the longest streak, the biggest jump. One approach builds a list of every candidate and calls max at the end. A tighter one keeps only the best candidate found so far and updates it as each item passes, so its memory stays the same size whether it reads 10 days or 10 years.

Day 2 and day 3 both reach 77, and the strict > keeps the first, printing 77 2. Change it to >= and the later tie replaces the earlier one, printing 77 3. The comparison operator is a decision about ties, so choose it on purpose.

The biggest rise in daily listeners, from an earlier day to a later one, depends on a pair of days. Subtracting the overall minimum from the overall maximum gives the wrong answer when the peak comes before the trough. Keep 2 running values instead: lowest, the smallest count seen so far, and best_gain, the largest rise found so far. Each new day is measured against the lowest day before it.

Starting best at 0 looks harmless until every value is negative:

The first loop reports 0, a value that never appears in the list. Starting from changes[0] makes the first real item the first candidate. On an empty list that start raises IndexError, which is usually right: an empty list has no best value, and a guard clause before the loop can say so in its own words. The rise loop starts best_gain at 0 on purpose, meaning 'no rise found'.

Some winners are runs, such as the longest stretch of consecutive days with any listening. Keep current, the length of the run that ends today, and longest, the best run so far. A listening day extends current and offers it to longest; a silent day resets current to 0.

The winning run is 3 days long. It starts with 12 minutes and 45 minutes and ends on a 9-minute day. The same 2-variable shape finds the largest total over any consecutive run when values can be negative. Now current is the best total of a run ending exactly at this item, and that run has 2 choices: extend the run that ended at the previous item, or start fresh here. A run whose total is negative only drags down whatever follows it, so when current is negative the next run starts over at the new value. That is current = max(value, current + value). The winning run can end at any item, so best = max(best, current) keeps the largest current seen.

Build a list prefix where prefix[i] is the total of the first i days, starting with prefix[0] = 0. The total from day first through day last, both included, is prefix[last + 1] - prefix[first]: everything up to and including last, minus everything before first.

The query for days 2 through 4 reads only the 2 entries 110 and 50, however many days lie between them. Day 3 alone works the same way: prefix[4] - prefix[3] is 80 minus 75. The build costs one pass, and each query after it costs one subtraction.

Without the leading 0, prefix[i] would hold the total through day i, and a range starting at day 0 would subtract prefix[first - 1]. In Python that is prefix[-1], the last element, so the query returns a wrong number and raises no error. The 0 at the front gives every range, including one that starts at day 0, the same formula.

How many runs of consecutive hours have a net follower change of exactly 7? A run from hour first to hour last totals 7 when prefix[last + 1] - prefix[first] == 7, so at each hour the question is how many earlier running totals equal the current total minus 7. That's the complement lookup from two-sum, with counts in the dict instead of positions.

The 4 runs are 3, 4, then 7, then 7, 2, -3, 1, then 1, 4, 2. The entry seen[0] = 1 stands for the empty prefix before hour 0, so a run starting at hour 0 gets counted. Negative values rule out a sliding window here, since growing a window no longer guarantees a larger total.

Prefix code goes wrong in 2 places, and both are off by one. The list must start with 0, which gives it 1 more entry than there are days, and a query's end index must be last + 1, because entry i holds the total of the days before day i. A one-day range tests both at once: range_total(d, d) has to equal day d's own minutes. Without the + 1 it returns 0, and without the leading 0 it returns the next day's minutes instead.

Listening sessions arrive as (start, end) hours in any order, and overlapping ones should become one block. After sorting by start, a session can only overlap the block built just before it, so each session either extends the last block or opens a new one.

(3, 6) starts at 3, inside [1, 4], so the block grows to [1, 6]. (9, 12) starts after 6 and opens a new block, which (11, 13) then stretches to 13. The max(last[1], end) matters for a session lying fully inside a block, such as (2, 3) inside [1, 6], which must not shrink it.

A sorted list also supports binary search. bisect_right(lengths, x) returns how many values are at most x, so the program below finds 3 sessions of 10 minutes or less and 2 longer than 20. One sort pays for any number of these questions.

Every pass in this section trusts the order the sort produced. The closest-pair loop assumes the nearest values are neighbours, the merge assumes a session can only overlap the last block, and bisect_right assumes no larger value sits before a smaller one. Remove the sort and each loop still runs to the end with no exception. The assumption is false, though, so the output is a wrong answer that looks like a real one.

A missing sort sometimes leaves a visible trace. In the closest-pair loop run on arrival order, b - a goes negative whenever a later timestamp is smaller, as 140 - 905 = -765 is. A negative gap is smaller than every real gap, so it wins. Any gap below 0 means the order the loop relies on is missing.

This one combines 3 patterns: sort the input, walk 2 pointers inward, and keep the best total so far. A total that fits the gap is a candidate, and moving left up tries a larger one; a total that overflows moves right down to a shorter track.