Choose the approach from the limits
Read the constraints before the code. A rough guide for Python in a test is about 10 million simple steps per second (the browser here is slower still).
- n ≤ 1,000: a double loop is about a million steps. Fine.
- n ≤ 10^5: a double loop is about 10 billion steps and will time out. You need roughly
norn log n: one pass, a dict, a prefix array, or sort plusbisect. - n ≤ 20: even trying every subset is fine.
When two limits are large (say n items and m queries), the slow version usually costs n times m. Ask what you can remember so each item and each query costs one step.
Range updates are the mirror image of range queries. Instead of adding to every slot in a range, mark +amount at the start and -amount just past the end in a difference array, then take one running total at the end.
In the visual, count how many pairs a double loop visits for 6 items, then scale it to 10^5.
See it run
n = 6 pair_steps = 0 for i in range(n): for j in range(i + 1, n): pair_steps = pair_steps + 1
Every item is paired with each item after it.
Practice choose the approach from the limits
Exercise 1
A garden strip has n plots numbered 0 to n - 1, all starting dry (level 0). Each sprinkler run [first, last, amount] adds amount litres to every plot from first to last, both included. Return a list with the final level of every plot after all runs.
Constraints: 1 ≤ n ≤ 10^5, 0 ≤ len(runs) ≤ 10^5, 0 ≤ first ≤ last < n, 1 ≤ amount ≤ 1000.
Example: solution(5, [[1, 3, 2], [2, 4, 1]]) returns [0, 2, 3, 3, 1].
Exercise 2
A trail has markers at elevations heights, in walking order. Count the pairs of markers at positions i < j where the later marker is exactly climb metres higher: heights[j] - heights[i] == climb. climb can be 0, which counts pairs of equal elevations. A marker never pairs with itself.
Constraints: 0 ≤ len(heights) ≤ 10^5, 0 ≤ heights[i] ≤ 10^9, 0 ≤ climb ≤ 10^9.
Example: solution([3, 5, 8, 5, 10], 2) returns 3: (3, 5), (3, 5 again) and (8, 10). solution([5, 3, 5], 2) returns 1: only the 3 followed by the last 5.
Exercise 3
A ferry takes exactly two passengers at a time. Given the passenger weights weights (kg), count the pairs of different passengers (positions i < j) whose combined weight is at least low and at most high. Both limits are included.
Constraints: 0 ≤ len(weights) ≤ 10^5, 1 ≤ weights[i] ≤ 10^6, 0 ≤ low ≤ high ≤ 2 * 10^6.
Example: solution([50, 70, 40, 60], 100, 120) returns 4: 50 + 70 = 120, 50 + 60 = 110, 70 + 40 = 110 and 40 + 60 = 100. The pairs 50 + 40 = 90 and 70 + 60 = 130 fall outside.
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.