Precompute once, then answer
The slowest habit in a timed test is redoing the same work for every question: calling max(heights[i + 1:]) inside a loop, or sum(1 for p in prices if p < b) for each customer.
Ask: what does this loop recompute that never changes? Move it out, build it once, and let the loop only look things up. Common precomputes:
- a running max, min or sum (one pass, then read it at any index),
- a sorted copy plus
bisectto count values below a threshold, - a dict or set instead of searching a list,
- prefix sums of two quantities (values, and value times position) when a cost splits into a left part and a right part.
cheapest = min(cheapest, p) # remembers the best so far
Building costs one pass; every later question costs about one step. The visual builds one running minimum: each entry is ready after a single comparison, and any later question about "the cheapest up to day k" is just a read.
See it run
prices = [8, 5, 9, 4, 6] cheapest = prices[0] cheapest_so_far = [] for p in prices: cheapest = min(cheapest, p) cheapest_so_far.append(cheapest)
Each pass keeps the lowest price seen so far.
Practice precompute once, then answer
Exercise 1
A lookout post records the cloud ceiling height each hour: heights. For every hour, report the highest ceiling recorded in any later hour. The last hour has no later hour and reports -1. Return the list of reports. An empty list gives [].
Constraints: 0 ≤ len(heights) ≤ 10^5, 0 ≤ heights[i] ≤ 10^9.
Example: solution([4, 9, 2, 7, 3]) returns [9, 7, 7, 3, -1].
Exercise 2
A bakery lists the price of each item in prices. Customers arrive with budgets in budgets. For each budget, count the items that cost strictly less than it (an item priced exactly at the budget does not count). Return a list with one count per budget, in order. No budgets gives [].
Constraints: 1 ≤ len(prices) ≤ 10^5, 0 ≤ len(budgets) ≤ 10^5, 1 ≤ prices[i], budgets[i] ≤ 10^9.
Example: solution([5, 2, 8, 2], [3, 2, 9, 1]) returns [2, 0, 4, 0].
Exercise 3
A street has blocks numbered 0 to n - 1, and crowd[i] people live on block i. A food truck parks on exactly one block. Each person walks |i - j| blocks to the truck, where i is their block and j is the truck's block. Return the smallest possible total walking distance (added over all people) over every block where the truck could park.
Constraints: 1 ≤ len(crowd) ≤ 10^5, 0 ≤ crowd[i] ≤ 1000.
Example: solution([2, 0, 0, 5, 1]) returns 7. Parking on block 3 costs 2 3 + 5 0 + 1 * 1 = 7, and no other block is cheaper.
The explanation and tasks are public. Running this lesson requires an account with course access.
Practice
Loading Python…Visualizer Watch your code run line by line
Run your code, then choose Play to follow its execution.