Arrays & Dynamic Arrays

An array is the simplest and most used data structure: a row of numbered boxes in memory, side by side. Almost every other structure in this course is built on arrays, and many interview problems are array problems in disguise.

In this lesson you will learn why reading any position in an array is instant, why inserting at the front is slow, how a dynamic array such as Python's list grows without you noticing, and two useful array techniques: 2D grids and prefix sums.

How an array sits in memory

A classic array is one contiguous block of memory (all the boxes are next to each other) where every box has the same size. If the array starts at memory address 1000 and each box takes 8 bytes, then box number i is at:

address of box i = 1000 + i × 8

The computer does one multiplication and one addition, no matter whether i is 3 or 3 lakh. That is why reading or writing items[i] is O(1). This is also why indexes start at 0: box 0 is right at the start address.

A Python list works the same way, but each box holds a reference (a memory address) pointing to a Python object somewhere else. That is how one list can hold a number, a string and another list together.

Inserting and deleting: the cost of shifting

Because the boxes must stay side by side with no gaps, putting a new item at the front means moving every other item one place to the right. This function does what list.insert() does inside, and counts the moves:

def insert_at(items, index, value):
    """Insert like list.insert(), counting how many items move."""
    moves = 0
    items.append(None)                      # make room at the end
    for i in range(len(items) - 1, index, -1):
        items[i] = items[i - 1]             # shift one place right
        moves += 1
    items[index] = value
    return moves

queue = ["Aarav", "Priya", "Kabir", "Meera"]
print(insert_at(queue, 0, "Isha"), queue)
print(insert_at(queue, 5, "Rohan"), queue)

4 ['Isha', 'Aarav', 'Priya', 'Kabir', 'Meera']
0 ['Isha', 'Aarav', 'Priya', 'Kabir', 'Meera', 'Rohan']

Inserting at the front moved all four names; adding at the end moved none. Deleting works the same way in reverse, because the items after the gap must slide left. So for an array:

If your program keeps adding and removing at the front, an array is the wrong tool. You will meet better ones in Linked Lists and Queues & Deques.

Dynamic arrays: how a list grows

A classic array has a fixed size chosen when it is created. A dynamic array hides this limit. It reserves some extra empty boxes (its capacity). When the boxes run out, it asks for a bigger block, copies everything across and frees the old one.

Copying n items sounds expensive, so why is append() called O(1)? Because the array grows by a multiple of its size, the copies happen rarely. Here is a small dynamic array that doubles its capacity and counts every copy:

class DynamicArray:
    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.slots = [None] * self.capacity
        self.copies = 0

    def append(self, value):
        if self.size == self.capacity:
            self._grow()
        self.slots[self.size] = value
        self.size += 1

    def _grow(self):
        self.capacity *= 2
        bigger = [None] * self.capacity
        for i in range(self.size):
            bigger[i] = self.slots[i]
            self.copies += 1
        self.slots = bigger

    def __getitem__(self, i):
        if not 0 <= i < self.size:
            raise IndexError("index out of range")
        return self.slots[i]


arr = DynamicArray()
for n in range(1, 100_001):
    arr.append(n)
    if n in (10, 1000, 100_000):
        print(f"{n} appends, capacity {arr.capacity}, "
              f"{arr.copies} copies, {arr.copies / n:.2f} copies per append")
print(arr[99_999])

10 appends, capacity 16, 15 copies, 1.50 copies per append
1000 appends, capacity 1024, 1023 copies, 1.02 copies per append
100000 appends, capacity 131072, 131071 copies, 1.31 copies per append
100000

The total number of copies is always less than 2n, so each append costs fewer than two copies on average. This kind of average over a long sequence of operations is called amortised cost: a single append can be slow, but n appends together take O(n) time, so each one is amortised O(1).

Python's real list grows by about one eighth plus a few extra slots instead of doubling, which wastes less memory. You can watch it happen with sys.getsizeof(), which reports the memory a list uses:

import sys

items = []
grew_at = []
last = sys.getsizeof(items)
for i in range(70):
    items.append(i)
    size = sys.getsizeof(items)
    if size != last:
        grew_at.append(len(items))
        last = size
print("The list reserved more room at lengths:", grew_at)

The list reserved more room at lengths: [1, 5, 9, 17, 25, 33, 41, 53, 65]

Between those lengths, appends just fill empty slots. The exact byte sizes differ between computers, so the example prints only the lengths.

2D arrays

A grid, such as the seats in a cinema hall in Lucknow, is an array of rows where each row is an array. In Python that is a list of lists, and hall[r][c] means row r, column c.

rows, cols = 4, 6
hall = [["." for _ in range(cols)] for _ in range(rows)]

booked = [(0, 2), (0, 3), (2, 1), (3, 5)]
for r, c in booked:
    hall[r][c] = "X"

for r, row in enumerate(hall):
    print(chr(ord("A") + r), " ".join(row))

free = sum(row.count(".") for row in hall)
print("Free seats:", free)

A . . X X . .
B . . . . . .
C . X . . . .
D . . . . . X
Free seats: 20

Build grids with a comprehension. The shortcut [["."] * cols] * rows repeats one row object, so booking a seat in row A would book it in every row. Visiting every cell of an r by c grid is O(r × c).

Advanced: prefix sums

Many interview problems ask for the sum of a range again and again. Adding up the range each time is O(n) per question. A prefix sum array stores the running total up to each position, built once in O(n). After that, the sum of any range is one subtraction, which is O(1).

Here are the daily sales (in ₹ thousands) of a bakery in Kochi for ten days:

from itertools import accumulate

sales = [12, 15, 9, 20, 18, 7, 25, 30, 11, 14]
prefix = [0] + list(accumulate(sales))    # prefix[i] = sum of first i days
print(prefix)

def range_total(first_day, last_day):     # days numbered from 1
    return prefix[last_day] - prefix[first_day - 1]

print("Days 1-3:", range_total(1, 3))
print("Days 4-8:", range_total(4, 8))
print("Days 7-10:", range_total(7, 10))

[0, 12, 27, 36, 56, 74, 81, 106, 136, 147, 161]
Days 1-3: 36
Days 4-8: 100
Days 7-10: 80

The extra 0 at the start of prefix removes a special case for ranges that start on day 1. itertools.accumulate() produces running totals; a simple loop works too. Prefix sums only work while the data does not change. If values are updated often, you need the trees in Fenwick & Segment Trees.

Common mistakes

• Calling insert(0, x) or pop(0) in a loop. Each call is O(n), so a loop of them is O(n²). Use collections.deque for a queue.
• Building grids with *. [[0] * 3] * 3 shares one row three times. Use a comprehension.
• Off-by-one errors. The last index is len(items) - 1. Write down a tiny example and check the first and last positions.
• Thinking O(1) amortised means every append is fast. Most are, but an occasional append copies the whole list.

Key points

• An array stores items side by side, so items[i] is O(1) by simple address arithmetic.
• Inserting or deleting anywhere except the end shifts items and costs O(n).
• A dynamic array grows by a multiple of its size, so append() is amortised O(1).
• Python's list, Java's ArrayList and C++'s std::vector are dynamic arrays.
• A 2D grid is a list of rows; build it with a comprehension.
• Prefix sums answer range-sum questions in O(1) after O(n) preparation.

units = [210, 185, 160, 240, 310, 355, 330, 290, 220, 190, 175, 205]

prefix = [0]
for u in units:
    prefix.append(prefix[-1] + u)

def total(first, last):
    return prefix[last] - prefix[first - 1]

print("April to June:", total(4, 6))
print("Whole year:", total(1, 12))

April to June: 905
Whole year: 2870