Linear pass thinking and hidden costs of built-ins

Many problems can be solved by walking through the data one time, keeping track of what you have seen so far. This one-pass strategy is often the fastest way. Built-in functions like count(), index(), and sort() are convenient, but they hide work. Understanding what they do helps you write faster code.

One pass vs. multiple searches

Suppose you have a list of numbers and need to find the maximum and minimum. A naive approach is to search for the maximum, then search again for the minimum. That is two passes.

A smarter approach is to keep track of both in a single pass:

1numbers = [3, 1, 4, 1, 5, 9]2min_val = numbers[0]3max_val = numbers[0]4
5for num in numbers:6    if num < min_val:  # noqa: PLR1730 (spelled out on purpose, not `min()`/`max()`)7        min_val = num8    if num > max_val:  # noqa: PLR17309        max_val = num10
11print(min_val, max_val)

This visits each number once. The two-loop approach visits each number twice. One pass is twice as fast.

Hidden costs in built-in functions

The index() method finds the first position of a value in a list. It scans the list from the start, one element at a time, until it finds a match. If the value is at the end, index() scans the entire list.

numbers = [1, 2, 3, 4, 5]pos = numbers.index(5)  # Scans all 5 elements

If you call index() many times, the cost adds up. Each call scans part or all of the list. Doing this in a loop can turn a problem that should run fast into one that runs slow.

1numbers = list(map(int, input().split()))2seen = set()3first_dup = -14
5for num in numbers:6    if num in seen:7        first_dup = num8        break9    seen.add(num)10
11print(first_dup)

1 2 3 2 4 5

2

This program checks each number to see if it has been seen before. A set remembers what you have already read, and in checks membership in close to constant time regardless of how many numbers the set holds. There is no repeated scanning: the set grows as you iterate, but each membership check stays fast.

The hidden cost of index() is that it searches the entire list every time you call it. If you search for ten different values, you pay the cost ten times. A set trades a small amount of memory for instant lookups, making the total time linear instead of quadratic.

Why tracking state matters

When you keep track of information as you scan, you avoid repeating work. Think about finding the maximum value in a list. The naive way uses max(numbers), which works fine. But if you loop through to find the maximum and then loop again to find something else, you have wasted the first loop.

A better approach is to calculate everything you need in one pass. Keep running variables for maximum, minimum, sum, count, or anything else you need. Update them as you go. At the end of the loop, you have all your answers without re-scanning the data.

This idea scales. If a problem asks "find the maximum value that appears more than once", you can do it in one pass by tracking both a seen set and a running maximum. Problems that look like they need multiple scans often collapse to one pass if you think carefully about the state you need to track.

Another example: finding a pair

Suppose you have a sorted list and need to find two numbers that add up to a target sum. The naive way searches for each number with index():

1numbers = [1, 2, 3, 5, 7]2target = 83
4found = False5for num in numbers:6    complement = target - num7    if complement in numbers:  # This searches the list8        print(num, complement)9        found = True10        break

Using in on a list searches it. For a large list, this is slow. A smarter approach uses two pointers:

1numbers = [1, 2, 3, 5, 7]2target = 83
4left = 05right = len(numbers) - 16
7while left < right:8    sum_val = numbers[left] + numbers[right]9    if sum_val == target:10        print(numbers[left], numbers[right])11        break12    elif sum_val < target:13        left += 114    else:15        right -= 1

This scans the list once with two pointers moving toward each other. No searching, no repeated passes. The technique works because the list is sorted. As you move the pointers, the sum changes predictably.

Two pointers on sorted data

If data is sorted, you can use two pointers to solve problems in one pass. Start with one pointer at the beginning and one at the end. Move them toward each other based on what you find.

This technique is especially useful for finding pairs or ranges that meet a condition. Two pointers let you avoid nested loops and stay fast.

Time complexity intuition

An algorithm that visits each element a constant number of times is O(n). An algorithm that searches for each element is O(n²) or worse. The difference grows fast as n increases.

For n = 100, O(n) is 100 steps and O(n²) is 10,000 steps. For n = 10,000, O(n) is 10,000 steps and O(n²) is 100 million steps. Avoid repeated searching when a single pass will do.

Common mistakes

One mistake is calling a built-in that searches the list inside a loop. This creates nested loops even if the code looks simple. Before using a method that searches, ask yourself whether you can solve it in one pass instead.

Another mistake is sorting data and then searching it repeatedly, when a set or dictionary would track items faster.

A third mistake is assuming built-ins are always optimal. They are convenient and correct, but sometimes a custom loop that tracks state is faster.

Think in terms of passes through the data. One pass is fast. Many passes, even ones hidden inside an innocent-looking method call, are slow, and the slowdown only shows up once the input is large enough to matter.