CHAPTER 01 · Array

The Array

A row of side-by-side slots in memory, numbered from 0. It pays for every insertion and deletion in the middle by moving the elements after it, and in exchange it gives you the fastest operation in this course: O(1) random access.

§01

Intuition: a row of numbered lockers

Get the picture first, then talk about complexity.

Picture the row of lockers at a gym: the lockers are next to each other, all the same size, and numbered from 0. With key number 5 in your hand you do not check locker 0, then 1, then 2. You walk straight to locker 5. That is the one ability an array is built for: give it an index and it returns the element.

The row of lockers follows three rules. Every behavior of an array comes from these three rules.

RULE 01

Contiguous

The elements sit next to each other in memory, with no gaps. The benefit: any position can be computed with a formula. The cost: inserting or deleting in the middle means moving elements.

RULE 02

Same element size

Every element takes the same number of bytes, for example 4 bytes for an int. That is what makes the multiplication index × element size possible.

RULE 03

Fixed length (the basic form)

Once allocated, the length cannot change, because the memory right after it may already be used by something else. To “grow”, the whole block has to move to a larger one. That is the dynamic array in §04.

Arrays are everywhere

Your photos are arrays of pixels. The text on this page is an array of characters. A database page stores its rows one after another. The array is the structure closest to the hardware, and it is the base that hash tables, heaps, and dynamic arrays are built on. Learn this chapter well and the next few will be easier.

§02

In memory: one formula does all the work

address = base address + index × element size. Click a cell below to check it.

Memory is one long street of numbered addresses. What an array asks the system for is one contiguous range of those addresses. Suppose an int array starts at address 1000 and each int takes 4 bytes. Then the address of element i is not searched for. It is calculated:

Addressing lab — click any cell

The address of arr[2] = 1000 (base address) + 2 × 4 (element size) = 1008. One multiply and one add, no searching. That is O(1). With a hundred million elements the formula is still the same.

Why does indexing start at 0?

Because an index is really an offset. The first element is 0 units away from the base address. arr[0] means “0 steps from the start”, and the formula works out cleanly. It is not a habit of computer scientists, it follows from the formula.

Why is going out of bounds dangerous?

The formula does not know where the array ends. arr[100] computes an address even when another variable lives there. In C that is the classic buffer overflow. Java throws ArrayIndexOutOfBoundsException, Python raises IndexError, and JavaScript simply returns undefined for a read past the end. The checks are safer, but they are not free.

Why the CPU cache favours arrays

The CPU does not read memory one byte at a time. It reads a whole block, called a cache line, usually 64 bytes. Because array elements sit next to each other, reading arr[0] also pulls arr[1..15] into the cache when the elements are 4-byte ints. A forward scan then finds almost every element already in the cache. This is a cache effect, not a difference in complexity: walking an array and walking a linked list are both O(n), but in practice the array is often several times faster.

§03

Core operations and binary search

Every cost comes from one question: do other elements have to move?

Operation	Complexity	Why
Read or write by index `arr[i]`	O(1)	One formula gives the address. No other element is touched.
Append at the end (space available)	O(1)	Write into the next free slot. Nothing has to move.
Insert at the front or in the middle	O(n)	Every element to the right of the insertion point shifts one slot right to make room.
Delete (not at the end)	O(n)	Every element to the right shifts one slot left to close the gap. Deleting means filling in, not cutting out.
Search (unsorted)	O(n)	There is no clue about where the value is, so you check every element in turn.
Search (sorted, binary search)	O(log n)	Each comparison removes half of the remaining range. This needs sorted data and O(1) random access together.

The important column is the last one. Insert and delete a few times yourself and count the moves. After that you will not confuse these costs again.

Insert and delete lab

Pick a position, then insert or delete, and count how many elements move.

Index 1

A common mistake in interviews

“Deleting one element from an array” is not O(1) just because the API call is short. list.pop(0) in Python, arr.shift() in JavaScript, and list.remove(0) on a Java ArrayList are all O(n). The convenient method still shifts every element after the removed one.

The O(log n) search on sorted data in that table deserves its own code. Binary search repeatedly cuts the remaining range in half: compare the middle element with the target, and one half can be discarded. Think of guessing a number between 1 and 100 where each guess is answered with “higher” or “lower”. Always guessing the middle finds it in at most 7 guesses, because 2⁷ = 128 > 100. A million elements take 20 comparisons. A billion take 30. That is what a logarithm means here.

binary_search.py

1# Precondition: nums is sorted in ascending order. Returns the index of target, or -1.

2def search(nums: list[int], target: int) -> int:

3 left, right = 0, len(nums) - 1 # closed interval [left, right]

4 while left <= right: # the interval still holds elements

5 mid = (left + right) // 2 # Python ints are unbounded, no overflow

6 if nums[mid] == target:

7 return mid

8 elif nums[mid] < target:

9 left = mid + 1 # target is in the right half

10 else:

11 right = mid - 1 # target is in the left half

12 return -1

14# The standard library has this too: import bisect, then bisect.bisect_left(nums, target)

Python integers have no fixed width, so there is no overflow here. The bisect module in the standard library is already a binary search.

The invariant, and the three details interviewers ask about

The code above uses a closed interval [left, right], meaning both ends are still candidates. The invariant is: if target is in the array, its index is inside [left, right]. Every branch preserves it, because nums[mid] < target rules out everything up to mid, and nums[mid] > target rules out everything from mid on. Three details follow from the invariant. First, the loop condition is left <= right, because an interval with one element still has to be checked. Second, the update must be mid + 1 or mid - 1; keeping mid inside the interval can loop forever. Third, binary search needs sorted data and O(1) random access, so it does not work on a linked list. Practice: LC 704 for the template, LC 35 to see where left stops when the value is absent.

§04

Dynamic arrays: how a fixed block pretends to grow

What ArrayList, Python list, and JS Array really do: when the block is full, allocate a bigger one and copy.

A plain array has a fixed length, yet you use “arrays” that you can push into forever. The trick is simple: keep a fixed-size array inside, plus a count of how many slots are used. If there is room, write into the next slot, which is O(1). If it is full, allocate a larger array, usually 1.5 to 2 times the size, copy every element across, and continue. Trigger a resize yourself:

Dynamic array resize lab

·0

·1

A dynamic array with capacity 2. Keep pushing and watch when it moves to a bigger block.

capacity 2 · stored 0 · pushes 0 · copies 0

One resize really does cost O(n), so why call append O(1)? Count the total instead of one call. Growing from capacity 1 to n by doubling copies 1 + 2 + 4 + … + n/2, which is less than n. So n appends do at most about 2n units of work in total, an average of 2 units each, which is a constant. This way of counting is called amortized analysis, and the average is what the counter in the lab above keeps showing you. Note the exact claim: a single append is not O(1) in the worst case, it is O(n) when the resize happens. It is O(1) amortized: the expensive calls are rare enough that any sequence of n appends still costs O(n) in total. This holds for any growth factor greater than 1, not only for doubling.

Language	Dynamic array	Growth in the main implementation	Worth knowing
Java	`ArrayList`	about ×1.5 (`old + (old >> 1)`)	The storage is an `Object[]`. If you know the size in advance, `new ArrayList<>(n)` avoids the copies.
Python	`list`	about ×1.125 plus a small constant (smaller steps, different from Java)	A list stores pointers to objects, not raw numbers. That is one reason NumPy is much faster for numeric work.
JavaScript	`Array`	V8 uses about ×1.5 plus 16	V8 uses a packed, contiguous backing store only while the array stays dense. A sparse array falls back to a dictionary.

The growth factors are not the same

It is common to hear “dynamic arrays double”. That is a simplification. Java ArrayList grows by about 1.5. CPython over-allocates by roughly one eighth of the new size plus a small constant, so its factor is much smaller and changes with the size. What they share is that the growth is proportional to the current size, and that is the only property the amortized O(1) argument needs.

§05

Build a dynamic array yourself

Under 50 lines, with the same skeleton the standard libraries use.

You now know the three parts of a dynamic array: a fixed-size array, a size counter, and a resize step that runs when it is full. Put them together. The implementation below is small but complete: read, write, append, and insert or delete at any position.

A good way to use it: cover the code, write push and insert yourself, then compare. Pay attention to why insert copies from the back to the front. Copying front to back would overwrite a value before it has been moved, which the lab in §03 showed step by step.

dyn_array.py

1# A minimal dynamic array in Python (the skeleton of CPython's list)

2class DynArray:

3 def __init__(self):

4 self._data = [None] * 2 # the fixed-size storage, capacity 2

5 self._size = 0 # how many slots are in use

7 def get(self, i): # O(1)

8 if not 0 <= i < self._size:

9 raise IndexError(i)

10 return self._data[i]

12 def push(self, x): # O(1) amortized

13 if self._size == len(self._data):

14 self._grow()

15 self._data[self._size] = x

16 self._size += 1

18 def insert(self, i, x): # O(n)

19 if self._size == len(self._data):

20 self._grow()

21 for j in range(self._size, i, -1): # copy back to front

22 self._data[j] = self._data[j - 1]

23 self._data[i] = x

24 self._size += 1

26 def remove_at(self, i): # O(n)

27 victim = self._data[i]

28 for j in range(i, self._size - 1): # copy front to back

29 self._data[j] = self._data[j + 1]

30 self._size -= 1

31 return victim

33 def _grow(self): # resize: twice the capacity

34 bigger = [None] * (len(self._data) * 2)

35 for j in range(self._size):

36 bigger[j] = self._data[j]

37 self._data = bigger

How the real CPython list differs: it over-allocates by about one eighth plus a small constant, and its storage is a C array of pointers to objects. The logic is the same.

Check that you understood it

Close the code and answer three questions. First, why does insert copy from the back to the front? Second, why does removeAt copy from the front to the back? Third, if the resize added only one slot each time, what would n appends cost in total? The answer to the third is 1 + 2 + … + n = O(n²), which is why the capacity has to grow by a factor, not by a fixed amount.

§06

Two-dimensional arrays: the same formula, one dimension up

A chessboard, an image, a spreadsheet. Memory has no rows and columns, only a line you read as a grid.

A matrix is an array of arrays: matrix[i][j] is row i, column j. Memory has no rows or columns, so a matrix has to be laid out in one line. The usual layout is one row after another, called row-major order, and the position formula gains one dimension: flat index = row × number of columns + column. Click a cell to check it:

Row-major layout — click any cell in the matrix

510

311

Flattened row by row, matrix[1][2] lands at index = row × number of columns + column = 1 × 4 + 2 = 6. The same multiply-and-add formula, one dimension up.

One contiguous block, or an array of rows?

In C, and in a NumPy array, a 2D array is one contiguous block, and the formula above is exactly how the compiler addresses it. In Java, int[][] is an array of references to row arrays: each row is contiguous, but two rows need not sit next to each other, and rows can even have different lengths. Python lists of lists and JavaScript arrays of arrays work the same way. The formula still describes the layout you get when you flatten a matrix into one array yourself, which many problems ask you to do.

Traverse rows first

Looping row by row (for i → for j) reads elements that are next to each other in memory, so most reads hit the cache. Looping column by column jumps a whole row each step and can be several times slower on a large matrix. Both are O(mn); the difference is a cache effect, not a difference in complexity (see the cache line note in §02).

Three habits for matrix problems

First, use a direction array: dirs = [[-1,0],[1,0],[0,-1],[0,1]] handles up, down, left, and right in one loop instead of four if blocks. Second, check the bounds first (0 ≤ i < m and 0 ≤ j < n) before reading a cell. Third, for O(1) extra space, use the first row and column of the matrix itself as marks (LC 73). A matrix is also a grid graph, and the graph chapter will traverse it as one.

§07

Three languages, one abstraction

The structure does not change with the language. The implementation and the API do. The top bar switches the code language for the whole site.

The abstraction is the same in all three languages: elements in index order, O(1) access by index, O(n) insertion and deletion in the middle. The memory layout is not guaranteed to be the same. Java gives you two separate types, a fixed-size int[] and a dynamic ArrayList. Python gives you only the dynamic list, which stores pointers to objects. A JavaScript Array is an object whose keys happen to be index-like strings; V8 keeps it in a packed contiguous store while it stays dense, and switches to a dictionary when it does not.

array_basics.py

1# Python: list is the dynamic array (there is no built-in fixed-size array)

2arr = [7, 2, 9, 4, 1]

3arr[0] # O(1) read by index

4arr[-1] # negative index counts from the end, same as arr[len(arr)-1]

5arr.append(8) # append at the end, O(1) amortized

6arr.insert(0, 99) # insert at the front, O(n) shifting

7arr.pop() # remove the last element, O(1); arr.pop(0) is O(n)

8sub = arr[1:4] # a slice is a copy, O(k) time and O(k) space

10for v in arr: # iteration

11 print(v)

Common mistake: a list stores pointers to objects, not raw numbers, and slicing copies. For a fixed-size numeric array use the array module or NumPy. Do not build a 2D list with [[0]*m]*n: all n rows would be the same inner list.

Operation	Java (`ArrayList`)	Python (`list`)	JavaScript (`Array`)	Complexity
Create	`new ArrayList<>()`	`[]`	`[]`	O(1)
Length	`list.size()`	`len(arr)`	`arr.length`	O(1)
Read by index	`list.get(i)`	`arr[i]`	`arr[i]`	O(1)
Append at the end	`list.add(x)`	`arr.append(x)`	`arr.push(x)`	O(1) amortized
Delete at the end	`list.remove(size-1)`	`arr.pop()`	`arr.pop()`	O(1)
Insert at the front	`list.add(0, x)`	`arr.insert(0, x)`	`arr.unshift(x)`	O(n)
Slice	`list.subList(a, b)`*	`arr[a:b]`	`arr.slice(a, b)`	O(k)
Sort	`Collections.sort(list)`	`arr.sort()`	`arr.sort((a,b)=>a-b)`	O(n log n)
Contains	`list.contains(x)`	`x in arr`	`arr.includes(x)`	O(n)

* Java subList returns a view, not a copy. Changing the view changes the original list. This is the one place where the three slice operations differ in meaning.

§08

Two array techniques: two pointers and the sliding window

★ Interview core

A large share of array problems. Three worked examples, step by step.

The brute-force solution to an array problem is usually two nested loops, O(n²), checking every pair of indices. The two pointers family instead moves two indices each in one direction only. At every step a property of the problem rules out a whole group of candidates, which turns O(n²) into O(n). There are three forms:

FORM 01

Fast and slow, same direction

fast reads, slow writes, and everything left of slow is already arranged. This is the standard shape for in-place removal and compaction. See LC 283, 26, and 27.

FORM 02

Pointers moving toward each other

Start at both ends and move inward. Sorted order, or the fact that the shorter side limits the result, lets you discard one end at every step. See LC 11, 167, 15, and 42.

FORM 03

Sliding window

For contiguous subarrays: the right end adds, the left end removes, and the window keeps a quantity that can be updated step by step. See LC 209, 3, and 76.

WORKED A

LC 283 · Move Zeroes

EASY

Problem: move every 0 to the end of the array, keep the order of the non-zero values, and do it in place. Brute force: build a new array, copy the non-zero values, then pad with zeros. That is O(n) time but O(n) extra space, which the problem forbids. Solution: change the target. Do not move the zeros, move the non-zero values.

LC 283 · Two pointers in the same direction, step by step

slowfast

124

Start. slow marks the slot where the next non-zero value belongs. fast reads every element in turn. Goal: move the non-zero values to the front, and the zeros end up at the back.

1 / 7

lc283_move_zeroes.py

1class Solution:

2 def moveZeroes(self, nums: list[int]) -> None:

3 slow = 0 # where the next non-zero value belongs

4 for fast in range(len(nums)):

5 if nums[fast] != 0: # only non-zero values matter

6 # Python swaps in one line, no temporary variable needed

7 nums[slow], nums[fast] = nums[fast], nums[slow]

8 slow += 1 # the arranged region grows by one

Complexity and follow-up questions

Time O(n), because fast makes one pass. Space O(1). Interviewers often follow up: what if the value to move is not 0 but a given value? That is LC 27. What if the order of the zeros also has to be preserved? This solution already does that. The answer they are looking for is the loop invariant: everything left of slow is non-zero and in its original relative order.

WORKED B

LC 11 · Container With Most Water

MEDIUM

Problem: given n vertical lines, pick two so that the container they form with the x-axis holds the most water. The area is the distance between the two lines times the shorter one. Brute force: try every pair, O(n²). Solution: start at the widest pair and move inward, always moving the shorter side. The width will shrink no matter what, so only replacing the shorter line can make the area larger.

LC 11 · Pointers moving inward (the number in each cell is the line height)

L = 0 (height 1), R = 8 (height 7). Area = min(1, 7) × width 8 = 8. The shorter line is on the left, so move L to the right.

1 / 6

lc11_max_area.py

1class Solution:

2 def maxArea(self, height: list[int]) -> int:

3 l, r, best = 0, len(height) - 1, 0

4 while l < r:

5 area = min(height[l], height[r]) * (r - l)

6 best = max(best, area)

7 if height[l] < height[r]:

8 l += 1 # always move the shorter side

9 else:

10 r -= 1

11 return best

Why is it safe to move the shorter side?

Say the left line is the shorter one. Consider every pair that keeps this left line: the other line has to be somewhere between the current two, so the width is smaller, and the height is still limited by the same short left line. Every one of those pairs has an area no larger than the one just measured, so they can all be discarded together. Each step therefore removes a whole group of candidates without losing the answer, and n steps are enough: O(n²) becomes O(n). This argument is the expected answer in an interview.

WORKED C

LC 209 · Minimum Size Subarray Sum

MEDIUM

Problem: in an array of positive integers, find the length of the shortest contiguous subarray whose sum is at least target. Brute force: try every start and end, O(n²). Solution: a sliding window. Because every element is positive, the window sum only increases when the right end moves right and only decreases when the left end moves right. That is the invariant that makes it correct: once the sum drops below target, moving the left end further can never bring it back, so the left end never has to move backwards.

LC 209 · Sliding window (target = 7)

target = 7. The window is one contiguous piece of the array. The right end adds elements, the left end removes them.

1 / 7

lc209_min_subarray.py

1class Solution:

2 def minSubArrayLen(self, target: int, nums: list[int]) -> int:

3 l, s, ans = 0, 0, float("inf")

4 for r, v in enumerate(nums):

5 s += v # the right end adds an element

6 while s >= target: # shrink while the condition holds

7 ans = min(ans, r - l + 1)

8 s -= nums[l]

9 l += 1 # the left end removes an element

10 return 0 if ans == float("inf") else ans

Complexity, and the template for window problems

There is a while inside a for, but l and r only move forward, at most n steps each, so the total is at most 2n and the time is O(n). Three questions describe any window problem. What quantity does the window keep (here the sum)? When does it grow (here every step)? When does it shrink (here while the sum is at least target)? Answer those three and LC 3, 76, and 438 all follow the same shape. One warning: this window works because the values are positive. With negative numbers allowed the sum is no longer monotonic, and you need prefix sums instead.

§09

Problem set: 17 array problems

Hot 100 selection

Grouped by technique, easy to hard. Your progress is stored in this browser. Think for 30 seconds before opening a hint.

LC 26Remove Duplicates from Sorted ArrayTwo pointersIn placeEASY

LC 27Remove ElementTwo pointersIn placeEASY

LC 704Binary SearchBinary searchTemplate problemEASY

LC 35Search Insert PositionBinary searchFinding a boundaryEASY

LC 88Merge Sorted ArrayTwo pointersBack to frontEASY

LC 121Best Time to Buy and Sell StockOne passPrefix minimumEASY

LC 283Move ZeroesTwo pointersIn placeEASY

LC 167Two Sum II - Input Array Is SortedPointers moving inwardSorted inputMEDIUM

LC 238Product of Array Except SelfPrefix productTwo passesMEDIUM

LC 53Maximum SubarrayKadaneDynamic programmingMEDIUM

LC 56Merge IntervalsSortingIntervalsMEDIUM

LC 153SumSortingPointers moving inwardRemoving duplicatesMEDIUM

LC 189Rotate ArrayReversalIn placeMEDIUM

LC 54Spiral MatrixMatrixSimulationMEDIUM

LC 48Rotate ImageMatrixIn placeMEDIUM

LC 73Set Matrix ZeroesMatrixMarking in placeMEDIUM

LC 42Trapping Rain WaterPointers moving inwardPrecomputationHARD

§10

Chapter quiz

✎ Chapter quiz

Answer all 9 correctly to mark this chapter complete.

QUESTION 01 / 9

What is the time complexity of inserting one element at the front of an array of length n?

QUESTION 02 / 9

What is the most accurate description of appending to a dynamic array (ArrayList, Python list, JS Array)?

QUESTION 03 / 9

A long array (8 bytes per element) starts at address 2000. What is the address of arr[3]?

QUESTION 04 / 9

In Java, what is the main difference between int[] and ArrayList<Integer>?

QUESTION 05 / 9

In JavaScript, what are the complexities of arr.pop() and arr.shift()?

QUESTION 06 / 9

Which of these array operations are O(1)? (Select all that apply.)

QUESTION 07 / 9

A matrix with 3 rows and 5 columns is flattened into one array in row-major order. What is the flat index of matrix[2][3]?

QUESTION 08 / 9

In a hand-written dynamic array, if the resize added only one slot instead of doubling the capacity, what would n appends cost in total?

QUESTION 09 / 9

Binary search runs in O(log n) only when two conditions hold at the same time. Which two?

What to take away from this chapter

Everything about an array follows from address = base address + index × element size. That formula gives you O(1) random access, and it charges you for keeping the elements contiguous.
Do other elements have to move? That single question decides the cost of every array operation. At the end, O(1). At the front or in the middle, O(n), because of the shift, not because of any search.
A dynamic array is a fixed-size array plus a resize when it is full. One resize is O(n); append is O(1) amortized, not O(1) worst case. Java ArrayList grows by about 1.5, CPython over-allocates by a smaller amount, and V8 uses about 1.5 plus 16. Only the fact that growth is proportional matters for the amortized bound.
Binary search needs sorted data and O(1) random access together. With a closed interval the invariant is that the answer, if it exists, stays inside [left, right]; hence left <= right, mid ± 1, and a midpoint written as left + (right - left) / 2 in Java so it cannot overflow.
Two dimensions are a way of reading one dimension: flat index = row × number of columns + column in row-major order. In C and NumPy the block really is contiguous; Java int[][] is an array of row references. Reading row by row is faster because of cache lines, not because the complexity differs.
Three two-pointer forms: same direction for in-place compaction, inward for sorted data or a limiting shorter side, and the sliding window for contiguous subarrays. All three rest on the same idea: use a monotonic property to rule out candidates and turn O(n²) into O(n). Always be able to state the invariant.
Practical notes: the CPU cache favours contiguous memory, and the convenient calls shift(), insert(0, x), and add(0, x) are all O(n).