DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Dynamic Arrays

The Problem with Static Arrays

A static array is fixed at creation. You declare int[100] and you have exactly 100 slots — no more, no less. If you need to store 101 items, you are stuck.

This constraint forces an uncomfortable choice before you start: guess the maximum size you will ever need, over-allocate to be safe, and waste memory. Or under-allocate, run out of space, and crash.

Real programs do not know their data size in advance. A contact list grows as users add contacts. A log file grows as events occur. A shopping cart grows as items are added. Every real-world collection changes size dynamically.

Dynamic arrays solve this by starting with a fixed block of memory and automatically growing when capacity is exhausted. From the outside, they look like unlimited collections. Under the hood, they are carefully engineered static arrays that resize themselves.

This page explains exactly how that resizing works, what it costs, and why it matters.

Dynamic Arrays in Each Language

Every major language provides a built-in dynamic array. Each is backed by a static array internally — they just hide the resizing from you.

Language	Dynamic Array	Static Array
Java	`ArrayList<Integer>`	`int[]`
Python	`list`	`array.array` (rarely used)
C++	`std::vector<int>`	`int arr[n]`
JavaScript	`Array`	`Int32Array` (TypedArray)

Python's list is the most transparent — it is always a dynamic array with no static equivalent for general use. JavaScript's Array is similarly always dynamic. Java and C++ explicitly separate the two: int[] is static, ArrayList/vector is dynamic.

How Resizing Works

A dynamic array maintains two numbers internally:

›Size — how many elements are currently stored (what you see)
›Capacity — how many elements the underlying static array can hold (internal limit)

When size == capacity and you try to add another element, the dynamic array:

›Allocates a new, larger static array (typically 2× the current capacity)
›Copies all existing elements from the old array to the new one
›Frees the old array
›Adds the new element to the new array
›Updates capacity to the new array's size

Initial state: capacity=4, size=0
  [_, _, _, _]   ← 4 empty slots

Add 10: capacity=4, size=1
  [10, _, _, _]

Add 20: capacity=4, size=2
  [10, 20, _, _]

Add 30: capacity=4, size=3
  [10, 20, 30, _]

Add 40: capacity=4, size=4
  [10, 20, 30, 40]   ← capacity full

Add 50: SIZE == CAPACITY → RESIZE
  Step 1: Allocate new array of size 8 (2×4)
  Step 2: Copy [10, 20, 30, 40] to new array
  Step 3: Free old array
  Step 4: Add 50
  [10, 20, 30, 40, 50, _, _, _]   ← capacity=8, size=5

Add 60, 70, 80: capacity=8, size=8
  [10, 20, 30, 40, 50, 60, 70, 80]   ← capacity full again

Add 90: RESIZE again
  New capacity = 16, copy all 8 elements, add 90

The capacity doubles each time. This exponential growth means resizes happen less and less frequently as the array gets larger.

Implementing a Dynamic Array from Scratch

The best way to understand dynamic arrays is to build one. This implementation mirrors what ArrayList, Python list, and std::vector do internally.

Java

public class DynamicArray {

    private int[] data;       // The underlying static array
    private int size;         // Number of elements currently stored
    private int capacity;     // Total slots in the underlying array

    public DynamicArray() {
        capacity = 4;         // Start with capacity 4
        data = new int[capacity];
        size = 0;
    }

    // Add element to the end — O(1) amortized
    public void add(int value) {
        if (size == capacity) {
            resize();         // Expand before adding
        }
        data[size] = value;
        size++;
    }

    // Access element by index — O(1)
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return data[index];
    }

    // Update element by index — O(1)
    public void set(int index, int value) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        data[index] = value;
    }

    // Current number of elements
    public int size() { return size; }

    // Internal capacity (not typically exposed, shown for learning)
    public int capacity() { return capacity; }

    // Doubles the capacity and copies all elements — O(n)
    private void resize() {
        capacity = capacity * 2;
        int[] newData = new int[capacity];

        // Copy every element to the new array
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }

        data = newData;
        System.out.println("  [Resize] new capacity = " + capacity);
    }

    public static void main(String[] args) {
        DynamicArray arr = new DynamicArray();

        System.out.println("Adding elements 1 through 9:");
        for (int i = 1; i <= 9; i++) {
            arr.add(i * 10);
            System.out.println("  Added " + (i * 10)
                + " → size=" + arr.size()
                + ", capacity=" + arr.capacity());
        }

        System.out.println("\nGet index 3: " + arr.get(3));
        arr.set(3, 999);
        System.out.println("After set(3, 999): " + arr.get(3));
    }
}

Output:
Adding elements 1 through 9:
  Added 10 → size=1, capacity=4
  Added 20 → size=2, capacity=4
  Added 30 → size=3, capacity=4
  Added 40 → size=4, capacity=4
  [Resize] new capacity = 8
  Added 50 → size=5, capacity=8
  Added 60 → size=6, capacity=8
  Added 70 → size=7, capacity=8
  Added 80 → size=8, capacity=8
  [Resize] new capacity = 16
  Added 90 → size=9, capacity=16

Get index 3: 40
After set(3, 999): 999

Dry Run: Resize Sequence

Starting capacity = 4

Elements added → [Resize points]:
  1st: size=1,  cap=4   (75% free)
  2nd: size=2,  cap=4   (50% free)
  3rd: size=3,  cap=4   (25% free)
  4th: size=4,  cap=4   (0% free — full)
  5th: RESIZE → cap=8,  copy 4 elements,  size=5
  ...
  8th: size=8,  cap=8   (0% free — full)
  9th: RESIZE → cap=16, copy 8 elements,  size=9
  ...
  16th: size=16, cap=16  (full)
  17th: RESIZE → cap=32, copy 16 elements, size=17

Resize happens at:    5, 9, 17, 33, 65, 129, ...
Elements copied at:   4, 8, 16, 32, 64, 128, ...

Total elements copied for n insertions:
  = 1 + 2 + 4 + ... + n/2 (geometric series)
  ≈ n

Total work: n insertions + n copies = 2n = O(n)
Amortized per insertion: O(n) / n = O(1)

Amortized O(1): Why Append Is "Effectively" Constant

The amortized analysis is important enough to revisit precisely.

The geometric series argument shows that across n appends, the total number of element copies during all resizes is at most n. Combined with the n append operations themselves, total work is 2n = O(n). Divided by n operations, the amortized cost per append is O(1).

Think of it as a prepaid cost. Each cheap append pre-pays a small amount toward the next expensive resize. When the resize happens, it is already "paid for."

Potential function analogy:
  Each element stored beyond the halfway point of current capacity
  represents one "prepaid" copy for the next resize.

  When capacity = 8 and size = 5:
    Elements beyond half (4): 1 element
    Prepaid for resize: 1 copy
  
  When size hits 8 (capacity full):
    Elements beyond half (4): 4 elements
    All 8 copies during resize are covered by prepaid costs

This is why amortized O(1) holds — no single append pays for
more than a constant amount of total future copy work.

Capacity Growth Strategies

Not all dynamic arrays double their capacity. Different growth strategies make different tradeoffs:

Strategy	Growth Factor	Result
Doubling (×2)	2.0	Fewer resizes, more wasted space
1.5×	1.5	More resizes, less wasted space
Fixed increment (+10)	+10	O(n²) total copies — bad
Python actual growth	~1.125×	Tuned for memory efficiency

Fixed increment (+10) is catastrophically bad. Each resize copies n elements, and with n/10 resizes, total copy work is O(n²/10) = O(n²). Doubling (O(n) total copies) and 1.5× are both O(n) total but differ in memory overhead.

Python's actual growth factors are computed from a formula that produces increments of 0, 4, 8, 16, 25, 35, 46, 58, 72, 91... — growing roughly 12.5% each time for small lists, amortizing to O(1) while minimizing wasted capacity.

Observing Real Language Internals

You can observe capacity growth directly in Python and Java.

Java

import java.util.ArrayList;
import java.lang.reflect.Field;

public class CapacityObserver {

    // Uses reflection to peek at ArrayList's internal array size
    // This is for educational purposes only
    public static int getCapacity(ArrayList<?> list) throws Exception {
        Field field = ArrayList.class.getDeclaredField("elementData");
        field.setAccessible(true);
        Object[] elementData = (Object[]) field.get(list);
        return elementData.length;
    }

    public static void main(String[] args) throws Exception {
        ArrayList<Integer> list = new ArrayList<>();

        System.out.println("Java ArrayList capacity growth:");
        System.out.printf("%-10s %-10s%n", "Size", "Capacity");

        int prevCap = 0;
        for (int i = 0; i < 20; i++) {
            list.add(i);
            int cap = getCapacity(list);
            if (cap != prevCap) {
                System.out.printf("%-10d %-10d  ← resize%n", list.size(), cap);
                prevCap = cap;
            } else {
                System.out.printf("%-10d %-10d%n", list.size(), cap);
            }
        }
    }
}

Output (Python approximate):
Python list capacity growth:
Size     Bytes      Approx Capacity
1        88         4
2        88         4
3        88         4
4        88         4
5        120        8         ← resize
6        120        8
...
9        184        16        ← resize
...

Size vs Capacity: The Critical Distinction

This confusion causes real bugs. Always be clear about which you are asking about.

Dynamic array state after adding [10, 20, 30, 40, 50]:

  Internal: [10, 20, 30, 40, 50, _, _, _]
             ↑                   ↑
          size = 5           capacity = 8

Accessing arr[5] → out of bounds from the user's perspective
  (size is 5, valid indices are 0-4)
  BUT the underlying array physically has something at index 5
  — it is just uninitialized/garbage data the user should not see

The dynamic array enforces:
  - User can only see indices 0 to size-1
  - Elements at size to capacity-1 are reserved but inaccessible
  - Capacity is an implementation detail, not a user-facing property

Java

import java.util.ArrayList;

public class SizeVsCapacity {

    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>();

        // Add 5 elements
        for (int i = 1; i <= 5; i++) arr.add(i * 10);

        // Size: what you see
        System.out.println("Size (elements you can access): " + arr.size());

        // Accessing by valid index — O(1)
        System.out.println("arr.get(0): " + arr.get(0));
        System.out.println("arr.get(4): " + arr.get(4));

        // This would throw — index 5 is beyond size
        try {
            arr.get(5);
        } catch (IndexOutOfBoundsException e) {
            System.out.println("arr.get(5): IndexOutOfBoundsException");
        }

        // You can pre-allocate capacity without affecting size
        ArrayList<Integer> preallocated = new ArrayList<>(1000);
        System.out.println("\nPre-allocated with capacity 1000");
        System.out.println("Size after construction: " + preallocated.size()); // 0
        // No elements added — size is still 0
    }
}

Output (Java):
Size (elements you can access): 5
arr.get(0): 10
arr.get(4): 50
arr.get(5): IndexOutOfBoundsException

Pre-allocated with capacity 1000
Size after construction: 0

When to Pre-Allocate Capacity

If you know the approximate number of elements in advance, pre-allocating capacity avoids unnecessary resizes — saving both time (no copies) and memory (no over-allocation from repeated doubling).

Without pre-allocation (n = 1000 elements):
  Resize at 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 → 10 resizes
  Total elements copied: ~1000 (geometric sum)
  Final capacity: 1024 or 2048 (24-1024 slots wasted)

With reserve(1000):
  0 resizes
  0 elements copied during growth
  Exactly 0 slots wasted (or minimal depending on exact n)

Java

import java.util.ArrayList;

public class PreAllocate {

    public static void main(String[] args) {
        int n = 1_000_000;

        // Without pre-allocation — multiple resizes occur
        long start1 = System.nanoTime();
        ArrayList<Integer> noPrealloc = new ArrayList<>();
        for (int i = 0; i < n; i++) noPrealloc.add(i);
        long time1 = System.nanoTime() - start1;

        // With pre-allocation — zero resize copies
        long start2 = System.nanoTime();
        ArrayList<Integer> prealloc = new ArrayList<>(n); // Reserve n slots
        for (int i = 0; i < n; i++) prealloc.add(i);
        long time2 = System.nanoTime() - start2;

        System.out.printf("Without pre-allocation: %.2f ms%n", time1 / 1_000_000.0);
        System.out.printf("With pre-allocation:    %.2f ms%n", time2 / 1_000_000.0);
        System.out.println("Both contain " + prealloc.size() + " elements");
    }
}

Output (approximate — varies by machine):
Without pre-allocation: ~45 ms
With pre-allocation:    ~20 ms
Both contain 1000000 elements

Shrinking: What Happens on Delete

Dynamic arrays typically do not shrink immediately on deletion. Shrinking too eagerly causes thrashing — if elements are alternately added and removed near the capacity boundary, the array would resize every operation.

Most implementations shrink only when size drops below 25% of capacity, and shrink to 50% (not down to size) to leave room for future growth.

Capacity = 16, Size = 16
Delete until size = 4  (size/capacity = 0.25)
  → Shrink: new capacity = 8  (not 4, to avoid immediate re-growth)

Python's list never shrinks automatically from pop() alone.
  → Manual: arr.clear() + refill, or create a new list

Java's ArrayList.trimToSize() trims capacity to match size exactly.
  → Use only when memory is tight and the list will not grow again.

C++ vector.shrink_to_fit() is a non-binding hint to the implementation.

Dynamic Array vs Static Array: When to Use Each

Criterion	Static Array	Dynamic Array
Size known at creation	Preferred — no overhead	Works, but wastes capacity
Size changes during runtime	Cannot use	Required
Memory is critical	More efficient — exact size	Less efficient — extra capacity
Need maximum performance	Slightly faster — no capacity checks	Slightly slower
Multi-dimensional grid	Common (2D int[][])	Verbose (ArrayList of ArrayList)
Passing to functions	Must track size separately	Self-describing (has .size())

In practice: use dynamic arrays (ArrayList, list, vector) for almost everything in interviews and application code. Use static arrays only when you have a specific reason — fixed-size buffers, performance-critical inner loops, or interoperating with C APIs.

Interview Questions

Q: What is the time complexity of appending to a dynamic array?

O(1) amortized. Each individual append is O(1) unless it triggers a resize, which is O(n). But resizes happen exponentially less frequently — the total work across n appends is O(n), giving O(1) average cost per operation. Single worst-case appends are O(n), but you cannot trigger them in consecutive operations.

Q: Why does doubling capacity give O(1) amortized while adding a fixed amount does not?

With doubling, the total elements copied across all resizes is a geometric series that sums to O(n). The cost of each resize is "prepaid" by the cheap appends that preceded it. With a fixed increment of k, you resize n/k times and each resize copies O(n) elements — total copy work is O(n²/k) = O(n²). Doubling is the critical insight.

Q: What is the difference between size and capacity in a dynamic array?

Size is the number of elements currently stored — what the user sees and can access. Capacity is how many elements the underlying static array can hold — an internal implementation detail. Size is always less than or equal to capacity. Accessing indices beyond size is an out-of-bounds error even if the slot physically exists in memory.

Q: How would you implement a dynamic array that supports O(1) prepend (insert at beginning) in addition to O(1) append?

Use a circular buffer or a deque (double-ended queue). A standard dynamic array prepend is O(n) because all elements shift right. A circular buffer tracks a head pointer — prepend moves the head backward (with wraparound), giving O(1). This is what Python's collections.deque and Java's ArrayDeque implement.

FAQs

Is Python's list always a dynamic array?

Yes. CPython's list is always a dynamic array backed by a C array of PyObject pointers. There is no Python built-in static array for general use. For true fixed-size typed arrays (like C's int[]), use the array module or NumPy ndarray. For algorithm problems, Python's list is the standard tool and its dynamic nature is a feature.

Does std::vector in C++ ever release memory automatically?

No — vector.push_back() and vector.pop_back() do not automatically shrink capacity. The capacity only grows. To release unused capacity, call vector.shrink_to_fit() (a non-binding hint) or swap with a trimmed copy: vector<int>(v).swap(v). This is a deliberate design choice — resizing on every deletion would cause thrashing.

When should I use ArrayList vs LinkedList in Java?

Use ArrayList for almost everything. It gives O(1) access by index, O(1) amortized append, and better cache performance than LinkedList for sequential traversal. Use LinkedList only when you frequently insert or delete from the middle of the list with an iterator (O(1) with a pointer to the node, compared to O(n) shifting in ArrayList). In practice, LinkedList is rarely the right choice — even mid-list operations are often faster with ArrayList on modern hardware due to cache effects.

What happens if I set new ArrayList<>(0) in Java?

Java creates an ArrayList with an empty internal array (or a shared empty array constant). The first add() call triggers a resize to the default capacity (10 in most JVM implementations). Using new ArrayList<>(0) saves memory when you are unsure whether the list will ever have elements, at the cost of a slightly earlier resize.

Quick Quiz

Question 1: A dynamic array has capacity 8 and size 8. You add one more element. What happens?

›A) The element is rejected — the array is full
›B) The array resizes to capacity 16, copies 8 elements, then adds the new one
›C) The array resizes to capacity 9, adds the element
›D) The element overwrites the last position

Answer: B) Resize to capacity 16, copy 8 elements, then add. Dynamic arrays double their capacity when full. The resize allocates a new array of size 16, copies all 8 existing elements, then adds the new element at index 8. Size becomes 9, capacity becomes 16.

Question 2: For n appends to a dynamic array starting empty, the total work across all resize operations is:

›A) O(n²) — each resize gets more expensive
›B) O(n log n) — log n resizes of increasing size
›C) O(n) — geometric series sums to approximately 2n
›D) O(1) — resizes are negligible

Answer: C) O(n) — geometric series. Resize copies: 1 + 2 + 4 + ... + n/2 = n - 1 ≈ O(n). This is the foundation of amortized O(1) per append.

Question 3: What does vector.reserve(1000) do in C++?

›A) Adds 1000 elements with default values
›B) Sets the size to 1000
›C) Allocates capacity for 1000 elements without changing size
›D) Limits the vector to a maximum of 1000 elements

Answer: C) Allocates capacity for 1000 elements without changing size. reserve() pre-allocates the underlying array so that future push_back() calls up to 1000 elements will not trigger any resizes. Size stays at its current value — no elements are added.

Question 4: You need to store exactly 500 integers that will never change after initialization. Which is more appropriate?

›A) Dynamic array (ArrayList, list, vector)
›B) Static array (int[], int[500])
›C) Either — there is no meaningful difference
›D) Linked list for cache efficiency

Answer: B) Static array. When the size is fixed and known at initialization, a static array is more efficient — exact memory allocation, no wasted capacity, no resize overhead, and no per-element wrapper objects (in Java's case, int[] vs Integer[] in ArrayList). Dynamic arrays shine when size is unknown or changes — not when it is fixed.

Summary

Dynamic arrays solve the fixed-size limitation of static arrays by automatically resizing when capacity is exhausted. They start with a small block, double when full, and copy all elements to the new block.

The key ideas to carry forward:

›Size is what you see — the number of stored elements
›Capacity is the internal limit — the size of the underlying static array
›Append is O(1) amortized — occasional O(n) resizes are absorbed across many O(1) appends
›Doubling strategy is critical — fixed increment gives O(n²) total copy work
›Pre-allocating with reserve() or new ArrayList<>(n) eliminates all resize copies when size is known in advance
›Python's list, Java's ArrayList, C++'s vector, and JS's Array are all dynamic arrays under different names
›Dynamic arrays do not shrink automatically on deletion — most require explicit trimming

In the next topic, you will explore Common Mistakes — the recurring array bugs that appear in interviews and production code, with clear explanations of why each one happens and how to avoid it.

←

Previous2D Arrays

NextPractice Problems

→