Merging sorted lists

When two lists are already sorted, you do not need to sort again. Keep one pointer in each list and always take the smaller front item.

i = j = 0
while i < len(a) and j < len(b):
    if a[i] <= b[j]:
        out.append(a[i]); i += 1
    else:
        out.append(b[j]); j += 1
out += a[i:] + b[j:]          # one list ran out: add the rest

Each item is looked at once, so the cost is len(a) + len(b). The same two-pointer walk finds items common to both lists: advance whichever side is smaller, and act when the fronts are equal.

Ties matter. The <= above means "on a tie take from a first". If the statement says which list wins a tie, that comparison is where you encode it.

In the visual, i and j are the two fronts. Notice that one list ends first and the loop stops with items left over.

See it run

a = [1, 4, 9]
b = [2, 3, 10]
out = []
i = 0
j = 0
while i < len(a) and j < len(b):
    if a[i] <= b[j]:
        out.append(a[i])
        i += 1
    else:
        out.append(b[j])
        j += 1

Two sorted lists, two pointers. Each pass copies the smaller front item into out.

Practice merging sorted lists

Exercise 1

Two sensors each keep a log of events as [minute, name] pairs, sorted by minute (earliest first). Write solution(log_a, log_b) to merge them into one timeline and return the event names in time order.

Rules:

Earlier minutes come first.
If two events share the same minute, the one from log_a comes before the one from log_b.
Events within one log keep their given order, even when minutes repeat.
Either log may be empty. Return a list of strings.

Constraints: 0 ≤ len(log_a), len(log_b) ≤ 10^4; minutes are integers from 0 to 10^6.

Example: solution([[1, "x"], [5, "y"]], [[1, "p"], [3, "q"]]) returns ["x", "p", "q", "y"]: at minute 1 the event from log_a goes first.

Exercise 2

Two clubs each keep a sorted (smallest first) list of member ids; an id can appear more than once in a list. Write solution(ids_a, ids_b) to return the ids that appear in both lists.

Rules:

Return a list in ascending order.
Each shared id appears once in the result, however often it repeats in the inputs.
If nothing is shared, return [].

Constraints: 0 ≤ len(ids_a), len(ids_b) ≤ 10^5; ids are integers from 0 to 10^9. Both inputs are already sorted ascending.

Example: solution([1, 2, 2, 4, 7], [2, 2, 3, 7, 9]) returns [2, 7].

Exercise 3

Two cleaners each have a list of busy shifts as [start, end] minutes, meaning busy from start up to but not including end. Within one list the shifts are sorted by start and never overlap each other. Write solution(shifts_a, shifts_b) to return the total number of minutes when both cleaners are busy at the same time.

Rules:

Shifts that only touch (one ends at the minute the other starts) share 0 minutes.
Return an integer; either list may be empty.

Constraints: 0 ≤ len(shifts_a), len(shifts_b) ≤ 10^4; 0 ≤ start < end ≤ 10^9. Your solution must be fast on 10^4 shifts each.

Example: solution([[1, 5], [8, 12]], [[3, 9], [11, 20]]) returns 4: both are busy during [3, 5) = 2 minutes, [8, 9) = 1 minute and [11, 12) = 1 minute.

The explanation and tasks are public. Running this lesson requires an account with course access.

Practice

Loading Python…

Loading exercise content…

Visualizer Watch your code run line by line

Run your code, then choose Play to follow its execution.

Memory · names → values

Variables appear here as Python creates them.

Output & plots