λDSA Learning Hubpart of DSA Atlas

Arrays

Beginner~3h · 8 lessons12 practice problems

Contiguous memory, O(1) indexing, and the traversal, insertion, rotation and Kadane techniques that power a third of all interview questions.

0 of 8 lessons checked off

Introduction

What it is

  • An array is a block of elements stored side by side in memory, addressed by index. Python's list is a dynamic array: it keeps a contiguous buffer and grows it automatically.
  • Because element i lives at a predictable memory offset, reading or writing any index costs O(1) — the defining property everything else trades against.

Why it matters

  • Arrays are the default container: fastest constant factors, cache-friendly, and the substrate for strings, matrices, heaps, and hash tables.
  • The cost asymmetry — O(1) reads but O(n) middle insertions — is the reason other structures (linked lists, trees, hash maps) exist at all. Understanding arrays deeply makes every later trade-off obvious.

How it works

  • Indexing computes an address: base + i × element_size. That's why it is O(1) and why indexes start at 0.
  • Inserting or deleting anywhere but the end must shift every later element to keep the block contiguous — O(n).
  • Growth uses doubling: when the buffer fills, allocate roughly twice the space and copy — O(n) occasionally, O(1) amortised per append.

Where it's used

  • Image pixels, audio samples, database rows in a column store, and every spreadsheet column are arrays — anything scanned in bulk benefits from contiguity.
  • CPU caches fetch memory in 64-byte lines, so iterating an array is dramatically faster than chasing pointers in a linked structure of the same size.

In interviews

  • Direct array manipulation: rotate, merge sorted arrays in place, move zeroes, spiral-order a matrix.
  • As the substrate for patterns: two pointers, sliding window, prefix sums, and Kadane's algorithm all assume O(1) indexing.
Analogy: An array is a row of numbered parking spots: driving straight to spot 37 is instant, but squeezing a new car between spots 3 and 4 means every car behind must move back one space.

Interactive diagram

Watch what really happens when you call list.insert(2, 99) — this is where the O(n) comes from.

Start

Insert 99 at index 2. Every element from index 2 onward must shift one slot right first.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. One-dimensional arrays and memory

    Contiguity, base + offset indexing, dynamic-array growth.

    15 min
  2. Array traversal

    Forward, backward, enumerate, and index vs value iteration.

    10 min
  3. Insert and delete operations

    Why middle edits shift elements; end edits are O(1).

    20 min
  4. Two-dimensional arrays and matrix traversal

    Row-major layout, nested loops, and spiral/diagonal walks.

    25 min
  5. Rotation

    The three-reversal trick for rotating in place.

    20 min
  6. Kadane's algorithm

    Maximum subarray sum in one pass by extending or restarting.

    25 min
  7. In-place operations

    Overwrite-and-shrink, swap-to-end, and the read/write pointer idiom.

    20 min
  8. Prefix sums and difference arrays (preview)

    Precompute once, answer range queries in O(1) — full topic later.

    10 min

Operations

Insert at index

Make room by shifting the suffix one slot right, then write. End-appends skip the shifting entirely.

Start

Insert 99 at index 2. Every element from index 2 onward must shift one slot right first.

def insert_at(arr: list[int], index: int, value: int) -> None:    """Insert value at index, shifting later elements right. O(n)."""    arr.append(0)                     # grow by one slot    for i in range(len(arr) - 1, index, -1):        arr[i] = arr[i - 1]           # shift right, back to front    arr[index] = value
Time: O(n) — O(1) amortised when appending at the endSpace: O(1) extra

Edge cases

  • index == len(arr) degenerates to append.
  • index == 0 shifts every element — the worst case.
  • Out-of-range index should raise, not silently clamp.

Common mistakes

  • Shifting front-to-back, which overwrites values before they are copied.
  • Forgetting that repeated front-inserts in a loop cost O(n²) total.

Delete at index

Overwrite the victim by shifting the suffix one slot left, then shrink. There are no holes in an array.

Mark the victim

Delete index 2 (value 99). Arrays cannot leave holes, so later elements shift left.

def delete_at(arr: list[int], index: int) -> int:    """Remove and return arr[index], shifting later elements left. O(n)."""    removed = arr[index]    for i in range(index, len(arr) - 1):        arr[i] = arr[i + 1]           # shift left, front to back    arr.pop()                         # drop the duplicated last slot    return removed
Time: O(n) — O(1) when deleting the last elementSpace: O(1) extra

Edge cases

  • Deleting from an empty array must raise IndexError.
  • Deleting the last index does zero shifting.
  • If order doesn't matter, swap with the last element and pop: O(1).

Common mistakes

  • Deleting from a list while iterating it forward — indexes shift under you; iterate backwards or build a new list.
  • Using remove(value) (O(n) search + O(n) shift) when the index is already known.

Rotate right by k (three reversals)

Reverse the whole array, then reverse the first k and the rest separately — rotation in place with no extra buffer.

Rotate right by k (three reversals)
def rotate(nums: list[int], k: int) -> None:    """Rotate right by k steps, in place. O(n) time, O(1) space."""    n = len(nums)    if n == 0:        return    k %= n                      # rotating by n is a no-op    def reverse(lo: int, hi: int) -> None:        while lo < hi:            nums[lo], nums[hi] = nums[hi], nums[lo]            lo, hi = lo + 1, hi - 1    reverse(0, n - 1)           # [1,2,3,4,5,6,7] -> [7,6,5,4,3,2,1]    reverse(0, k - 1)           # k=3 ->            [5,6,7,4,3,2,1]    reverse(k, n - 1)           #                    [5,6,7,1,2,3,4]
Time: O(n)Space: O(1)

Edge cases

  • k larger than n — always take k % n first.
  • Empty array or k == 0: return immediately.
  • k % n == 0 leaves the array unchanged.

Common mistakes

  • Popping and re-inserting one element k times: O(n·k).
  • Allocating a second array when the prompt says in place.

Kadane's algorithm (maximum subarray)

One pass, two numbers: the best sum ending here (extend or restart) and the best sum anywhere.

Initialise

current and best both start at the first value, -2. current tracks the best subarray ending here.

current
-2
best
-2
def max_subarray(nums: list[int]) -> int:    """Maximum sum over all contiguous subarrays. O(n) / O(1)."""    best = current = nums[0]    for x in nums[1:]:        current = max(x, current + x)   # restart or extend        best = max(best, current)    return best
Time: O(n)Space: O(1)

Edge cases

  • All-negative input: the answer is the largest single element — never return 0 unless empty subarrays are allowed.
  • Single element: both best and current are that element.

Common mistakes

  • Initialising best to 0, which breaks on all-negative arrays.
  • Resetting current to 0 instead of to the current element.

Complexity analysis

OperationBestAverageWorstSpace
Access by indexO(1)O(1)O(1)—
Search (unsorted)O(1)O(n)O(n)O(1)
Append at endO(1)O(1)O(n) on resize—
Insert / delete at front or middleO(1) at endO(n)O(n)O(1)
Rotate in placeO(n)O(n)O(n)O(1)
Kadane / single scanO(n)O(n)O(n)O(1)

Python implementation

Production-quality code with type hints, validation, and docstrings.

A dynamic array from scratch (what Python's list does underneath)
class DynamicArray:    """A growable array built on a fixed-size buffer, mirroring    CPython's list: O(1) index, amortised O(1) append."""    def __init__(self) -> None:        self._capacity = 4        self._size = 0        self._buffer: list[object] = [None] * self._capacity    def __len__(self) -> int:        return self._size    def _check_index(self, index: int) -> None:        if not 0 <= index < self._size:            raise IndexError(f"index {index} out of range for size {self._size}")    def get(self, index: int) -> object:        self._check_index(index)

What interviewers expect you to know

Properties you must state cold

  • O(1) random access comes from address arithmetic on contiguous memory.
  • Middle insert/delete is O(n) because contiguity forbids holes.
  • Python list append is amortised O(1) via capacity doubling.
  • Slicing copies: nums[a:b] costs O(b−a) time and space.

Frequent follow-ups

  • "Can you do it in place?" — the interviewer wants O(1) extra space: think reversal tricks, read/write pointers, or swapping to the end.
  • "What if the array is sorted?" — sortedness unlocks binary search and two pointers; always ask or note it.
  • "How would you handle streaming input?" — Kadane-style running state that never re-reads old elements.

How to explain arrays in an interview

  • Frame trade-offs as read-heavy vs edit-heavy: arrays win when reads dominate; linked structures win when middle edits dominate.
  • When you write nums[i], say what invariant i maintains ('everything left of write is finalised') — invariants are what interviewers grade.

Common mistakes

Off-by-one on boundaries

range(n) visits 0..n−1; the last index is n−1; range(a, b) excludes b. Trace one tiny example on paper before running.

Mutating while iterating

Removing items from a list inside `for x in arr` skips elements as indexes shift. Iterate a copy, iterate backwards, or build a new list.

O(n) operations disguised as O(1)

insert(0, x), pop(0), `in`, and slicing are all linear. Counting them as constant flips your complexity answer from right to wrong.

Returning 0 for all-negative Kadane

best must start at nums[0], not 0 — the maximum subarray of [-3, -1, -2] is −1.

Row/column confusion in 2-D arrays

matrix[r][c]: r selects the row list, c the element. Building grids with [[0]*cols]*rows aliases every row to the same list — use a comprehension.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (4)

Medium (7)

Hard (1)

Topic quiz

6 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Complexity1. Why is reading arr[500000] from a million-element array O(1)?
  2. Code output2. What does this print?
    nums = [1, 2, 3, 4, 5]nums.insert(0, 9)nums.pop()print(nums)
  3. Concept3. You must rotate an array right by k in place with O(1) extra space. Which approach works?
  4. Code output4. Kadane's algorithm on nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] returns…
  5. Scenario5. grid = [[0] * 3] * 3; grid[0][0] = 7. What is grid[2][0], and why?
  6. Complexity6. Appending n items one by one to an empty Python list costs…
0 of 6 answered

Frequently asked questions

Is a Python list the same as an array?

It's a dynamic array of object references. The indexing and shifting behaviour matches classic arrays; the differences (heterogeneous elements, reference indirection) affect constants, not Big O.

When should I choose a linked list over an array?

When you do many insertions/deletions at known positions (especially the front) and few random reads. If reads dominate — the common case — arrays win.

What's the fastest way to delete when order doesn't matter?

Swap the victim with the last element and pop: O(1). Interviewers love this trick in 'remove element' style questions.

Summary & cheat sheet

Key takeaways

  • Arrays trade O(n) middle edits for O(1) reads — the foundational trade-off of data structures.
  • Shift right back-to-front to insert; shift left front-to-back to delete.
  • Rotation = three reversals; deletion-without-order = swap-and-pop.
  • Kadane: current = max(x, current + x); best tracks the answer. O(n), handles negatives correctly if seeded from nums[0].

Formulas & cheat sheet

  • address(i) = base + i × element_size
  • Shifts for insert at i: n − i; for delete at i: n − i − 1
  • Rotate right k: reverse(0, n−1), reverse(0, k−1), reverse(k, n−1) with k %= n

Interview checklist

  • I can implement insert/delete with explicit shifting loops.
  • I can rotate in place and explain why k %= n first.
  • I can run Kadane on paper for a mixed-sign array.
  • I know which list operations are secretly O(n).