Built-ins, Classes & Iterators

Built-ins, Classes & Iterators | Algoryva

Intuition

A well-stocked toolbox

You can drive a nail with a rock, but a hammer is faster, safer and every carpenter recognises it. Python ships with a toolbox of small, well-tested functions for jobs you meet constantly: adding things up, finding the biggest, sorting, pairing lists together.

Using them makes code shorter, less likely to contain off-by-one errors, and easier for others (and you, next week) to read.

First, the naive way

Writing every loop by hand

Without the toolbox, even small jobs become index juggling: finding the largest item *and where it is*, or pairing two lists, each needs a counter, a bound check and an update.

Every one of those lines is a chance for an off-by-one error (range(1, len(a)) or len(a) - 1?). The built-ins do the same work with the loop already written and tested.

python

def my_max_with_index(a):
    best, where = a[0], 0
    for i in range(1, len(a)):
        if a[i] > best:
            best, where = a[i], i
    return best, where

names = ["ana", "ben", "cy"]
scores = [90, 85, 72]
i = 0
pairs = []
while i < len(names):
    pairs.append((names[i], scores[i]))
    i += 1

print(my_max_with_index([4, 9, 2, 9]))   # (9, 1)
print(pairs)   # [('ana', 90), ('ben', 85), ('cy', 72)]

Cost: Same speed, but more code, more places for index bugs, and harder to read.

The concept

The built-ins worth knowing

Most work on any iterable: anything you can loop over (lists, tuples, strings, sets, dictionaries, range, files).

Aggregates: len, sum, min, max. max(a, key=f) picks the item with the largest f(item); min([], default=-1) avoids an error on empty input.
Ordering: sorted(a, key=..., reverse=...) returns a new list; reversed(a) walks backwards (wrap in list(...) to see it).
Pairing and numbering: enumerate(a, start=1) gives (index, item); zip(a, b) gives pairs and stops at the shorter one.
Transform and test: map(f, a) applies f; filter(f, a) keeps items where f is true; any(...) and all(...) ask “is at least one / every item true?”.
Numbers: abs, divmod(a, b) (quotient and remainder together), pow(a, b, m) (modular power), round.
Iterator vs list: map, filter, zip, enumerate and reversed return lazy iterators; wrap in list(...) to materialise them.

See it move

zip: walking two lists in step

zip pairs the items at the same position and hands them out one pair at a time. Step through and watch the highlighted pair move along both lists together. Because zip stops at the shorter list, unequal lengths never cause an error.

Worked by hand

Choosing the right tool

Each row is a task you would otherwise write a loop for.

task	one-liner	replaces
total of a list	sum(a)	an accumulator loop
position and item	for i, x in enumerate(a)	`range(len(a))` plus `a[i]`
pair two lists	zip(names, scores)	an index loop over both
longest word	max(words, key=len)	tracking best and best length
any negative?	any(x < 0 for x in a)	a flag variable and a `break`
count of each item	Counter(a)	a dictionary-and-`get` loop

1
A pattern in the right column
Every “replaces” entry is a loop with a small piece of state. The built-in packages that state so you cannot get it wrong.
2
is the powerful parameter

Implementation

The built-ins in action

Predict each result before reading the comment. Notice how often the answer needs list(...) to display.

python

a = [4, 9, 2, 7]
print(len(a), sum(a), min(a), max(a))   # 4 22 2 9
print(sorted(a), list(reversed(a)))   # [2, 4, 7, 9] [7, 2, 9, 4]
print(max(a, key=lambda x: -x))   # 2
print(list(enumerate(["a", "b"], start=1)))   # [(1, 'a'), (2, 'b')]
print(list(zip([1, 2, 3], "ab")))   # [(1, 'a'), (2, 'b')]
((([, ], [, ])))   
(((str, [, , ])))   
((( x: x > , a)))   
((x >   x  a), (x >   x  a))   
((, ), (-), (, , ))   
((, ), (), ())   
(([], default=-))

Implementation

Iterators and generators

An iterator hands out items one at a time with next(), remembering where it is. A generator is an iterator you write with yield, or with an expression in parentheses. Neither builds the whole sequence in memory.

python

it = iter([10, 20, 30])
print(next(it), next(it))   # 10 20
print(list(it))   # [30]
print(list(it))   # []

def countdown(n):
    while n > 0:
        yield n
        n -= 1

print(list(countdown(3)))   # [3, 2, 1]
total = sum(x * x for x in range(1, 1001))
print(total)   # 333833500
gen = (x * 2 for x in ())
((gen), (gen), (gen))   
((gen, ))

Implementation

A first class

A class bundles data with the functions that work on it. __init__ runs when you create an object; methods take self (the object itself) as their first parameter. Special “dunder” methods let your class work with built-ins: __len__ powers len(obj), __repr__ controls how it prints.

python

class Stack:
    def __init__(self):
        self.items = []

    def push(self, x):
        self.items.append(x)

    def pop(self):
        return self.items.pop()

    def __len__(self):
        return len(self.items)

    def __repr__(self):
        return f"Stack({self.items})"

s = Stack()
s.push(1)
s.push(2)
print(s)   # Stack([1, 2])
print(s.pop(), len(s))   # 2 1
print(((s)))

Complexity

What the built-ins cost

len

time O(1)space O(1)

Containers store their size.

sum, min, max, any, all

time O(n)space O(1)

They scan the items once. any/all stop early when the answer is decided.

sorted

time O(n log n)space O(n)

A comparison sort on a new list.

enumerate, zip, map, filter, reversed

time O(1) to create, O(n) to consumespace O(1)

They are lazy: nothing happens until you iterate.

list(zip(a, b)) and other materialisation

time O(n)space O(n)

Building the list copies every pair.

Generator expression vs list comprehension

time samespace O(1) vs O(n)

Edge cases

min / max of an empty sequenceRaises ValueError. Pass default=... or check emptiness first.
zip with lists of different lengthsIt silently stops at the shorter one. Use itertools.zip_longest if you need every item.
Using an iterator twiceThe second pass sees nothing. Convert to a list first if you need two passes.
map/filter results printed directlyprint(map(...)) shows an object, not the values. Wrap in list(...).
round on halvesPython rounds to the nearest even number, so round(2.5) is 2. Do not use it to “round half up”.
Dictionary or set passed to sortedYou get a sorted list of the keys (or items), not a sorted dictionary.

Common mistakes

Mistakes to avoid

Looping with range(len(a)) when you only need the items.
Write for x in a. Use enumerate when you need the index too.
Printing a map, zip or filter and wondering what the output means.
They are lazy. Wrap in list(...).
Consuming an iterator and then reusing it.
Store the results in a list if you need them again.
Writing max(a) when you wanted the *index* of the maximum.
Use max(range(len(a)), key=lambda i: a[i]), or a.index(max(a)).
Forgetting self in a method definition or call.

Recognize it in a contest

How to spot a built-in opportunity

Reach for it when the problem says or implies

You are about to write a loop whose only job is to add up, count, find the biggest or smallest, or check a condition.
You need to walk two lists together, or number items while looping: zip and enumerate.
A problem asks you to count occurrences or compare multisets of letters or numbers: Counter.
You need the smallest, largest or best item by some measure: min/max/sorted with key=.
You are processing a huge stream and cannot afford a full list in memory: a generator expression.

Look elsewhere when

Worked problem

Fewest changes to make two strings anagrams

The problem

Strings s and t have equal length. In one step you may replace any character of t with any other. Return the minimum number of steps to make t an anagram of s.

Two strings are anagrams when each letter appears equally often in both.
Count the letters in each string. Counter(s) - Counter(t) keeps only the letters s has more of than t.
Each surplus letter in s must be matched by one replacement in t, so the answer is the total of those surpluses.

python

from collections import Counter

def min_steps_anagram(s, t):
    diff = Counter(s) - Counter(t)
    return sum(diff.values())

print(min_steps_anagram("bab", "aba"))   # 1
print(min_steps_anagram("leetcode", "practice"))   # 5
print(min_steps_anagram(, ))

Worked problem

The majority element

The problem

A list has a value that appears more than half the time. Return that value.

Count how often each value appears with Counter.
most_common(1) returns a list holding the single most frequent (value, count) pair.
Take the value from the first pair: [0][0].

python

from collections import Counter

def majority(a):
    return Counter(a).most_common(1)[0][0]

print(majority([3, 2, 3]))   # 3
print(majority([2, 2, 1, 1, 1, 2, 2]))   # 2

Takeaway. Counter(a).most_common(1)[0][0] reads inside out: count, take the top one, take its pair, take its value. It is O(n) time and O(distinct values) memory. (A trick called Boyer–Moore voting does it in O(1) memory, a good follow-up once the basics feel natural.)

Wrap-up

Remember this

Python's built-ins replace common loops with shorter, tested code: sum, min, max, sorted, enumerate, zip, any, all.
key= on sorted, min and max says what to compare by.
map, filter, zip and enumerate are lazy iterators: wrap in list(...) to see them, and note they are used up once consumed.
A generator produces values one at a time and keeps memory flat.
Classes bundle data and methods; dunder methods like __len__ and __repr__ connect them to built-ins.

Cheat sheet

Aggregates: len · sum · min · max (key=, default=)
Ordering: sorted(a, key=f, reverse=True) · reversed(a)
Pairing: enumerate(a, start=1) · zip(a, b) (stops at shorter)
Lazy: map, filter, zip, enumerate, reversed → wrap in list()
Tests: any(...) · all(...)
Counting: Counter(a) · most_common(k) · Counter(a) - Counter(b)

Top traps to avoid

Looping with range(len(a)) when you only need the items.
Printing a map, zip or filter and wondering what the output means.
Consuming an iterator and then reusing it.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What does list(zip([1, 2, 3], "ab")) return?
2.What happens if you call list(it) twice on the same iterator?
3.max(["pear", "fig", "banana"], key=len) returns:
4.Why is sum(x * x for x in range(1000000)) friendlier to memory than sum([x * x for x in range(1000000)])?
5.“Count how many of each letter appear in a string” suggests:
6.What does round(8.5) return in Python?
7.What does sorted([3, 1, 2], reverse=True) return?
8.What does list(zip([1, 2], 'ab')) give?
9.What does list(map(str, [1, 2])) give?
10.What does an __init__ method do?
11.What does print(max([3, 1, 4], key=lambda x: -x)) print?
12.s = 0 for _ in range(10): s += 0.1 What does print(s == 1.0) print?
13.What does print(list(filter(lambda x: x > 1, [1, 2, 3]))) print?
14.What does print(any([]), all([])) print?
15.What does zip do when its input lists have different lengths?

key=

Built-ins, Classes & Iterators

After this lesson you will be able to

Builds on

Unlocks

A well-stocked toolbox

Writing every loop by hand

The built-ins worth knowing

zip: walking two lists in step

Choosing the right tool

The built-ins in action

Iterators and generators

A first class

What the built-ins cost

Edge cases

Mistakes to avoid

How to spot a built-in opportunity

Fewest changes to make two strings anagrams

The majority element

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up1 problem

Core3 problems

Application2 problems

Reading the code

Reading the code

Reading the code