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

How Arrays Work in Memory

Why Understanding Memory Makes You a Better Developer

You can use arrays without understanding memory. Most beginners do. But when you understand what is physically happening — how elements are laid out, why index access is instant, why arrays are cache-friendly — you stop treating data structures as black boxes.

That understanding answers questions that otherwise feel arbitrary:

›Why is index access O(1) but searching is O(n)?
›Why do arrays outperform linked lists in practice even when Big-O is identical?
›Why does passing an array to a function sometimes modify the original?
›Why do some array operations cause surprising performance cliffs on large inputs?

This topic answers all of those. It connects what you write in code to what the computer actually does.

Contiguous Memory: The Core Property

When you create an array, the operating system allocates a single unbroken block of memory large enough to hold all the elements. The elements sit side by side — no gaps, no pointers between them.

Array: [10, 20, 30, 40, 50]

Memory (each cell = 4 bytes for int):
┌────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │
└────┴────┴────┴────┴────┘
 1000 1004 1008 1012 1016   ← memory addresses
  [0]  [1]  [2]  [3]  [4]  ← array indices

This contiguous layout is what makes arrays special. It is the property that enables O(1) access and excellent cache performance.

The Address Formula: Why O(1) Access Works

To retrieve arr[i], the computer does not scan from the beginning. It computes the memory address directly using one arithmetic operation:

address of arr[i] = base_address + (i × element_size)

›base_address — the memory address where the array starts
›i — the index you want
›element_size — how many bytes one element occupies

For the array above with integers (4 bytes each) starting at address 1000:

arr[0] → 1000 + (0 × 4) = 1000  → value 10
arr[1] → 1000 + (1 × 4) = 1004  → value 20
arr[2] → 1000 + (2 × 4) = 1008  → value 30
arr[3] → 1000 + (3 × 4) = 1012  → value 40
arr[4] → 1000 + (4 × 4) = 1016  → value 50

This is one multiplication and one addition — a fixed number of operations regardless of array size or which index you request. That is the definition of O(1).

No matter how large the array is — 10 elements or 10 million — retrieving arr[i] always takes the same time.

Element Size by Data Type

The element_size in the address formula depends on the data type. Different types occupy different amounts of memory:

Type	Java	C++	Python (CPython)	JavaScript
boolean / bool	1 byte	1 byte	28 bytes (object)	8 bytes (number)
byte / char	1 byte	1 byte	N/A	N/A
short	2 bytes	2 bytes	N/A	N/A
int / int32	4 bytes	4 bytes	28 bytes (object)	8 bytes (float64)
long / int64	8 bytes	8 bytes	28 bytes+ (object)	8 bytes (float64)
float	4 bytes	4 bytes	24 bytes (object)	8 bytes (float64)
double / float64	8 bytes	8 bytes	24 bytes (object)	8 bytes (float64)

Python and JavaScript have important differences: Python integers are objects with overhead, not raw 4-byte values. JavaScript stores all numbers as 64-bit floats regardless of whether the value is an integer.

This is why int[] in Java is more memory-efficient than List<Integer> — the former stores raw 4-byte values contiguously, while the latter stores 16-byte object references pointing to heap-allocated Integer objects.

Calculating Total Array Memory

The total memory an array occupies is:

total_memory = number_of_elements × element_size

For practical examples:

int[1000] in Java:
  1000 × 4 bytes = 4,000 bytes ≈ 4 KB

double[1000000] in Java:
  1,000,000 × 8 bytes = 8,000,000 bytes ≈ 8 MB

char[1000000] in Java:
  1,000,000 × 2 bytes = 2,000,000 bytes ≈ 2 MB

This calculation matters when working with large inputs. An algorithm that creates several arrays of size n can use multiples of this memory — and that affects both feasibility and performance.

Java

public class ArrayMemorySize {

    public static void main(String[] args) {
        // Demonstrate element sizes using Java's type system
        int[] intArray = new int[1000];
        long[] longArray = new long[1000];
        double[] doubleArray = new double[1000];

        // Java does not expose byte sizes directly, but these are guaranteed:
        // int    = 4 bytes → intArray    uses ~4,000 bytes
        // long   = 8 bytes → longArray   uses ~8,000 bytes
        // double = 8 bytes → doubleArray uses ~8,000 bytes

        System.out.println("int[]    size: " + intArray.length + " elements × 4 bytes = ~"
            + (intArray.length * 4) + " bytes");

        System.out.println("long[]   size: " + longArray.length + " elements × 8 bytes = ~"
            + (longArray.length * 8) + " bytes");

        System.out.println("double[] size: " + doubleArray.length + " elements × 8 bytes = ~"
            + (doubleArray.length * 8) + " bytes");
    }
}

Output (Java):
int[]    size: 1000 elements × 4 bytes = ~4000 bytes
long[]   size: 1000 elements × 8 bytes = ~8000 bytes
double[] size: 1000 elements × 8 bytes = ~8000 bytes

Output (C++):
sizeof(int):    4 bytes
sizeof(long):   8 bytes
sizeof(double): 8 bytes
sizeof(char):   1 bytes
sizeof(bool):   1 bytes
int[1000] total size: 4000 bytes
That is: 1000 elements × 4 bytes

Output (JavaScript):
Regular Array length: 10
Int32Array byteLength:    40 bytes ( 10 elements × 4 bytes)
Float64Array byteLength:  80 bytes ( 10 elements × 8 bytes)

Cache Locality: Why Arrays Are Faster Than Big-O Suggests

Modern CPUs do not fetch one byte from memory at a time. They fetch a chunk of memory called a cache line — typically 64 bytes — and load it into the CPU's L1 cache. Accessing data in the L1 cache is 100x to 1000x faster than accessing main memory.

Because array elements are contiguous in memory, when you access arr[0], the CPU loads arr[0] through approximately arr[15] (for 4-byte ints) into cache simultaneously. When you then access arr[1], it is already in cache. Same for arr[2], arr[3], and so on.

Cache line fetch when accessing arr[0]:
                       64 bytes fetched
┌────────────────────────────────────────────────────────────┐
│ arr[0] arr[1] arr[2] ... arr[15] │ (rest of memory ignored)│
└────────────────────────────────────────────────────────────┘
     ↑ requested         ↑ free rides into cache

Next access to arr[1]: already in cache → near-instant
Next access to arr[2]: already in cache → near-instant
...
Next access to arr[16]: cache miss → new fetch from memory

This property — called spatial locality — means that sequential array traversal is extremely cache-friendly. The actual performance of array traversal is often 5x to 10x faster than a linked list traversal with the same Big-O, simply because linked list nodes are scattered across memory and every node access risks a cache miss.

Stack vs Heap: Where Arrays Live

Where an array is stored in memory depends on how it is declared:

Stack-allocated arrays (C++ local arrays of fixed size) live in the function's stack frame. They are allocated and freed automatically when the function is called and returns. Stack memory is very fast but limited — typically 1MB to 8MB.

Heap-allocated arrays (Java new int[], C++ new int[], Python lists, JavaScript arrays) live on the heap. They persist until explicitly freed or garbage collected. Heap memory is larger but slower to allocate.

Stack (fast, limited, automatic):
  C++: int arr[100];   // 400 bytes on the stack
  → Freed when function returns

Heap (larger, explicit or GC-managed):
  Java:    int[] arr = new int[100];  // 400 bytes on heap
  C++:     int* arr = new int[100];  // 400 bytes on heap, manual free
  Python:  arr = [0] * 100           // heap, GC-managed
  JS:      const arr = new Array(100) // heap, GC-managed

In Java, Python, and JavaScript, arrays always live on the heap. You never think about stack vs heap because the runtime manages it. In C++, you choose explicitly, and stack overflow is a real risk for very large local arrays.

How Arrays Behave When Passed to Functions

This is one of the most important and frequently misunderstood behaviors.

When you pass an array to a function, you are passing a reference to the same block of memory — not a copy of all the elements. This means the function can modify the original array.

Java

public class ArrayPassByReference {

    // This function modifies the ORIGINAL array — no copy is made
    public static void doubleAll(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i] * 2;  // Modifies the original
        }
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};

        System.out.print("Before: ");
        for (int n : numbers) System.out.print(n + " ");
        System.out.println();

        doubleAll(numbers);  // Passes reference to the same array

        System.out.print("After:  ");
        for (int n : numbers) System.out.print(n + " ");
        System.out.println();

        // numbers was modified in place — not a copy
    }
}

Output:
Before: 1 2 3 4 5
After:  2 4 6 8 10

Dry Run: What Happens in Memory

Main creates:  numbers → [1, 2, 3, 4, 5]  at address 2000

doubleAll(numbers) is called:
  Parameter arr → points to address 2000 (same block)
  arr[0] = 1 × 2 → memory at 2000 = 2
  arr[1] = 2 × 2 → memory at 2004 = 4
  arr[2] = 3 × 2 → memory at 2008 = 6
  arr[3] = 4 × 2 → memory at 2012 = 8
  arr[4] = 5 × 2 → memory at 2016 = 10

doubleAll returns. No new array was created.
Main reads numbers → same address 2000 → [2, 4, 6, 8, 10]

Cost: O(n) time, O(1) extra space — no copy was made.

When You Need a Copy

If you want to modify an array inside a function without affecting the original, you must explicitly copy it:

Java

import java.util.Arrays;

public class ArrayCopy {

    // Creates a new array — original is not modified
    public static int[] doubleAllCopy(int[] arr) {
        int[] copy = Arrays.copyOf(arr, arr.length); // New block of memory

        for (int i = 0; i < copy.length; i++) {
            copy[i] = copy[i] * 2;
        }

        return copy;
    }

    public static void main(String[] args) {
        int[] original = {1, 2, 3, 4, 5};
        int[] doubled = doubleAllCopy(original);

        System.out.println("Original: " + Arrays.toString(original));
        System.out.println("Doubled:  " + Arrays.toString(doubled));
    }
}

Output:
Original: [1, 2, 3, 4, 5]
Doubled:  [2, 4, 6, 8, 10]

Making a copy costs O(n) extra time and O(n) extra space. This is not free — for large arrays, it is a meaningful cost. Only copy when you genuinely need to preserve the original.

Why Fixed Size Is a Fundamental Constraint

Because arrays are contiguous blocks of memory, their size must be fixed when they are created. The block is reserved all at once. You cannot extend it later — the memory after the array might already be in use by something else.

Memory layout when array of size 5 is created:

Address: 1000  1004  1008  1012  1016  1020  1024
         [arr0][arr1][arr2][arr3][arr4][????][????]
                                         ↑
                                   Other data lives here
                                   Cannot expand arr into it

If you need a 6th element, you cannot just append to the existing block. You must:

›Allocate a new, larger block elsewhere in memory
›Copy all existing elements to the new block
›Free the old block (or let GC handle it)
›Add the new element

This is exactly what dynamic arrays (ArrayList, Python list, C++ vector) do automatically — but it is O(n) work, not O(1). Understanding this explains why dynamic array growth is more expensive than it looks, and why pre-allocating the right size matters for performance-critical code.

Interview Questions

Q: Why is array index access O(1)?

Because the memory address of any element is computed in a single arithmetic operation: base_address + (index × element_size). No searching or scanning is involved. This works only because array elements occupy contiguous memory with uniform element sizes. The CPU computes the exact address and fetches from it directly.

Q: Why are arrays more cache-friendly than linked lists?

Arrays store elements in a single contiguous block of memory. When the CPU fetches one element, it loads the surrounding elements into cache simultaneously (a 64-byte cache line holds 16 integers). Subsequent accesses to nearby elements hit the cache — orders of magnitude faster than main memory. Linked list nodes are scattered across memory, so each node access risks a cache miss and a full main-memory fetch.

Q: What happens to the original array when you pass it to a function?

In Java, Python, C++, and JavaScript, passing an array to a function passes a reference to the same memory block, not a copy of the elements. The function operates on the original data. Modifying the array inside the function modifies the original. To avoid this, explicitly copy the array before modifying it.

Q: Why can you not just append an element to a static array?

Because the contiguous memory block was allocated for a fixed size. The memory immediately after the last element might be used by something else. To grow the array, you must allocate a new larger block, copy all elements to it, and discard the old block. This is what dynamic arrays do automatically — but it is not free.

FAQs

Does Python's list use contiguous memory like a C array?

Python lists store a contiguous array of pointers (references) to Python objects, not the objects themselves. The pointer array is contiguous, giving O(1) index access. But the actual integer or string objects those pointers point to are scattered across the heap. This is why Python lists have higher memory overhead than Java int[] — each integer element is a full Python object, not a raw 4-byte value.

What is a TypedArray in JavaScript and why does it matter?

A standard JavaScript array is a dynamic collection of JavaScript values, each an object with overhead. A TypedArray (Int32Array, Float64Array, etc.) stores raw numeric values in a contiguous memory buffer — similar to a C array. TypedArrays use less memory and provide better performance for numeric computation. They are used in WebGL, audio processing, and any performance-sensitive numeric code.

How does the C++ sizeof operator help with array memory calculations?

sizeof(arr) on a C-style array gives the total bytes occupied by the entire array. sizeof(arr) / sizeof(arr[0]) gives the number of elements — a common idiom for computing array length in C++ without tracking it manually. Note: this only works for actual arrays, not for pointers. When a C-style array is passed to a function, it decays to a pointer and sizeof returns the pointer size (4 or 8 bytes), not the array size.

Why does uninitialized array access cause undefined behavior in C++ but not in Java?

Java guarantees that all array elements are zero-initialized when the array is created. This is part of the Java Language Specification. C++ does not make this guarantee for local (stack) arrays — their values are whatever bits happened to be in that memory from previous use. This saves a small amount of time at allocation but risks hard-to-debug bugs when code reads from uninitialized positions.

Quick Quiz

Question 1: An int array of size 1000 starts at memory address 5000. Where is arr[7] stored?

›A) 5007
›B) 5028
›C) 5014
›D) 5035

Answer: B) 5028. Using the formula: 5000 + (7 × 4) = 5000 + 28 = 5028. Each integer occupies 4 bytes, so the 7th element (0-indexed) is 28 bytes after the start.

Question 2: Why is sequential traversal of an array faster than random traversal in practice?

›A) Random access is O(n) while sequential is O(1)
›B) Sequential access benefits from CPU cache — nearby elements are loaded together
›C) Sequential traversal skips some elements
›D) Arrays have a hardware fast path for sequential access only

Answer: B) Sequential access benefits from CPU cache. When the CPU fetches one element, it loads surrounding elements into cache. Sequential traversal accesses these cached elements, avoiding repeated main-memory fetches. Random traversal jumps around in memory, causing more cache misses.

Question 3: You pass an int[] array to a function in Java and the function modifies arr[0]. After the function returns, what is the value of the original array's first element?

›A) Unchanged — Java passes arrays by value
›B) Changed — Java passes arrays by reference (the function modified the same memory)
›C) Depends on whether the array is declared final
›D) Undefined behavior

Answer: B) Changed. Java passes a reference to the array, not a copy of its elements. The function operates on the same memory block. Modifications inside the function are visible in the caller.

Question 4: What is the main reason a static array cannot simply grow when more elements are needed?

›A) Arrays have a maximum size defined by the language
›B) The contiguous memory block after the array may be occupied by other data
›C) Growing would invalidate all existing indices
›D) The OS does not allow arrays larger than physical RAM

Answer: B) The contiguous memory block after the array may be occupied by other data. The array was allocated as a fixed block. There is no guarantee the adjacent memory is free. To grow, a new larger block must be allocated elsewhere, all elements copied to it, and the old block freed.

Summary

Arrays store elements in a single contiguous block of memory. This physical layout is what makes them fast — index access is O(1) because any element's address is computable in one arithmetic step, and sequential traversal is cache-friendly because nearby elements load into cache together.

The key ideas to carry forward:

›address of arr[i] = base_address + (i × element_size) — this is why O(1) access works
›Contiguous memory enables cache efficiency — arrays beat linked lists in practice even at identical Big-O
›Passing an array to a function passes a reference — the function can modify the original
›Copying an array is O(n) time and O(n) space — only do it when necessary
›Fixed size is a fundamental consequence of contiguous allocation — the block cannot expand if adjacent memory is taken
›Java zero-initializes arrays; C++ local arrays are uninitialized and contain garbage

In the next topic, you will explore Array Traversal — the core technique for processing every element in an array systematically, with the patterns and edge cases that appear most often in interviews.