DSA · Arrays

n boxes in a row, numbered from 0

Q: What is an array?

A fixed-size block of contiguous memory holding n values of the same type, laid one after another with no gaps. Because every element is the same width, the address of a[i] is just base + i × sizeof(element) , so any cell is reachable in constant time. That contiguity is the whole trade: reads are instant, but the size is fixed up front and inserting in the middle means shifting everything after it.

Q: Why does the index start at 0 and not 1?

Because the index is an offset, not a serial number. a[0] means zero elements past the start of the block, which is the first element. A 1-based scheme would force the machine to subtract 1 on every access or waste one element of memory. The consequence you have to carry around is that the last valid index is n − 1 , never n.

Q: Why is reading a[i] O(1) while reaching the i-th node of a linked list is O(i)?

The array computes an address; the list follows pointers. base + i × size is one multiplication and one addition no matter what i is, so a[0] and a[999999] cost the same. A linked list stores each node wherever memory happened to be free, so the only way to reach node i is to start at the head and hop i times.

Q: For an array of size n, what is the last valid index, and what happens if you read a[n]?

The last valid index is n − 1 , so a[n] is one element past the end. In C or C++ nothing checks it: you read whatever bytes live there and the program carries on with a wrong value, or corrupts memory if you write. Java throws ArrayIndexOutOfBoundsException and Python raises IndexError . The unchecked case is the dangerous one, because the damage surfaces somewhere else entirely.

Q: What is the most common bug you see in array loops?

Writing i <= n instead of i < n — confusing the size with the last index. With n = 5 that runs six iterations over five cells and touches a[5] . The mirror of it is a loop that stops at i < n − 1 and silently ignores the last element. Reading the guard out loud as "up to but not including n" is what stops both.

Q: Why is inserting into the middle of an array O(n)?

Because the block has to stay contiguous. To open a slot at index i you move every element from i to n − 1 one place right, which is up to n moves. Deleting is the mirror — everything after the hole shifts left. Appending at the end is the cheap case and is O(1), as long as there is spare capacity to append into.

Q: How do you find the maximum of an array, and why can you not stop early?

One traversal: seed best with a[0] , then for i from 1 to n − 1 replace best whenever a[i] is bigger. You cannot stop early because until the last cell has been read, the next one could still be larger. On 5 1 4 2 3 the answer is fixed after the very first cell, but there is no way to know that, so it is n reads and exactly n − 1 comparisons in every case.

Q: Someone seeds best with 0 instead of a[0]. Give me an input that breaks it.

Any array whose values are all negative. On −9 −3 −7 it returns 0, and 0 is not in the array. Seeding from a[0] guarantees the answer is a real element. If you must seed with a constant, use the type minimum such as INT_MIN or Integer.MIN_VALUE , and handle the empty array as a separate case either way.

Q: Array or linked list — how do you choose?

Array wins on indexing (O(1) against O(n)), on memory (no per-node pointer), and on cache behaviour, because a traversal reads consecutive addresses. Linked list wins on inserting or deleting once you already hold the node — an O(1) splice against O(n) shifting — and it never needs one big contiguous block. In practice arrays win by default; you switch when middle-insertion dominates the workload.

Q: Is a Python list or a Java ArrayList the same thing as a C array?

Underneath, yes — both hold a contiguous array plus a count of how much of it is used. The difference is that they reallocate: when the block fills they allocate a bigger one, usually about double, and copy everything across. That copy is O(n), but it happens rarely enough that appending is O(1) amortised. Indexing is still O(1) and middle insertion is still O(n).

An array is one unbroken block of memory holding n values of the same type. You will see why a[i] costs the same whether i is 0 or 999999, walk a single left-to-right traversal over 5 1 4 2 3, and kill the two bugs every fresher writes: seeding the answer with a value the array does not contain, and letting i run all the way to n.

Walk the index across 5 1 4 2 3 →

a[0]base address + 0 × 4 bytes

→

a[4]base address + 4 × 4 bytes · the last cell

→

a[5]one multiplication past the end · not a cell

01 The idea

Why a[i] is instant

An array is one unbroken run of memory holding n values of the same type, laid back to back with nothing in between. Because every value takes the same number of bytes, the machine does not have to hunt for a[i] — it computes where the cell lives. The address is the start of the block plus i times the size of one element. One multiplication, one addition, one read.

That is why a[0] and a[999999] cost exactly the same. It is also why counting starts at 0 rather than 1: index 0 means zero elements past the start, which is the first element itself. The last legal index is therefore n − 1, and the one-cell gap between n − 1 and n is where most first-year array bugs live.

An array is n boxes side by side in memory. The index is not a name for a box — it is how many boxes to step over from the start. So the first box is 0, the last box is n − 1, and a[n] is not a box at all.

ContiguousThe n elements sit in one unbroken run of memory, each the same width. Nothing else is stored between them, and that is what makes the address arithmetic work.

Index (zero-based)How many elements to step past the start. a[0] is the first value, a[n − 1] is the last, and there is no a[n].

TraversalOne pass that visits every element once, left to right. It costs n reads. Almost everything you do to a whole array is a traversal with a different body.

02 Worked example

Finding the largest of 5 1 4 2 3

Five values, 5 1 4 2 3, and one rule: read each cell once and hold on to the biggest value seen so far. The variable holding it is best. It is seeded with a[0] rather than with 0, so it is always a value that really exists in the array. On each row the label on the left is the current value of i, the rose box is the cell being read, and the emerald box is the cell best came from.

index01234

i = 0 · seed51423best ← a[0] = 5 · i starts at 1

i = 1514231 > 5 ? no · best stays 5

i = 2514234 > 5 ? no · best stays 5

i = 3514232 > 5 ? no · best stays 5

i = 4514233 > 5 ? no · best stays 5

i = 551423i < 5 is false · stop · a[5] is not a cell

result51423best = 5 · 5 reads, 4 comparisons

Row seven is the row that matters. If the loop had been written i <= n, the walk would take one more step and read a[5]. In C nothing stops it: you get whatever bytes happen to sit after the block, and the program prints a confident wrong answer. In Java you get ArrayIndexOutOfBoundsException, in Python an IndexError. The silent version is the one that hurts.

best was already correct after the seed row and never changed again. That is not something you can rely on. Until the last cell has been read, the value that beats 5 could always be the next one — so the walk cannot stop early, and it costs n reads every single time. Notice also that nothing in those rows is specific to "largest": read one cell, fold it into a variable, move on. Change the variable and change the fold, and the same walk computes the sum or counts the even numbers.

03 The code

The traversal skeleton, and the two bugs

Both loops below try to find the maximum of 5 1 4 2 3. The left one gets it wrong twice over, and on this particular input it may well still print 5: the seed bug is invisible because every value is positive, and the out-of-bounds read only changes the answer if the bytes sitting past the block happen to be bigger than 5. That is exactly why the bugs survive into submitted code — they are not reliably wrong, they are unreliably right. The right one is the skeleton you will reuse for the rest of the course: seed an accumulator, walk from the first legal index to the last, fold each cell in, report.

Broken — the two classic bugs

best = 0                  # bug 1: 0 is not in the arrayfor i = 0; i <= n; i++    # bug 2: i reaches n    if a[i] > best        best = a[i]print best

Correct — the traversal skeleton

best = a[0]               # seed from inside the arrayfor i = 1; i < n; i++     # last legal index is n - 1    if a[i] > best        best = a[i]print best

Why seed with a[0] and not with 0? Seeding with 0 happens to work on 5 1 4 2 3 because every value is positive. Hand the same loop −9 −3 −7 and it answers 0, a number that is not in the array at all. Seeding from a[0] can only ever return a real element. The price is that the array must be non-empty, so check n > 0 before you start.

Why i < n and never i <= n? The n cells are numbered 0 to n − 1, so i = n is one cell past the end. With n = 5 the broken loop runs i = 0, 1, 2, 3, 4, 5 — six iterations over five cells. This is the size-versus-size-minus-one confusion, and it is the single most common array bug in a written test. Say the loop out loud as "i goes up to but not including n" and the off-by-one stops happening.

Why does the correct version start at i = 1? Because a[0] has already been folded in by the seed. Starting at 0 would compare a[0] with itself, which is harmless for a maximum but is a real bug the moment the body adds instead of compares. The seed decides where i starts — that pairing is the thing to memorise.

Nothing in that skeleton mentions "largest". The walk, the guard and the index arithmetic are fixed; only the seed and the body change. Here are three different jobs done by the same five rows of walking, all over 5 1 4 2 3.

# one walk, three bodies — over 5 1 4 2 3seed sum   = 0     i from 0    sum = sum + a[i]             → 15seed evens = 0     i from 0    if a[i] % 2 == 0: evens++    → 2seed best  = a[0]  i from 1    if a[i] > best: best = a[i]  → 5

Why do two of them start at 0 and one at 1? The seed again. sum and evens start from 0, a value that is not in the array, so cell 0 has not been counted yet and the walk must read it. best starts from a[0], which has been counted, so the walk begins at the next cell. Get this backwards and your sum quietly drops the first element or adds it twice — and the total still looks plausible, so nobody notices.

05 Cheat sheet

What an array costs

Operation	Cost	Why
Read or write a[i]	`O(1)`	One multiplication and one addition on the base address. The value of i does not matter: a[0] and a[999999] cost the same.
Traverse all n cells	`O(n)`	Every cell read exactly once. Sum, maximum, count, print — the same walk with a different body.
Search for a value, unsorted	`O(n)`	You have no idea where it is, so the worst case reads every cell before finding it or giving up.
Insert or delete in the middle	`O(n)`	The block has to stay contiguous, so every element after the hole shifts by one.
Grow beyond the declared size	`O(n)`	A fixed array cannot grow. You allocate a bigger block and copy all n values across.
Space for n elements	`O(n)`	n × the size of one element, and nothing else. No per-element pointer or header.

Zero-indexedValid indices run 0 to n − 1. a[n] is out of bounds in every language; only some of them tell you.

Fixed sizeA C array has its length baked in at declaration. Vectors, ArrayLists and Python lists are arrays underneath that reallocate when they fill up.

Same type, same widthEvery cell holds the same type, so every cell is the same number of bytes. Break that and the address arithmetic stops working.

06 Where & why

When the container should be an array

An array is the cheapest container there is — no pointers, no hashing, nothing but a block of memory and some arithmetic. What you pay for that is rigidity. The size is decided up front, and anything that changes the middle costs a full O(n) shuffle.

Reach for it when…

You know roughly how many itemsMarks for 60 students, 26 letter counts, a 9 × 9 board. A block sized once beats a structure that grows.

You index far more than you insertReads are O(1) and middle insertions are O(n), so the ratio between the two is the entire decision.

You will walk it end to endContiguous memory is what the CPU cache is built for. The same traversal over an array beats one over a linked list of equal length, even though both are O(n).

The index itself carries meaningA seating chart where seat[k] says whether seat k is taken, or a month table where rain[d] holds the rainfall on day d. The position is the information, so the lookup is free.

Use something else when…

Situation	Better choice	Why
Items arrive and leave at the front constantly	Linked list, or a deque	Shifting n cells on every insert is O(n). A linked list splices a node in at O(1) once you are holding it.
You look items up by name, not by position	Hash map / dictionary	Scanning an array for a key is O(n). A hash map answers in O(1) on average and does not care about order.
The count is unknown and can keep growing	Dynamic array — vector, ArrayList, Python list	Still an array underneath, but it reallocates and copies for you, which makes appending O(1) amortised.
You need the smallest or largest item repeatedly	Heap / priority queue	Re-walking the array is O(n) per query. A heap hands you the extreme in O(1) and removes it in O(log n).

Nearly every container you meet later is an array wearing a costume — a hash table is an array of buckets, a heap is an array with an index rule, a dynamic array is an array that copies itself when full. Getting a[i], i < n and the traversal skeleton right here is what makes all of those readable.

07 Interview questions

What interviewers actually ask

Eleven questions in the order an interview escalates: what an array is, why the index starts at 0, what happens at a[n], and then the container comparison that decides the round.

What is an array?

A fixed-size block of contiguous memory holding n values of the same type, laid one after another with no gaps. Because every element is the same width, the address of a[i] is just base + i × sizeof(element), so any cell is reachable in constant time. That contiguity is the whole trade: reads are instant, but the size is fixed up front and inserting in the middle means shifting everything after it.

Why does the index start at 0 and not 1?

Because the index is an offset, not a serial number. a[0] means zero elements past the start of the block, which is the first element. A 1-based scheme would force the machine to subtract 1 on every access or waste one element of memory. The consequence you have to carry around is that the last valid index is n − 1, never n.

Why is reading a[i] O(1) while reaching the i-th node of a linked list is O(i)?

The array computes an address; the list follows pointers. base + i × size is one multiplication and one addition no matter what i is, so a[0] and a[999999] cost the same. A linked list stores each node wherever memory happened to be free, so the only way to reach node i is to start at the head and hop i times.

For an array of size n, what is the last valid index, and what happens if you read a[n]?

The last valid index is n − 1, so a[n] is one element past the end. In C or C++ nothing checks it: you read whatever bytes live there and the program carries on with a wrong value, or corrupts memory if you write. Java throws ArrayIndexOutOfBoundsException and Python raises IndexError. The unchecked case is the dangerous one, because the damage surfaces somewhere else entirely.

What is the most common bug you see in array loops?

Writing i <= n instead of i < n — confusing the size with the last index. With n = 5 that runs six iterations over five cells and touches a[5]. The mirror of it is a loop that stops at i < n − 1 and silently ignores the last element. Reading the guard out loud as "up to but not including n" is what stops both.

Why is inserting into the middle of an array O(n)?

Because the block has to stay contiguous. To open a slot at index i you move every element from i to n − 1 one place right, which is up to n moves. Deleting is the mirror — everything after the hole shifts left. Appending at the end is the cheap case and is O(1), as long as there is spare capacity to append into.

How do you find the maximum of an array, and why can you not stop early?

One traversal: seed best with a[0], then for i from 1 to n − 1 replace best whenever a[i] is bigger. You cannot stop early because until the last cell has been read, the next one could still be larger. On 5 1 4 2 3 the answer is fixed after the very first cell, but there is no way to know that, so it is n reads and exactly n − 1 comparisons in every case.

Someone seeds best with 0 instead of a[0]. Give me an input that breaks it.

Any array whose values are all negative. On −9 −3 −7 it returns 0, and 0 is not in the array. Seeding from a[0] guarantees the answer is a real element. If you must seed with a constant, use the type minimum such as INT_MIN or Integer.MIN_VALUE, and handle the empty array as a separate case either way.

Array or linked list — how do you choose?

Array wins on indexing (O(1) against O(n)), on memory (no per-node pointer), and on cache behaviour, because a traversal reads consecutive addresses. Linked list wins on inserting or deleting once you already hold the node — an O(1) splice against O(n) shifting — and it never needs one big contiguous block. In practice arrays win by default; you switch when middle-insertion dominates the workload.

Is a Python list or a Java ArrayList the same thing as a C array?

Hard

Return the largest sum obtainable from any contiguous stretch of the array, using a single traversal.

Follow-up

The obvious solution tries every start and every end, which is O(n²) — getting it in one pass is the entire exercise. And the lesson array hides the difficulty: 5 1 4 2 3 is all positive, so the answer is simply the whole array. Test on −2 1 −3 4 −1 2 1, where taking everything is wrong.

Show the hint

The best block ending at cell i is either a[i] on its own or a[i] added to the best block ending at i − 1. Keep that number, and keep the largest value it has ever reached.