Overview

An array stores elements in one contiguous block of memory, so the address of element i is simply start + i × size. That arithmetic is why indexing is O(1) and why arrays are cache-friendly and fast in practice. The cost is rigidity: inserting or deleting in the middle shifts every element after it, which is O(n).

Most array problems are not about the array itself but about traversing it cleverly — keeping a running best, overwriting in place with a second index, or noticing that a matrix is just an array of arrays. Master the handful of moves below and a large share of "Easy" and "Medium" problems become routine.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Access by indexO(1)
Search (unsorted)O(n)
Append at endO(1) amortised
Insert / delete in the middleO(n)
Copy or slice of length kO(k)

Patterns to recognise

Running best

Use it for: Max profit, max subarray, running minimum.

Track the best answer so far and the best "state" ending at the current index in one pass.

Write pointer

Use it for: Remove elements, move zeroes, deduplicate.

Read every element; copy the keepers to position w and increment w.

Index as hash

Use it for: Values are in the range 1..n.

Use the sign or position of nums[v − 1] to mark that v was seen — O(1) extra space (first missing positive).

Code template

Kadane's algorithm — maximum subarray sum
def max_subarray(nums):
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)   # extend or restart
        best = max(best, current)
    return best

Common mistakes

  • Off-by-one errors on loop bounds — test with arrays of length 0, 1 and 2.
  • Removing items from a list while iterating over it skips elements; iterate over a copy or use a write pointer.
  • Sums of large arrays overflow 32-bit integers.
  • Python slicing (a[1:]) copies the data — fine for clarity, but it costs O(n) memory.

Quick check

Three questions on Arrays. Get all three right to earn +15 XP.

  1. What does it cost to insert a value at the front of an array of n elements?

  2. Kadane's algorithm finds the maximum subarray sum. What does it decide at each element?

  3. What makes reading arr[i] an O(1) operation?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Arrays?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor