Hard 3: Lists and positions

These problems move one or two positions through a list in a disciplined way: from both ends inward, a reader ahead of a writer, or a window that grows on the right and shrinks on the left. (Programmers often call such a position a pointer; here it just means an index you move.) Several ask you to change the list in place rather than build a new one, and the checks confirm that the list you were given ends up changed. Any correct solution passes; the described method is what each problem teaches.

Two sum on a sorted list

When the list is sorted, two positions can find a pair that sums to a target without checking every pair. Put one position at the start and one at the end. If the two values add up to the target, you are done. If the sum is too small, only moving the left position rightwards can make it bigger; if too large, only moving the right position leftwards can make it smaller. Repeat until the positions meet.

Write pair_sum(sorted_nums, target) that returns the two positions as a tuple (left, right), or None if no pair works. Values are distinct.

pair_sum([1, 3, 4, 6, 8], 10)  ->  (2, 3)
pair_sum([1, 2], 10)           ->  None

def pair_sum(sorted_nums, target):
    ...

Remove duplicates in place

A sorted list has duplicates next to each other. Remove them without making a new list, using two positions: a reader that visits every item, and a writer that marks where the next kept item goes. Whenever the reader sees a value different from the last kept one, copy it to the writer's position and advance the writer. At the end, the first writer items are the unique values.

Write dedupe(sorted_nums) that rearranges the list so its first part holds the unique values in order, and returns how many there are. The point is to practise the reader-and-writer method rather than build a new list or use a set.

nums = [1, 1, 2, 3, 3, 3]
dedupe(nums)  ->  3     and nums now starts [1, 2, 3, ...]

def dedupe(sorted_nums):
    ...

Move the zeros to the end

Rearrange a list so every zero is at the end and the other values keep their order, without making a new list. Use a writer position: walk the list with a reader, and every time the reader finds a non-zero value, put it at the writer's position and advance the writer. When the reader is done, fill from the writer to the end with zeros.

Write move_zeros(nums) that modifies the list in place and returns it.

move_zeros([0, 1, 0, 3, 12])  ->  [1, 3, 12, 0, 0]

def move_zeros(nums):
    ...

Squares of a sorted list

A sorted list may contain negatives, so squaring the values does not keep them sorted: [-3, 1, 2] squares to [9, 1, 4]. The largest square is always at one of the two ends of the original. Use a position at each end, compare their squares, write the larger into the last free slot of the result, and move that position inward. Fill the result from the back.

Write sorted_squares(nums) that returns a new sorted list of the squares. The point is to practise filling from both ends rather than call sort or sorted.

sorted_squares([-4, -1, 0, 3, 10])  ->  [0, 1, 9, 16, 100]

def sorted_squares(nums):
    ...

Merge into the first list

a is a sorted list that has extra zeros at the end: exactly enough room for all of b, another sorted list. Merge b into a so that a ends up sorted, without making a new list. Filling from the front would overwrite values of a not yet placed, so fill from the back: compare the last real value of a with the last value of b, put the larger in the last slot, and move inward.

Write merge_into(a, m, b) where m is how many real values a has at the start, so len(a) is always m + len(b). Modify a in place and return it.

merge_into([1, 3, 5, 0, 0], 3, [2, 4])  ->  [1, 2, 3, 4, 5]

def merge_into(a, m, b):
    ...

Rotate a list by k

Rotating [1, 2, 3, 4, 5] right by 2 gives [4, 5, 1, 2, 3]. It can be done in place with three reversals: reverse the whole list, then reverse the first k items, then reverse the rest. On the example, the list goes [5, 4, 3, 2, 1], then [4, 5, 3, 2, 1], then [4, 5, 1, 2, 3].

Write rotate(nums, k) that rotates the list right by k in place and returns it. k may be larger than the list; rotating by the length brings it back to the start, so only k % len(nums) matters. The point is to practise the three reversals rather than build a new list with slicing.

rotate([1, 2, 3, 4, 5], 2)  ->  [4, 5, 1, 2, 3]
rotate([1, 2, 3], 4)        ->  [3, 1, 2]

def rotate(nums, k):
    ...

Range sums with a prefix table

Many questions of the form "what is the total of items i to j" can be answered from one precomputed table. Build prefix where prefix[0] is 0 and prefix[i] is the sum of the first i items. Then the sum of items from position i up to and including j is prefix[j + 1] - prefix[i].

Write range_sums(nums, queries) where each query is a tuple (i, j) with 0 <= i <= j < len(nums). Return the list of answers. The point is to build the prefix table once rather than re-add the items for every query.

range_sums([2, 4, 6, 8], [(0, 1), (1, 3), (2, 2)])  ->  [6, 18, 6]

def range_sums(nums, queries):
    ...

Best run of days

Daily profits can be negative. Find the largest total over any run of consecutive days (at least one day). One method: walk the days keeping a running total of the current run. For each day, in this order: add the day to the running total; if the running total is now the best seen so far, remember it; then, if the running total is below zero, reset it to zero, because a negative run can only hurt whatever comes next. Because a run must have at least one day, start best at the first day's profit, not at zero, so that an all-negative list still gives the least bad day.

Write best_run(profits) for a non-empty list.

best_run([-2, 1, -3, 4, -1, 2, 1, -5, 4])  ->  6     (4 - 1 + 2 + 1)
best_run([-3, -1, -2])                     ->  -1

def best_run(profits):
    ...

Longest stretch without repeats

Find the length of the longest stretch of a string with no repeated characters. Keep a window [left, right] and a set of the characters in it. Move right one step at a time; if the new character is already in the set, move left rightwards, removing characters from the set, until it is not. The window is then valid again; record its length.

Write longest_unique(text).

longest_unique("abcabcbb")  ->  3
longest_unique("bbbbb")     ->  1
longest_unique("")          ->  0

def longest_unique(text):
    ...

Most water between two walls

heights lists the heights of vertical walls at positions 0, 1, 2, and so on. Pick two walls; the water they could hold between them is the distance between them times the shorter wall's height. Find the most water any pair can hold. Start with the two outermost walls. Moving inward makes the pair narrower, so a narrower pair can only hold more if its shorter wall is taller than the current shorter wall. Keeping the current shorter wall can never help, so move that wall's position inward and try again. Stop when the positions meet.

Write most_water(heights) for a list with at least two walls.

most_water([1, 8, 6, 2, 5, 4, 8, 3, 7])  ->  49
most_water([1, 1])                       ->  1

def most_water(heights):
    ...

That is the end of the course. If you solved all 120 without help, you can write Python. Go back to any you skipped, and then build something of your own.