ReviseAlgo Logo

Arrays

Array Fundamentals

Memory layout, indexing, traversal, in-place modification, rotation, two-pointer, and 2D arrays — the complete foundation.

Last Updated: August 2, 2026 • 25 min read

1. Introduction

What is an Array?

An array is a fundamental, linear data structure that stores elements in a contiguous block of memory. Every element in an array occupies consecutive memory addresses and is identified by its numerical index, starting at 0.

Why is it Important?

Because elements are stored contiguously, arrays provide O(1) random access time to any element using a simple arithmetic formula. It is the backbone data structure upon which strings, matrices, hash tables, heaps, and dynamic lists are built.

Where is it Used?

  • Buffer Storage: Audio/video streaming buffers storing consecutive samples in memory.
  • Matrix Representation: 3D game engines storing pixel/vertex matrices in contiguous memory blocks.
  • CPU Cache Optimization: Hardware pre-fetchers leverage array memory locality to load sequential data into CPU cache lines.

    • 2. Mental Model

    Imagine a row of numbered mailboxes on a wall, starting at Mailbox #0.

    If you know the base address of the first mailbox (1000) and the size of each box (4 bytes), you can instantly calculate the exact location of Mailbox #3:

    Address = 1000 + 3 × 4 = 1012

    No scanning or walking down the hallway is required! You jump directly to Mailbox #3 in constant time. However, if you want to insert a new mailbox between #1 and #2, you have to shift all subsequent mailboxes down the wall.

    3. Concept: Core Array Mechanics

    Memory Layout & Addressing

    Given an array arr with base memory address B and element size S bytes:
    address(arr[i]) = B + i × S

    Static vs Dynamic Arrays

  • Static Arrays: Fixed capacity set at creation time (e.g., C/C++ native int arr[10]). Cannot shrink or grow.
  • Dynamic Arrays: Automatically double their capacity when full (e.g., ArrayList in Java, std::vector in C++, list in Python).
    • - Amortized O(1) Append: Resizing happens at capacities 1 \to 2 \to 4 \to 8 \to 16 ..., making N appends cost O(N) total, averaging O(1) per append.

    4. Visuals

    Memory Allocation & Indexing Diagram

    Operation Summary Table

    OperationTime ComplexityExplanation / Condition
    Access by IndexO(1)Direct formula computation
    Search (Unsorted)O(N)Must inspect elements sequentially
    Search (Sorted)O(log N)Binary search
    Insert at EndO(1)^Amortized for dynamic arrays
    Insert at MiddleO(N)Shift right by one position
    Delete from MiddleO(N)Shift left by one position

    5. Real-World Examples

  • Operating System Memory Pages: The kernel treats physical memory as an array of fixed-size frames (4 KB each) for direct indexing.
  • Image Pixel Buffer: An uncompressed 1920 × 1080 image is stored as a 1D flattened array of RGB integers (1920 × 1080 × 3 values). O(1) pixel lookup is (row × width + col) × 3.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers assess whether you understand in-place array manipulation without allocating extra arrays (O(1) auxiliary space). Common challenges include in-place reversal, rotation, or partitioning (e.g., Dutch National Flag).

    Common Mistakes

    Warning: 1. Off-By-One Errors: Reading arr[arr.length] instead of arr[arr.length - 1].
    > 2. Modifying Array Size Inside a Loop: Removing elements during forward iteration skips adjacent elements.
    > 3. Assuming Array Slices are Free: Slicing an array in Python (arr[a:b]) creates a copy in O(K) time and space.

    7. Summary

  • Arrays store elements in contiguous memory locations, providing O(1) random access.
  • Insertion and deletion in the middle take O(N) time due to element shifting.
  • Dynamic arrays handle growth automatically with an amortized O(1) append time complexity.
  • In-place algorithms (like write-pointers and array rotation) eliminate unnecessary space complexity (O(1) extra space).

    • 8. Quiz

    Question 1: Why does accessing arr[500] take the exact same time as accessing arr[0]? Answer: Because array memory is contiguous! The memory address is calculated instantly using the formula base\_address + index × element\_size, which requires only one multiplication and one addition.
    Question 2: What is the amortized time complexity of appending an element to a dynamic array (like std::vector or ArrayList)? Answer: O(1) amortized. While resizing doubles the capacity in O(N) time, it happens exponentially rarely (1, 2, 4, 8, 16 ...), so N appends cost O(N) total operations.
    Question 3: Why does deleting an element at index 0 take O(N) time in a standard array? Answer: Removing the element at index 0 leaves an empty slot. To keep elements contiguous, all remaining N-1 elements must be shifted left by one position.
    Question 4: How is a 2D matrix of size R x C flattened into a 1D array in memory? Answer: Using row-major ordering. Row 0 is stored first, followed by Row 1, Row 2, etc. The 1D index for element at matrix[r][c] is given by r C + c.
    Question 5: What is the optimal space complexity for rotating an array by K steps? Answer: O(1) extra space using the Three-Reverse Trick: (1) reverse the entire array, (2) reverse the first K elements, (3) reverse the remaining N-K elements.