Arrays
An array is a linear data structure containing elements stored in contiguous memory blocks. Accessing elements by index runs in constant time, but insertion and deletion require shifting elements.
Why It Exists
Computers organize memory as a sequence of address slots. Arrays map directly to this hardware structure, enabling low-level CPU cache efficiency.
Intuition for Beginners
“Think of a row of lockers numbered 0 to N-1. If you know the locker number, you can open it instantly (O(1) access). If you want to insert a new locker in the middle, you must physically push all subsequent lockers down by one slot.”
Visual Explanation
Array Memory Contiguity: +-----+-----+-----+-----+-----+ | 10 | 8 | 25 | 14 | 90 | +-----+-----+-----+-----+-----+ Index: 0 1 2 3 4 Addr: 0x01 0x05 0x09 0x0D 0x11 (4-byte spacing)
Sliding Window Expansion/Shrink
Set left = 0, right = 0. Target subarray sum >= 7. Current sum = 2.
Complexity Analysis
| Operation | Time Complexity | Notes |
|---|---|---|
| Access | O(1) | Direct lookup by index offset |
| Search | O(N) | Unsorted scan (Linear search) |
| Insertion | O(N) | Shifting elements right to free up a slot |
| Deletion | O(N) | Shifting elements left to close the gap |
Production & Real World Applications
- •Image Pixels: 2D/3D grids mapping color buffers to rendering displays.
- •Dynamic Ring Buffers: Low-latency message packets queue processing.
Algorithmic Patterns
Using left/right pointers to find target values in sorted collections.
Shifting left and right bounds to compute contiguous subsegment sums.
Pre-calculating cumulative sums to answer range query requests in O(1).
Defending the Design (Interview Q&A)
Common Traps & Mistakes
- ⚠️Out-of-bounds index errors (accessing N instead of N-1).
- ⚠️Duplicating arrays in memory during subset copies (causing high space complexity).
Recommended Articles & Visual Guides
Mastering Sliding Windows
Optimize sub-array searches and substring boundaries from O(N^2) to O(N) complexity with moving boundary pointers.
Mastering Two Pointers
Learn how to optimize linear search intervals and matching bounds from O(N^2) to O(N) using inward or different speed pointers.