Data structure 1 of 12

Arrays and lists

An array is a row of numbered boxes. Jumping to box i takes one step, however long the row is; squeezing a new box into the middle means shifting everything after it. Almost every interview problem starts with one.

A 3-minute conversation: Sam asks, Priya explains

0:00 / 3:01

Follow along on the page Pause on “your turn” questions

Sam Lesson one: arrays. I use lists every day. What is there to learn?
Priya Why some list operations are instant and others are quietly slow. That one idea decides whether a solution passes. An array is a row of numbered boxes. Jumping to box i takes one step. Squeezing a new box into the middle means shifting everything after it.
Priya Picture school lockers, numbered from zero. To open locker seven you walk straight to it. But if a new student needs a locker between three and four, everyone from four onwards moves along one.
Sam And a Python list is an array?
Priya An array that grows by itself when you add to the end. TypeScript's array and Java's ArrayList are the same idea. Indices run from zero to n minus one.
Sam Why is reading box i instant?
Priya The values sit in one unbroken block of memory. If it starts at address one thousand and each value takes eight bytes, value i is at one thousand plus eight times i. One multiplication, one addition.
Sam And how does it grow?
Priya It keeps spare boxes at the end. When they run out, it gets a block about twice as big and copies everything across. The copy is slow, but it's rare, so appending is still O(1) on average. That's called amortised.
Sam So which operations are cheap?
Priya Reading or writing by index, the length, and adding or removing at the end. Expensive: inserting or removing near the front, because everything after shifts, and searching for a value, because you check every box.
Priya Your turn. What does inserting at index zero of a long list cost?
Priya Linear time. Every other value shifts one place right. Do it in a loop and you've got quadratic time.
Sam Anything language-specific?
Priya In Java, plain int arrays have a fixed size; ArrayList grows. And for a grid, build each row separately. In Python, multiplying a list of rows makes every row the same list.
Sam What are the five players?
Priya Walk every item to find the largest. Append, with a tiny version of how a list grows. Insert in the middle, shifting from the back. Delete from the middle, shifting from the front. And a grid: rows, columns, and the four neighbours of a cell.
Sam Why shift from the back when inserting?
Priya Shift from the front and you overwrite the next value before you've moved it.
Sam The memory hook?
Priya Numbered lockers. Index is instant, the end is cheap, the middle shifts.
Sam And the problems?
Priya Running sum, where each box adds the one before it. Remove element, with a read index and a write index. And richest customer wealth, a walk over a grid.
Sam Mistakes to avoid?
Priya Off by one: the last index is length minus one. Changing a list while looping over it. Working at the front in a loop. And shared rows in a grid.
Sam What's next?
Priya Lesson two, strings: arrays of letters you can't change.

1. What it is

A row of school lockers, numbered from 0. To open locker 7 you walk straight to it: you don't count lockers 0 to 6. But if a new student needs a locker between 3 and 4, everyone from 4 onwards has to move one locker along.

An array stores values side by side, each in a numbered slot called an index. The first index is 0, so a row of n values has indices 0 to n − 1. A list in Python (an Array in TypeScript, an ArrayList in Java) is an array that grows by itself when you add to the end.

Fast: reading or changing the value at any index; adding or removing at the end.
Slow: inserting or removing near the front (everything after shifts); searching for a value without an index (you check every box).

2. How it sits in memory

The values sit in one unbroken block of memory. If the block starts at address 1000 and each value takes 8 bytes, value i lives at 1000 + 8 × i. One multiplication and one addition find any box, which is why indexing costs O(1).

A list keeps some spare boxes at the end. When they run out it asks for a block about twice as big and copies everything across. Copying is slow, but it happens so rarely that adding to the end still costs O(1) on average (called amortised).

3. Operations and what they cost

Operation	Python	Cost	Why
Read or write at index i	`nums[i]`, `nums[i] = x`	`O(1)`	The address is computed directly.
Length	`len(nums)`	`O(1)`	The list keeps a count.
Add or remove at the end	`append(x)`, `pop()`	`O(1)` amortised	No shifting; an occasional resize.
Insert or remove at index i	`insert(i, x)`, `pop(i)`	`O(n)`	Everything after i shifts by one.
Search for a value	`x in nums`, `nums.index(x)`	`O(n)`	Checks the boxes one by one.
Copy a slice	`nums[a:b]`	`O(b − a)`	Makes a new list.
Sort	`nums.sort()`	`O(n log n)`	Comparison sorting.

Rule of thumbWork at the end of a list, never at the front. If you need to add or remove at both ends, use a deque (structure 07).

4. In Python, TypeScript and Java

The same everyday operations in each language. Switch the language with the tabs above any code block.

nums = [7, 3, 9]          # a list
    nums.append(4)            # [7, 3, 9, 4]
    last = nums.pop()         # 4; nums is [7, 3, 9] again
    nums[1] = 8               # [7, 8, 9]
    size = len(nums)          # 3
    first_two = nums[:2]      # [7, 8], a new list
    grid = [[0] * 3 for _ in range(2)]   # 2 rows, 3 columns, each row its own list
    for i, x in enumerate(nums):         # index and value together
        print(i, x)

const nums: number[] = [7, 3, 9];
    nums.push(4);                         // [7, 3, 9, 4]
    const last = nums.pop();              // 4
    nums[1] = 8;                          // [7, 8, 9]
    const size = nums.length;             // 3
    const firstTwo = nums.slice(0, 2);    // [7, 8]
    const grid = Array.from({ length: 2 }, () => new Array(3).fill(0));
    nums.forEach((x, i) => console.log(i, x));

int[] fixed = {7, 3, 9};                     // fixed size: fixed.length == 3
    List<Integer> nums = new ArrayList<>(List.of(7, 3, 9));
    nums.add(4);                                 // [7, 3, 9, 4]
    int last = nums.remove(nums.size() - 1);     // 4
    nums.set(1, 8);                              // [7, 8, 9]
    int size = nums.size();                      // 3
    int[][] grid = new int[2][3];                // 2 rows, 3 columns of 0
    for (int i = 0; i < nums.size(); i++) System.out.println(i + " " + nums.get(i));

5. Core operations, step by step

Five things you will do with arrays all the time. Each player runs the code line by line: press Play to hear it explained, or step with the arrow keys.

A · Walk every item (find the largest)

What it doesVisits each index once, keeping the best value so far.

Picture itWalking along the lockers with a sticky note that holds the biggest number seen so far.

CostO(n) time, O(1) extra space.

The code. Start with the first value, then compare every other value against it.

def largest(nums):
    best = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > best:
            best = nums[i]
    return best

function largest(nums: number[]): number {
  let best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > best) {
      best = nums[i];
    }
  }
  return best;
}

static int largest(int[] nums) {
    int best = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > best) {
            best = nums[i];
        }
    }
    return best;
}

Line by line.

Line	What it does	Why
`best = nums[0]`	Start with the first value.	Starting at 0 would be wrong for an all-negative array.
`for i in range(1, len(nums))`	Visit indices 1 to n − 1.	Index 0 is already in best.
`if nums[i] > best`	Compare with the best so far.	One comparison per item: O(n) in total.

Watch it run. Find the largest value in [7, 3, 9, 4].

Watch out for:

Starting best at 0. It fails when every value is negative. Start from nums[0].
Looping to len(nums) inclusive. The last index is len(nums) − 1.

B · Append, and how a list grows

What it doesAdds a value at the end; doubles the storage when it is full.

Picture itA shelf with a few empty spaces at the end. When it is full you buy a shelf twice as long and move every book once.

CostO(1) amortised: an occasional O(n) copy, spread over many cheap appends.

The code. A tiny version of what Python's list, TypeScript's array and Java's ArrayList do for you.

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

    def append(self, x):
        if self.size == len(self.slots):
            bigger = [None] * (2 * len(self.slots))
            for i in range(self.size):
                bigger[i] = self.slots[i]
            self.slots = bigger
        self.slots[self.size] = x
        self.size += 1

class DynamicArray {
  slots: (number | null)[] = [null];
  size = 0;

  append(x: number): void {
    if (this.size === this.slots.length) {
      const bigger: (number | null)[] = new Array(2 * this.slots.length).fill(null);
      for (let i = 0; i < this.size; i++) {
        bigger[i] = this.slots[i];
      }
      this.slots = bigger;
    }
    this.slots[this.size] = x;
    this.size += 1;
  }
}

static class DynamicArray {
    Integer[] slots = new Integer[1];
    int size = 0;

    void append(int x) {
        if (size == slots.length) {
            Integer[] bigger = new Integer[2 * slots.length];
            for (int i = 0; i < size; i++) {
                bigger[i] = slots[i];
            }
            slots = bigger;
        }
        slots[size] = x;
        size += 1;
    }
}

Line by line.

Line	What it does	Why
`if self.size == len(self.slots)`	Is every slot used?	Only then do we pay for a copy.
`bigger = [None] * (2 * len(self.slots))`	A block twice as big.	Doubling keeps copies rare: 1, 2, 4, 8 … Growing by one would copy on every append (O(n²) in total).
`self.slots[self.size] = x`	Write into the first free slot.	size is also the index of the first free slot.

Watch it run. Append 5, 8, 2, 6 and 1 to an empty list that starts with one slot.

Watch out for:

Thinking every append is O(1). Most are; the occasional resize is O(n). On average it is still O(1).
Growing by a fixed amount. Adding 10 slots at a time makes n appends cost O(n²). Grow by a factor.

C · Insert in the middle (shift right)

What it doesPuts a value at index i, moving everything from i onwards one place right.

Picture itSomeone joins the middle of a queue: everyone behind them takes one step back.

CostO(n): up to n values move.

The code. Make room at the end, then shift from the back so nothing is overwritten.

def insert_at(nums, i, x):
    nums.append(None)
    for j in range(len(nums) - 1, i, -1):
        nums[j] = nums[j - 1]
    nums[i] = x
    return nums

function insertAt(nums: (number | null)[], i: number, x: number): (number | null)[] {
  nums.push(null);
  for (let j = nums.length - 1; j > i; j--) {
    nums[j] = nums[j - 1];
  }
  nums[i] = x;
  return nums;
}

static List<Integer> insertAt(List<Integer> nums, int i, int x) {
    nums.add(null);
    for (int j = nums.size() - 1; j > i; j--) {
        nums.set(j, nums.get(j - 1));
    }
    nums.set(i, x);
    return nums;
}

Line by line.

Line	What it does	Why
`nums.append(None)`	One more box at the end.	The row must grow by one.
`for j in range(len(nums) - 1, i, -1)`	Walk from the back towards i.	Shifting from the front would copy the same value along the whole row.
`nums[j] = nums[j - 1]`	Move the left neighbour right.	Each move frees the box to its left.
`nums[i] = x`	Drop the new value in.	Box i is free now.

Watch it run. Insert 5 at index 1 of [7, 3, 9, 4].

Watch out for:

Shifting from the front. You overwrite the next value before moving it.
Inserting at the front inside a loop. n inserts at index 0 cost O(n²). Build the list in reverse and flip it once, or use a deque.

D · Delete from the middle (shift left)

What it doesRemoves the value at index i, moving everything after it one place left.

Picture itSomeone leaves the queue: everyone behind steps forward.

CostO(n).

The code. Shift from i towards the end, then drop the last box.

def remove_at(nums, i):
    for j in range(i, len(nums) - 1):
        nums[j] = nums[j + 1]
    nums.pop()
    return nums

function removeAt(nums: number[], i: number): number[] {
  for (let j = i; j < nums.length - 1; j++) {
    nums[j] = nums[j + 1];
  }
  nums.pop();
  return nums;
}

static List<Integer> removeAt(List<Integer> nums, int i) {
    for (int j = i; j < nums.size() - 1; j++) {
        nums.set(j, nums.get(j + 1));
    }
    nums.remove(nums.size() - 1);
    return nums;
}

Line by line.

Line	What it does	Why
`for j in range(i, len(nums) - 1)`	From i up to the second-to-last box.	The last box has no right neighbour to copy.
`nums[j] = nums[j + 1]`	Pull the right neighbour left.	Going left to right never overwrites a value we still need.
`nums.pop()`	Remove the now-duplicate last box.	O(1) at the end.

Watch it run. Remove index 1 from [7, 5, 3, 9, 4].

Watch out for:

Removing items while looping forwards over the same list. Indices shift under you and items get skipped. Build a new list, or loop backwards.
Using pop(0) as a queue. Every pop(0) shifts the whole list. Use a deque.

E · A 2-D grid: rows, columns and neighbours

What it doesReads grid[r][c] and lists the cells up, down, left and right of it that are inside the grid.

Picture itSeats in a cinema: row first, then seat number. Your neighbours are the seats in front, behind and either side.

CostO(1) per cell; walking every cell is O(rows × cols).

The code. A grid is a list of rows. Check the edges before stepping off them.

def neighbours(grid, r, c):
    rows, cols = len(grid), len(grid[0])
    found = []
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            found.append(grid[nr][nc])
    return found

function neighbours(grid: number[][], r: number, c: number): number[] {
  const rows = grid.length, cols = grid[0].length;
  const found: number[] = [];
  for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
    const nr = r + dr, nc = c + dc;
    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
      found.push(grid[nr][nc]);
    }
  }
  return found;
}

static List<Integer> neighbours(int[][] grid, int r, int c) {
    int rows = grid.length, cols = grid[0].length;
    List<Integer> found = new ArrayList<>();
    for (int[] d : new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
            found.add(grid[nr][nc]);
        }
    }
    return found;
}

Line by line.

Line	What it does	Why
`rows, cols = len(grid), len(grid[0])`	The grid's height and width.	Rows first, then columns, everywhere.
`for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]`	Up, down, left, right.	A list of directions beats four copies of the same if.
`if 0 <= nr < rows and 0 <= nc < cols`	Is the neighbour inside the grid?	Python would quietly read grid[-1] (the last row) without this check.

Watch it run. Find the neighbours of the cell at row 0, column 1 in a 2 × 3 grid.

Watch out for:

[[0] * cols] * rows. Every row is the same list: changing one changes all. Use a comprehension.
Swapping r and c. grid[r][c]: row first. Name them r and c, never x and y.

6. How to remember it

Memory hook: "Numbered lockers"Walk straight to any locker by its number. Add or remove at the end of the corridor freely; squeeze into the middle and everyone shuffles along.

Picture

A corridor of lockers numbered 0, 1, 2 … with a few empty ones at the far end.

Chant

"Index is instant, the end is cheap, the middle shifts."

Key rule

The last index is len − 1. Every loop bound should make you think about it.

7. Problems solved with it

Three easy LeetCode problems that need nothing but the operations above.

LC 1480 · Running Sum of 1d Array

The problemReturn an array where element i is the sum of nums[0] through nums[i].

What it doesWalks once, adding the previous total into the current box.

CostO(n) time, O(1) extra space (in place).

The code. Each box becomes itself plus the box before it.

def running_sum(nums):
    for i in range(1, len(nums)):
        nums[i] += nums[i - 1]
    return nums

function runningSum(nums: number[]): number[] {
  for (let i = 1; i < nums.length; i++) {
    nums[i] += nums[i - 1];
  }
  return nums;
}

static int[] runningSum(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
}

Line by line.

Line	What it does	Why
`for i in range(1, len(nums))`	Start at index 1.	Index 0's running sum is itself.
`nums[i] += nums[i - 1]`	Add the total so far.	nums[i − 1] already holds the sum of everything before it.

Watch it run. [1, 2, 3, 4].

Watch out for:

Starting at 0. nums[-1] is the last element in Python: index 0 would add the wrong value.

LC 27 · Remove Element

The problemRemove every occurrence of val from nums in place and return k, the number of values left. The first k boxes must hold them.

What it doesCopies each value worth keeping to the next free box at the front.

CostO(n) time, O(1) extra space.

The code. write is the next box to fill; read visits every box.

def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    return write

function removeElement(nums: number[], val: number): number {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== val) {
      nums[write] = nums[read];
      write += 1;
    }
  }
  return write;
}

static int removeElement(int[] nums, int val) {
    int write = 0;
    for (int read = 0; read < nums.length; read++) {
        if (nums[read] != val) {
            nums[write] = nums[read];
            write += 1;
        }
    }
    return write;
}

Line by line.

Line	What it does	Why
`write = 0`	The next box to fill.	Everything left of write is a kept value.
`if nums[read] != val`	Is this value a keeper?	Values equal to val are simply skipped.
`nums[write] = nums[read]`	Copy it forward.	write never passes read, so nothing unread is overwritten.

Watch it run. Remove 3 from [3, 2, 2, 3, 4].

Watch out for:

Calling remove() in a loop. Each remove shifts the rest: O(n²). Overwrite instead.

LC 1672 · Richest Customer Wealth

The problemaccounts[i][j] is how much customer i has in bank j. Return the largest total any customer has.

What it doesSums each row, keeping the largest row total.

CostO(rows × cols) time, O(1) space.

The code. A grid walk: one loop over rows, one over the cells of a row.

def maximum_wealth(accounts):
    best = 0
    for row in accounts:
        total = 0
        for money in row:
            total += money
        best = max(best, total)
    return best

function maximumWealth(accounts: number[][]): number {
  let best = 0;
  for (const row of accounts) {
    let total = 0;
    for (const money of row) {
      total += money;
    }
    best = Math.max(best, total);
  }
  return best;
}

static int maximumWealth(int[][] accounts) {
    int best = 0;
    for (int[] row : accounts) {
        int total = 0;
        for (int money : row) {
            total += money;
        }
        best = Math.max(best, total);
    }
    return best;
}

Line by line.

Line	What it does	Why
`total = 0`	A fresh total for each customer.	Resetting outside the row loop would add every customer together.
`best = max(best, total)`	Keep the richest so far.	Compare once per row, after the row is summed.

Watch it run. Three customers, two banks each.

Watch out for:

Resetting total in the wrong place. Reset it at the start of each row.

More practice, solved on the pattern pages

#	Problem	Level	Where
26	Remove Duplicates from Sorted Array	Easy	Solved step by step on 02 · Two Pointers
88	Merge Sorted Array	Easy	Solved step by step on 02 · Two Pointers
977	Squares of a Sorted Array	Easy	Solved step by step on 02 · Two Pointers
121	Best Time to Buy and Sell Stock	Easy	Solved step by step on 03 · Sliding Window
2239	Find Closest Number to Zero	Easy	Solved step by step on 21 · Array & String Basics
704	Binary Search	Easy	Solved step by step on 09 · Modified Binary Search

8. Common mistakes

Off by oneA list of length n has indices 0 to n − 1. nums[len(nums)] is an error; range(len(nums)) already stops before n.

Changing a list while looping over itRemoving items during a forward loop skips the item after each removal. Loop over a copy, loop backwards, or build a new list.

Working at the frontinsert(0, x) and pop(0) shift every element: O(n) each, O(n²) in a loop. Use a deque, or build backwards and reverse once.

Shared rows in a grid[[0] * 3] * 2 makes two references to one row. Write [[0] * 3 for _ in range(2)].

Negative indices by accidentIn Python nums[-1] is the last item, not an error. A bug that computes index −1 fails silently; check bounds yourself.

9. Self-check quiz

Reading nums[500000] in a list of a million numbers costs…

The address is start + 500000 × size: one calculation, whatever the index.

What does nums.insert(0, x) cost, and why?

All n values move one place right to make room at the front.

Why is append O(1) on average even though it sometimes copies the whole list?

After a copy of n items, the next n appends are free. Spread out, each append pays a constant.

g = [[0] * 3] * 3, then g[0][0] = 1. What happens?

The outer * 3 repeats a reference to the same inner list.

10. Where it shows up next

Arrays are the starting point of most patterns. These pages build directly on what you just learned:

21 · Array & String Basics: scanning with lookups and simple bookkeeping.
02 · Two Pointers: two indices moving towards each other or in step, like Remove Element above.
03 · Sliding Window: a range of indices that grows and shrinks.
01 · Prefix Sum: the running sum from LC 1480, used to answer range questions instantly.
13 · Matrix Traversal: grids and the neighbours loop from operation E.

Next structure: 02 · Strings and characters, which are arrays of letters with one important twist.