Arrays, Lists & Matrices

Arrays, Lists & Matrices | Algoryva

Worked by hand

Reading an array by hand

Take a = [10, 20, 30, 40, 50]. Every item has two names: a positive index counting from the left and a negative index counting from the right.

position	first	second	third	fourth	fifth
positive index	0	1	2	3	4
negative index	-5	-4	-3	-2	-1
value	10	20	30	40	50

1
a[3]
Index 3 is the fourth slot, so the value is 40. The index is one less than the “position” you would say aloud.
2
a[-2]
Second from the right: also 40. a[3] and a[-2] are the same slot, since -2 + 5 = 3.
3
a[1:4]
Start at index 1, stop before index 4: indices 1, 2, 3, giving [20, 30, 40]. The length is 4 − 1 = 3.
4
a[5]
There is no index 5 in a list of five items; Python raises an IndexError. The last valid index is always len(a) - 1.

Implementation

Reading, changing and slicing

Every one of these appears constantly. Predict each output before running it.

python

a = [10, 20, 30, 40, 50]
print(a[0], a[-1])   # 10 50
print(a[1:4])   # [20, 30, 40]
print(a[::-1])   # [50, 40, 30, 20, 10]

a[2] = 99
a.append(60)
print(a)   # [10, 20, 99, 40, 50, 60]

a[0], a[-1] = a[-1], a[0]      # swap two items
print(a)   # [60, 20, 99, 40, 50, 10]
print(len(a), sum(a), max(a))   # 6 279 99

Reading the code

›a[1:4] starts at index 1 and stops *before* index 4, so it holds indices 1, 2 and 3.
›a[::-1] is a reversed copy; the original is untouched. Contrast with a.reverse(), which reverses in place and returns nothing.
›a[0], a[-1] = a[-1], a[0] swaps without a temporary variable: the right side is evaluated first.
›sum and max each scan the whole list, so they are O(n).

Implementation

Traversal patterns

Choose the loop style that matches what you need: the values, the indices, or both.

python

a = [4, 9, 2, 7]

biggest = a[0]
for x in a:                    # values only
    if x > biggest:
        biggest = x

where = 0
for i in range(len(a)):        # indices
    if a[i] > a[where]:
        where = i

for i, x in enumerate(a):      # both together
    pass

print(biggest, where)   # 9 1
print(list(range(len(a) - 1, -1, -1)))   # [3, 2, 1, 0]

Reading the code

›Use for x in a when you only need values, range(len(a)) when you need to compare neighbours or write back, and enumerate for both.
›Starting biggest at a[0] (not 0) keeps the code correct when all values are negative. It does require a non-empty list.
›range(n - 1, -1, -1) walks the indices backwards: start at the last index, stop *before* -1, step -1.

Implementation

Counting how often things occur

A dictionary maps each distinct item to its count, turning a repeated search into one pass.

python

def frequencies(items):
    freq = {}
    for x in items:
        freq[x] = freq.get(x, 0) + 1
    return freq

print(frequencies("banana"))   # {'b': 1, 'a': 3, 'n': 2}
print(frequencies([3, 1, 3, 3]))   # {3: 3, 1: 1}

Reading the code

›freq.get(x, 0) returns the current count, or 0 the first time x appears.
›One pass, O(n) time, O(distinct items) space. Counting this way is the basis of many “anagram”, “majority” and “duplicate” problems.
›collections.Counter does exactly this in one call; write it by hand once so you know what it does.

Implementation

Matrices: lists of lists

A matrix is a list of rows. m[r][c] is the item in row r, column c. There is one trap every learner meets: building rows with multiplication.

python

bad = [[0] * 3] * 2            # two names for the SAME row
bad[0][0] = 1
print(bad)   # [[1, 0, 0], [1, 0, 0]]

good = [[0] * 3 for _ in range(2)]   # a fresh row each time
good[0][0] = 1
print(good)   # [[1, 0, 0], [0, 0, 0]]

m = [[1, 2, 3], [4, 5, 6]]
print(len(m), len(m[0]))   # 2 3
print([list(col) for col in zip(*m)])   # [[1, 4], [2, 5], [3, 6]]

Reading the code

›[[0] * 3] * 2 copies the *reference* to one row, so both rows are the same object. Changing one changes both. The list comprehension builds a new row for each iteration.
›len(m) is the number of rows and len(m[0]) the number of columns (assuming the matrix is not empty).
›zip(*m) groups the first items of every row, then the second, and so on: that is the transpose.

Worked problem

Two numbers that add up to a target

The problem

Given a list of integers and a target, return the indices of two *different* items whose values sum to the target. Exactly one answer exists.

Brute force checks all pairs: O(n²).
For each value x, the partner we need is target − x. If we have already seen that partner, we are done.
Keep a dictionary from value to index of everything seen so far; one pass, O(n).

python

def two_sum(a, target):
    seen = {}
    for i, x in enumerate(a):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

print(two_sum([2, 7, 11, 15], 9))   # [0, 1]
print(two_sum([3, 2, 4], 6))   # [1, 2]

Takeaway. Replacing “search the rest of the list” (O(n)) with “look it up in a dictionary” (O(1)) turns O(n²) into O(n). We check for the partner *before* storing the current item, so an item is never paired with itself.

Worked problem

Rotate an array

The problem

Rotate a list to the right by k places. For [1, 2, 3, 4, 5, 6, 7] and k = 3 the result is [5, 6, 7, 1, 2, 3, 4].

Rotating right by k moves the last k items to the front.
If k is larger than the length, rotating by n is a full circle that changes nothing, so use k % n.
Guard against an empty list to avoid dividing by zero.

python

def rotate(a, k):
    if not a:
        return a
    k %= len(a)
    if k == 0:
        return a[:]
    return a[-k:] + a[:-k]

print(rotate([1, 2, 3, 4, 5, 6, 7], 3))   # [5, 6, 7, 1, 2, 3, 4]
print(rotate([1, 2, 3], 4))   # [3, 1, 2]
print(rotate([], 5))   # []

Takeaway. Reduce the problem first (k %= n), then handle the special case (k == 0, since a[-0:] would be the whole list). Most array bugs live in these small edges.

Wrap-up

Remember this

An array gives instant access by index but slow insertion or deletion away from the end.
Python indices start at 0; a slice excludes its end; negative indices count from the back.
Choose between values, indices or enumerate when looping, and watch the boundaries.
Build matrices with a comprehension, and remember b = a does not copy.
Dictionaries count frequencies and replace inner searches, turning O(n²) into O(n).

Cheat sheet

Indices: 0 … n−1; a[-1] is the last
Slice: a[l:r] excludes r; length r − l; makes a copy
O(1): a[i], a[i] = x, append, pop(), len
O(n): x in a, insert/pop at the front, sum, max, slice
Matrix: [[0] * c for _ in range(r)] (never [[0]*c]*r)
Count: freq[x] = freq.get(x, 0) + 1

Top traps to avoid

Off-by-one: using range(1, n) when you meant range(n), or <= when you meant <.
Building a matrix with [[0] * c] * r.
Using a.pop(0) or a.insert(0, x) in a loop.

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.For a = [10, 20, 30, 40, 50], what is a[1:4]?
2.What is the cost of a.pop(0) on a list of n items, and why?
3.After bad = [[0] * 3] * 2; bad[0][0] = 1, what does bad look like?
4.Which task is a good fit for a frequency dictionary?
5.rotate([1, 2, 3], 4) returns:
6.Why is b = a not a copy of a list?
7.For a = [1, 2, 3, 4, 5], what is a[-2:]?
8.For a = [1, 2, 3], what does a.insert(1, 9) leave in a?
9.What does this print? for i, v in enumerate(['a', 'b']): print(i, v)
10.Which operation on a Python list takes the same time whatever its length?
11.a = [1, 2, 3]; a[1:1] = [9]. What does print(a) print?
12.a = [0] * 3; a[0] = 1. What does print(a) print?
13.grid = [[0] * 2] * 2; grid[0][0] = 5. What does print(grid) print?
14.a = [5, 6]. What does print(a.index(6), 6 in a) print?
15.What is the time to read a[i] in a Python list?

Arrays, Lists & Matrices

After this lesson you will be able to

A row of lockers

Indices and operations

Indices and swaps: reverse in place

Reading an array by hand

Reading, changing and slicing

Reading the code

Traversal patterns

Reading the code

Counting how often things occur

Reading the code

Matrices: lists of lists

Reading the code

What each operation costs and why

Edge cases

Mistakes to avoid

How to spot an array problem

Two numbers that add up to a target

Rotate an array

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up2 problems

Core53 problems

Application4 problems

Challenge1 problem