Array Foundations

8 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

A List Is a Row of Numbered Boxes

A list is a row of boxes standing side by side, and each box holds one value. Python writes a list with square brackets: coins = [12, 7, 9, 4, 15]. Picture a row of five lockers, where the number inside each locker is how many coins it holds. Every box has a number called its index, which is its position in the row. The first box has index 0, not 1, because the index counts how many boxes you skip to reach it, and for the first box you skip none. So coins[0] is 12, coins[1] is 7, coins[2] is 9, coins[3] is 4 and coins[4] is 15. The function len(coins) tells you how many boxes there are: 5. So the last box is at index len(coins) - 1, which is 4. Python can also count from the back: coins[-1] is the last box (15) and coins[-2] is the one before it (4). To change a box, put it on the left of an equals sign: coins[2] = 10 replaces the 9 with 10. Asking for a box that does not exist, such as coins[5], stops the program with an IndexError. An empty row is written [] and has len 0. Many people say array for a list; here the two words mean the same thing.

The intuition

The odd-looking start at 0 makes sense when you think of the index as a distance from the start of the row. The first box is 0 steps from the start, the second box is 1 step away, and so on. That also explains why the last index is one less than the length: five boxes sit at distances 0, 1, 2, 3 and 4. Because every box has a fixed address, Python never has to look through the row to find coins[3]; it goes straight there. So reading or changing a box by its index takes one step, whether the row has 5 boxes or 5 million. Everything else in this lesson builds on that one fact: you can jump straight to any numbered box.

A real-world analogy

Think of a row of lockers in a school corridor. Each locker has a number painted on its door, starting at 0, and holds one thing. The row is the list, each locker is a box, the number on the door is the index and what is inside is the value. If someone says open locker 3, you walk straight to it. Opening locker 5 in a corridor that only has lockers 0 to 4 is the IndexError: that door does not exist. Swapping two lockers means taking both things out first, then putting each one into the other locker.

coins = [12, 7, 9, 4, 15]            # five lockers
print(len(coins))                    # 5 boxes
print(coins[0], coins[4])            # first and last: 12 15
print(coins[-1], coins[-2])          # from the back: 15 4
coins[2] = 10                        # change box 2: the 9 becomes 10
print(coins)                         # [12, 7, 10, 4, 15]
coins[0], coins[4] = coins[4], coins[0]   # swap the first and last boxes
print(coins)                         # [15, 7, 10, 4, 12]
# print(coins[5])                    # would stop with IndexError: only boxes 0 to 4 exist

Walking Through a List

To look at every box in turn, use a for loop. In for v in tickets:, the name v holds each value one after the other. Take a queue at a counter where three people hold tickets numbered tickets = [30, 10, 20]. The loop body runs three times, with v equal to 30, then 10, then 20. Sometimes you need the position as well as the value. Then loop over the indexes: range(len(tickets)) gives 0, 1, 2, and tickets[i] is the value in box i. The stop number of a range is never included, and range(1, len(tickets)) starts at 1 and gives 1, 2, skipping box 0. A shortcut gives both at once: for i, v in enumerate(tickets) hands you the index i and the value v together: (0, 30), (1, 10), (2, 20). Inside a loop, total += v is a short way to write total = total + v. To reuse a loop, wrap it in a function: def add_up(row): makes a function named add_up, and return total hands the answer back to whoever called it. One trap: in for x in tickets, x is a VALUE, not an index, so tickets[x] would look for box 30.

The intuition

A for loop is the safest way to visit every box, because Python does the counting for you and you cannot run off the end by mistake. Use the plain for v in row when only the values matter. Use range or enumerate when the answer needs a position, for example where did I see it, or compare with the box before. So the question to ask is always: do I need just the value, or the position too? Remember also that a loop over n boxes does n rounds, so it takes about n steps.

A real-world analogy

Imagine a teacher walking along a queue at a counter with a clipboard. Walking past each person and reading their ticket is the plain for loop: you see the ticket, which is the value. Saying person number 0, person number 1, person number 2 as you walk is the index, and enumerate does that numbering for you. The running total on the clipboard is total, updated after every person. Mixing up value and index is like calling out person number 30 in a queue of three just because the ticket says 30: there is no such place in the line.

def add_up(row):                   # def makes our own function
    total = 0                      # start the running total at 0
    for v in row:                  # v is each VALUE in turn
        total += v                 # same as total = total + v
    return total                   # hand the answer back
tickets = [30, 10, 20]             # three people in a queue
print(add_up(tickets))             # 60
for i in range(len(tickets)):      # i is each INDEX: 0, 1, 2
    print(i, tickets[i])           # 0 30, then 1 10, then 2 20
for i, v in enumerate(tickets):    # index and value together
    print(i, v)                    # the same three lines again
for i in range(1, len(tickets)):   # starts at 1, so box 0 is skipped
    print(i)                       # 1, then 2

Adding, Removing and Searching

Lists can grow and shrink. Our example is a belt with five slots: slots = [0, 4, 0, 9, 6], where 0 means the slot is empty. slots.append(5) adds 5 at the end. slots.pop() removes the last value and hands it back. Both touch only the end, so nothing else moves: one step each. slots.insert(0, 7) puts 7 at the front, but boxes cannot overlap, so all 5 values must first slide one place right: 5 moves. slots.pop(0) removes the first value, and all the others slide one place left to close the gap. slots.remove(0) looks for the first 0, box by box, takes it out and closes the gap the same way. To ask whether 9 is on the belt, write 9 in slots. Python has no shortcut: it looks at box 0, then box 1, and so on, until it finds 9 or runs out of boxes. To tidy a whole list without sliding values again and again, use two fingers, where a finger is just a variable holding an index. A read finger walks over every slot. A write finger marks where the next real value should go. Copy each real value to the write finger, move the write finger on, and fill the rest with 0.

The intuition

Think about what must be physically true. A list is boxes in a row with no gaps. Touching the end disturbs nobody, but touching the front forces every other value to shuffle. The cost of an operation is the number of values that must move or be looked at. With 5 slots that is nothing, but with a million, one insert at the front moves a million values. The two-finger tidy avoids all that shuffling: every value is copied at most once, straight to its final box, so tidying n slots costs about n steps instead of n steps for each removal.

A real-world analogy

Picture a packed bookshelf. Putting a book on the right-hand end disturbs nobody. Putting one at the far left means pushing every other book one place right. Taking out the leftmost book leaves a gap, and every other book slides left to close it. To find a title you scan the spines one by one. To tidy a shelf where some spots hold blank blocks, walk along with one hand reading each spot (the read finger) and keep the other hand on the next free spot at the front (the write finger): move real books forward, then blank the rest.

slots = [0, 4, 0, 9, 6]            # 5 belt slots, 0 means empty
slots.append(5)                    # add at the END: 1 step
last = slots.pop()                 # take the LAST off (gives 5): 1 step
slots.insert(0, 7)                 # add at the FRONT: all 5 values slide right
first = slots.pop(0)               # take the FIRST off (gives 7): all slide left
print(9 in slots, 8 in slots)      # True False: a box-by-box scan
write = 0                          # write finger: where the next real value goes
for value in slots:                # read finger: walks every slot
    if value != 0:                 # a real parcel
        slots[write] = value       # copy it to the write spot
        write += 1                 # move the write finger on
for i in range(write, len(slots)): # every slot from the write finger onwards
    slots[i] = 0                   # becomes empty
print(slots)                       # [4, 9, 6, 0, 0]

Counting the Work

To compare two ways of solving a problem, count the steps each takes as the list gets longer. Call the number of boxes n. Looking at every box once is a loop of n rounds: about n steps. Now imagine a hall with n students, each holding a number card, and we want to know whether any two cards match. One way: for every student a, compare with every student b. A loop inside a loop is n rounds of n rounds: n x n steps. With 4 students that is 16 steps, with 10 students it is 100, and with 100,000 students it is 10,000,000,000. If a computer does about 10 million simple steps a second (a rough figure for Python), that takes 1,000 seconds, nearly 17 minutes, while one loop of 100,000 takes a hundredth of a second. Programmers write this growth as Big-O. O(1) means the same few steps whatever n is, like reading coins[3]. O(n) means the steps grow in step with n, like one loop. O(n^2), said order n squared, means n x n, like a loop inside a loop. Big-O ignores small extras: a loop done twice is 2n steps and is still O(n). Space counts the extra boxes you create: a few variables is O(1), a new list as long as the input is O(n).

The intuition

Counting steps instead of seconds makes the answer true on any computer. Doubling n doubles a single loop but quadruples a loop inside a loop: 10 students means 100 steps, and 20 students means 400. That is why the second kind gets out of hand: fine for 10 items, hopeless for 100,000. Whenever you design a solution, ask how many times the innermost line runs as n grows. One pass that does a constant amount of work per box is the sweet spot: about n steps in total. Often you can spend a little extra space to avoid a loop inside a loop.

A real-world analogy

Imagine a hall with n students, and you must find out whether two of them hold the same number card. Walking along the rows and reading each card once is the single loop: n visits. Making every student show their card to every student is the loop inside a loop: with 4 students that is 16 showings, with 100,000 students it is ten billion, and the hall would have emptied long before you finished. The pencil in your hand is O(1) extra space. Copying every student's card onto a second sheet of paper would be O(n) extra space.

def count_steps(n):               # count the rounds of two loops over n boxes
    one_loop = 0                  # rounds of a single loop
    nested = 0                    # rounds of a loop inside a loop
    for a in range(n):            # n rounds
        one_loop += 1             # one round of the single loop
        for b in range(n):        # n more rounds inside each round
            nested += 1           # one round of the nested loop
    print(one_loop, nested)       # show both counts
count_steps(4)                    # 4 16
count_steps(10)                   # 10 100
print(100000 * 100000)            # 10000000000 steps for n = 100,000
print(100000 * 100000 // 10000000)  # 1000 seconds at 10 million steps a second

Set and Dict: Look-Up Tables

Asking is this value in the list? is a scan of up to n boxes. Python has a faster tool: the set. A set is a bag of values with no order and no repeats. You make one with set(), put a value in with seen.add(x), and ask with x in seen. Picture the door of a hall where badge numbers arrive in this order: 41, 17, 41, 58. The set seen remembers each number once, so when 41 arrives a second time, 41 in seen is True. Why is it fast? Python turns each value into a number called its hash, and that number says which spot to look in. It jumps straight to that spot instead of walking the row. On average that is one step, whether the set holds 10 values or 10 million. (Rarely, two values land on the same spot, and Python checks a few extra values there.) A dict is a set whose items each carry a value too. where = {} makes an empty dict, where[41] = 0 stores badge 41 with the value 0, where[41] reads that value back, and 41 in where asks whether the key 41 exists. Keys are unique: storing a key again replaces its value.

The intuition

A list answers where is x? by walking along it. A set or dict answers by jumping straight to the spot. That changes the shape of many problems. Instead of looking back through the boxes you have already passed, which is a loop inside a loop, you remember each box in a table as you go and ask the table. That is one loop, with a one-step question each round: about n steps instead of n x n. You pay with memory, because the table holds up to n items. Use a set when you only need yes or no (have I seen it?). Use a dict when you also need to recall something about the item, such as where it was.

A real-world analogy

Think of a cloakroom with numbered hooks. You hand over your ticket and the attendant works out the hook from the ticket number, then walks straight to it without searching along the whole rail. The ticket is the key, the working-out is the hash, and the coat on the hook is the value. A set is a cloakroom that only records that hook 41 is taken. A dict also holds the coat. The slow way is a heap of coats on the floor, where you must dig through the pile one coat at a time.

seen = set()                       # an empty set: a bag with no repeats
where = {}                         # an empty dict: key -> value
badges = [41, 17, 41, 58]          # badge numbers arriving at the door
for i, badge in enumerate(badges): # i is the arrival position
    if badge in seen:              # one quick look-up, not a scan
        print(badge, 'again; first at', where[badge])
    else:
        seen.add(badge)            # remember this badge
        where[badge] = i           # and where it arrived
print(len(seen), where)            # 3 {41: 0, 17: 1, 58: 3}

Keep a Running Answer

Many questions can be answered in one pass: walk the list once and keep a small summary of everything seen so far. The summary is just a few variables. Our example is a market stall's profit for five days, profit = [2, -5, 3, 4, -1], where a negative number is a loss. Typical summaries are a running total (total += p), the lowest so far (low = min(low, p)) and the best so far (best = max(best, p)). The built-in min(a, b) and max(a, b) give the smaller or larger of two numbers, and sum(profit) adds a whole list. The starting value matters. A total starts at 0, because adding 0 changes nothing. A lowest-so-far starts at float('inf'), which means infinity, bigger than any real number, so the first value always beats it. A best starts as the first value, profit[0], and not 0, because if every day were a loss the true best would be negative. The cleverest summary is the best total of consecutive days ending today. Either extend yesterday's run, giving run + today, or restart with today alone, and keep the larger: run = max(today, run + today). A run that arrives at today with a negative total would only drag today down, so we drop it.

The intuition

Why does a running summary work? Because the answer for the first i + 1 boxes can be built from the answer for the first i boxes plus one new value, so you never need to look back. You walk once, update a few variables, and the work per box is a constant. That makes the whole pass about n steps, and the extra space is only the few variables: O(1). The one-pass mindset is to ask: what is the smallest thing I must remember about the boxes behind me, so that the next box can be handled without going back?

A real-world analogy

A stall owner keeps a notebook with just two lines: how much she is up in the current good stretch, and the best stretch she has ever had. Each evening she looks only at today's profit and the first line. If the stretch so far is a loss, it can only hurt today, so she starts a fresh stretch from today. Otherwise she adds today on. Then she compares the stretch with the all-time best line and keeps the larger. She never goes back through old pages, because the two lines hold everything she needs.

profit = [2, -5, 3, 4, -1]        # daily profit of a stall (negative = a loss)
run = profit[0]                   # best total of days ending today: day 0 is just 2
best = profit[0]                  # best total seen on any day so far
for i in range(1, len(profit)):   # days 1, 2, 3, 4 (day 0 is already used)
    run = max(profit[i], run + profit[i])  # extend yesterday's run, or restart today
    best = max(best, run)         # keep the largest run seen so far
print(best)                       # 7 (days 2 and 3: 3 + 4)
low = float('inf')                # infinity: bigger than any real number
for p in profit:                  # walk once and remember the lowest so far
    low = min(low, p)             # the first value always beats infinity
print(low, sum(profit))           # -5 3

Two Fingers on a Sorted List

A finger is a variable that holds an index, so with two fingers you can look at two boxes at once. A very useful way to use them is from the two ends of a sorted list. Sorted means arranged from smallest to largest. Say the prices on a menu are prices = [1, 4, 6, 8, 13], and we want two different items whose prices add up to 12. Put a left finger on box 0 and a right finger on the last box: left = 0 and right = len(prices) - 1. Add the two boxes. If the total is exactly 12, we are done. If it is too small, move the left finger one box right, to a bigger value. If it is too big, move the right finger one box left, to a smaller value. A while loop does the repeating: while left < right: runs the lines under it again and again for as long as the condition is True. Here, 1 + 13 = 14 is too big, so the right finger moves; 1 + 8 = 9 is too small, so the left finger moves; 4 + 8 = 12 is found at indexes 1 and 3. If positions are counted from 1, report 2 and 4.

The intuition

Why is it safe to throw a box away? The biggest value, 13, was paired with the smallest value, 1, and the total was still too big at 14. Every other partner for 13 is bigger than 1, so every other total with 13 is even bigger. So 13 can never be part of the answer, and the right finger can leave it for good. The same argument works for the left finger when the total is too small. Each move rules out one box forever, so after at most n - 1 moves the fingers meet. That is about n steps, instead of checking every pair, which is about n x n. This only works because the list is sorted: the order is what tells you which finger to move.

A real-world analogy

Two friends pick two sweets from a shelf where prices run from cheapest on the left to dearest on the right, and together they must spend exactly 12 coins. One friend stands at the cheapest end and the other at the dearest end. If the pair costs too much, the friend holding the dearest sweet steps one place towards the middle, because that sweet is too dear even with the cheapest partner. If the pair costs too little, the friend holding the cheapest sweet steps in. They keep going until they find the exact pair or meet in the middle.

def find_pair(row, target):       # row is sorted, smallest to largest
    left = 0                      # left finger on the first box
    right = len(row) - 1          # right finger on the last box
    while left < right:           # repeat while the fingers are on different boxes
        total = row[left] + row[right]  # add the two boxes
        if total == target:       # exactly right
            return [left + 1, right + 1]  # positions counted from 1
        if total < target:        # too small
            left += 1             # we need a bigger small value
        else:                     # too big
            right -= 1            # we need a smaller big value
    return []                     # the fingers met: no pair exists
print(find_pair([1, 4, 6, 8, 13], 12))  # [2, 4]
print(find_pair([1, 4, 6, 8, 13], 2))   # []

Totals: Whole Minus Part, Left Plus Right

Sometimes the answer for each box depends on all the other boxes. Take five shelves holding books = [3, 5, 2, 4, 6] books. For each shelf we want the number of books on all the OTHER shelves. The whole total is 3 + 5 + 2 + 4 + 6 = 20, and sum(books) adds a whole list. So for shelf 2 the others hold 20 - 2 = 18: whole minus part. The other way is left plus right: the books to the left of shelf i plus the books to the right of it. Build them with two sweeps and one result list. result = [0] * n makes n boxes all holding 0. Sweep 1 goes left to right with a running total: store the running total in result[i] first, then add shelf i to it. Now result[i] holds everything to the left. Sweep 2 goes right to left. range(n - 1, -1, -1) gives 4, 3, 2, 1, 0: it starts at n - 1, stops before -1 and steps by -1. Do the same with a fresh running total, but ADD it to result[i]. Each running total starts at 0, because nothing has been counted yet. The total 1 + 2 + ... + n needs no loop: it is n * (n + 1) // 2, where // is whole-number division.

The intuition

The trick is to stop recomputing. To get everything to the left of shelf 3 you do not add up 3, 5 and 2 from scratch. You already had everything to the left of shelf 2, which is 3 + 5 = 8, and you add shelf 2's own 2 to get 10. Each running total is built from the previous one in a single step. Doing that once from each end gives every box both of its halves for 2n steps in total. Adding up all the other boxes separately for each box would take about n x n steps.

A real-world analogy

A librarian wants a note beside each shelf saying how many books are on all the other shelves. Walking in from the left door with a tally counter, she writes beside each shelf the count so far, and only then adds that shelf's own books. Then she walks in from the right door with a fresh tally counter and adds the count so far to each note. Every note now says left side plus right side, and a shelf's own books are never counted in its own note.

books = [3, 5, 2, 4, 6]          # books on 5 shelves
n = len(books)                   # 5
print(sum(books) - books[2])     # whole minus part: 20 - 2 = 18
result = [0] * n                 # five boxes, all 0
running = 0                      # total of the shelves already passed
for i in range(n):               # sweep left to right: 0, 1, 2, 3, 4
    result[i] = running          # everything to the LEFT of shelf i
    running += books[i]          # now include shelf i
running = 0                      # start again for the way back
for i in range(n - 1, -1, -1):   # sweep right to left: 4, 3, 2, 1, 0
    result[i] += running         # add everything to the RIGHT of shelf i
    running += books[i]          # now include shelf i
print(result)                    # [17, 15, 18, 16, 14]
print(5 * 6 // 2)                # 1 + 2 + 3 + 4 + 5 = 15

All DSA learning paths