AlgoScope

Array Algorithms and Techniques

One block of memory, indexed from zero, and everything that follows from that.

15 topics6 lessons1 families

An array is a run of equally sized slots laid next to each other in memory. That one decision is why reading a[i] costs the same whatever i is, and why inserting in the middle does not: the slots after it all have to move up by one.

Most array technique is about avoiding that move, or about reading the array fewer times. Two pointers walk in from the ends instead of trying every pair. A sliding window keeps a running answer instead of recomputing it. A prefix sum pays once so every range query afterwards is a subtraction.

Because the layout is so simple, arrays are also where complexity first becomes visible: you can watch a nested loop touch n squared cells, and watch a single pass touch n.

After this you can

  • Say what an index costs, and what an insert in the middle costs, and why
  • Choose between a second pass, a second array, and an in-place rearrangement
  • Recognise when two pointers or a sliding window replaces a nested loop
  • Use a prefix sum to turn repeated range questions into one subtraction
5✓01✓14✓22✓38✓4i

Index 4 holds 8. Running total 20.

Open in the player →or start at step 6

In this order

  1. Array TraversalVisit every slot once, in order. Nothing is skipped and nothing is revisited.
  2. Array SearchCheck each slot in turn until the value turns up or the array runs out.
  3. Array InsertMake room by shifting everything after the slot one place right, then write.
  4. Array DeleteClose the gap by shifting everything after the slot one place left.
  5. Reverse ArraySwap the outermost pair and step both pointers inward until they meet.
  6. Two Pointer TraversalTwo indices walk the array under a rule instead of a nested loop.
  7. Prefix SumStore running totals once, and any range sum becomes two lookups and a subtraction.
  8. Range Sum QueryThe sum of a range is the total up to its end minus the total before its start.
  9. Maximum SubarrayThe largest total of any run of neighbours. Kadane solves it in one pass.
  10. Kadane's AlgorithmCarry the best run ending here. A negative run only hurts, so drop it and start over.

Also in this category

Array Techniques

Where people go wrong

Off by one at the ends

The last index is n - 1, and a range that includes both ends has to - from + 1 elements. Most array bugs are one of these two, not the algorithm.

Growing an array inside a loop

A dynamic array doubles its capacity and copies, so appending is cheap on average but not every time. Building a result by repeatedly inserting at the front is quadratic; build it backwards or push and reverse.

Or a different category

Linked List Algorithms

You insert and delete in the middle far more often than you read by index.

Hashing

You look things up by value rather than by position.

Lessons that teach these