Speed by experiment

A solution can be right and still too slow. Estimate the work by counting steps:

One loop over n items: about n steps.
A loop inside a loop: about n * n steps. For 1,000 items that is 1,000,000.
x in some_list scans the list. x in some_set is one quick lookup.

So when you catch yourself comparing every item with every other item, ask what you could remember instead: a set of what you have seen, or a dict of counts. Sometimes there is a formula and no loop at all.

Submit also runs a speed test on a large input. If it says you were too slow, the answer is probably right and the approach is the problem.

See it run

nums = [3, 8, 5]
steps = 0
for a in nums:
    for b in nums:
        steps = steps + 1
print(steps)

Count the inner-loop passes. Every number is paired with every number.

Practice speed by experiment

Exercise 1

Write solution(nums, target) returning True if two numbers at different positions in nums add up to target, else False. The same position cannot be used twice, but two equal values at different positions can. For example, solution([1, 4, 6], 10) is True (4 + 6), solution([5, 3], 10) is False, and solution([2, 2], 4) is True. nums can hold thousands of numbers, so checking every pair is too slow.

Exercise 2

Write solution(words) returning the first word that has already appeared earlier in the list, scanning from the left. If no word repeats, return None. Upper and lower case are different words. For example, solution(["p", "q", "q", "p"]) is "q" (its repeat comes before the repeat of "p"), and solution(["x", "y"]) is None.

Exercise 3

A pyramid has 1 stone in its top row, 2 in the next, 3 in the next, and so on. Write solution(n) returning the total number of stones in a pyramid of n rows. n is zero or more and can reach 10 to the power 7, so counting stone by stone is too slow. For example, solution(4) is 10 and solution(0) is 0. Return a whole number.

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