Arrays — Complete DSA Array Theory

Learning Progress. Work top to bottom: theory → types → the interactive visualizer → patterns → cheat sheet → interview prep. Pin the visualizer (button top-right of the panel) to keep it on screen while you read.

Theory & Fundamentals

What is an Array?

An Array is a collection of elements stored in contiguous memory, each identified by an index. Because addresses are computed arithmetically, any element is reachable in O(1).

That random access is the array's superpower — and its cost: inserting or deleting in the middle forces every later element to shift, which is O(n).

Address arithmetic

// contiguous layout
Index: 0 1 2 3 4
Value: 10 20 30 40 50

// O(1) access
addr(a[i]) = base + i * sizeof(elem)

Why Arrays matter. They're the most fundamental data structure: the backing store for strings, stacks, heaps, hash tables, dynamic arrays (vector), and matrices. Nearly every interview warm-up is an array problem.

Types of Array

▭

Static Array

Fixed size known at compile time. No resizing.

Use: fixed buffers, C-style int a[n].

↔️

Dynamic Array

Grows/shrinks at runtime; doubles capacity when full (amortized O(1) push).

Use: std::vector, the default choice.

▦

Multi-dimensional

Arrays of arrays — matrices, grids, tensors.

Use: DP tables, images, graphs as matrices.

🔤

Character Array

Contiguous chars; the basis for strings.

Use: strings, parsing, buffers.

🔢

Prefix / Difference

Derived arrays for O(1) range sums / range updates.

Use: range queries, subarray sums.

🧮

Sorted Array

Kept in order to enable binary search in O(log n).

Use: search, two pointers, merge.

Terminology

Index

Zero-based position of an element, a[0] is the first.

Contiguous memory

Elements stored back-to-back, enabling O(1) address math.

Subarray

A contiguous slice a[i..j].

Subsequence

Elements in order but not necessarily contiguous.

Capacity vs size

Dynamic arrays reserve capacity ≥ size to amortize growth.

Shift

Moving elements to make room (insert) or close a gap (delete).

Complexity Summary

Access a[i]

O(1)

Direct address arithmetic.

Search (unsorted)

O(n)

Linear scan.

Search (sorted)

O(log n)

Binary search.

Insert / Delete

O(n)

Middle shifts elements; end is O(1) amortized.

Append (dynamic)

O(1)*

Amortized; O(n) on a resize.

Space

O(n)

n contiguous elements.

Advantages & Disadvantages

Advantages

O(1) random access by index.
Excellent cache locality (contiguous memory).
Minimal per-element overhead.
Backbone of strings, stacks, heaps, matrices, and DP tables.

Disadvantages

Insert/delete in the middle is O(n) (shifting).
Static arrays have a fixed size.
Dynamic-array resizing occasionally copies everything.
Wasted capacity when over-reserved.

C++ STL Implementation

array_basics.cpp · std::vector essentials

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {10,20,30,40,50};
    cout << a[2] << "\n";        // 30 — O(1) access
    a.push_back(60);           // append — amortized O(1)
    a.insert(a.begin()+1, 99); // insert at index 1 — O(n)
    a.erase(a.begin()+3);    // delete index 3 — O(n)
    sort(a.begin(), a.end());   // O(n log n)
    bool f = binary_search(a.begin(),a.end(),30); // O(log n)
    return 0;
}

patterns.cpp · Binary search, two pointers, window

// Binary search — sorted array, O(log n)
int bsearch(vector<int>& a, int t){
    int lo=0, hi=a.size()-1;
    while(lo<=hi){ int mid=lo+(hi-lo)/2;
        if(a[mid]==t) return mid;
        if(a[mid]<t) lo=mid+1; else hi=mid-1; }
    return -1;
}

// Two pointers — pair sum in sorted array, O(n)
bool pairSum(vector<int>& a, int t){
    int i=0, j=a.size()-1;
    while(i<j){ int s=a[i]+a[j];
        if(s==t) return true;
        s<t ? i++ : j--; }
    return false;
}

// Sliding window — max sum of k elements, O(n)
int maxSumK(vector<int>& a, int k){
    int sum=0; for(int i=0;i<k;i++) sum+=a[i];
    int best=sum;
    for(int i=k;i<a.size();i++){ sum+=a[i]-a[i-k]; best=max(best,sum); }
    return best;
}

Interactive Array Visualization

Element Current / mid lo pointer hi pointer Search range Match

Idle

Current operation details

Operation

—

Pointer(s)

—

Result

—

Steps

taken

Comparisons

checks

Shifts

moves

Length

elements

Step — of —

Select a scenario above, or use the manual controls, then press Play.

Manual controls — build your own array

Array: Value / index:

✓ Done

Speed

Step-by-step operation log

Step	lo/i	hi/mid	Action	Array State
Run a scenario to populate the log.

Key Patterns

Two pointers. On a sorted array, move a pointer from each end inward to solve pair-sum, container-with-most-water, and dedup in O(n) — no extra space. Same-direction pointers handle in-place filtering and partitioning.

Sliding window & prefix sums. A moving window gives O(n) answers for "max/min subarray of size k" and variable-size condition problems. A prefix-sum array answers any range sum in O(1) after O(n) preprocessing.

Cheat Sheet

Operation	Time	Space	Notes
Access a[i]	O(1)	O(1)	Address arithmetic
Linear search	O(n)	O(1)	Unsorted
Binary search	O(log n)	O(1)	Sorted only
Insert / delete (mid)	O(n)	O(1)	Shifting
Two pointers	O(n)	O(1)	Sorted; pair/partition
Sliding window	O(n)	O(1)	Subarray problems
Prefix sum range query	O(1)	O(n)	After O(n) build

Learning Roadmap

Array Basics

Indexing, traversal, contiguous memory, static vs dynamic (vector), insert/delete costs.

~2 hours

Searching & Sorting

Linear vs binary search, sorting basics, when a sorted array unlocks O(log n).

~3 hours

Two Pointers

Pair sum, dedup, partition, container with most water, three-sum.

~4 hours

Sliding Window & Prefix Sums

Fixed/variable windows, subarray sums, Kadane's algorithm, range queries.

~4 hours

Advanced

Matrix traversal, in-place tricks, difference arrays, sorting-based greedy.

~4 hours

Interview Preparation

Two Sum

Sorted array → two pointers O(n); unsorted → hash map O(n). Classic warm-up.

Two Pointers

Maximum Subarray (Kadane's)

Track running sum; reset to 0 when it goes negative, keep the best. O(n).

DP / Window

Product of Array Except Self

Prefix products left-to-right, then suffix products right-to-left. O(n), no division.

Prefix

Rotate Array

Reverse whole array, then reverse the two halves. In-place O(n)/O(1).

Reversal

Practice Problems

EasyTwo SumHash / Pointers

EasyBest Time to Buy & Sell StockWindow

EasyMove ZeroesTwo Pointers

MediumMaximum SubarrayKadane's

MediumProduct of Array Except SelfPrefix

Medium3SumTwo Pointers

MediumContainer With Most WaterTwo Pointers

HardTrapping Rain WaterTwo Pointers

Key Takeaways

⚡O(1) access, O(n) middle edits: contiguous memory buys instant indexing but makes insert/delete shift everything after.

🔍Sort unlocks log n: a sorted array enables binary search and two-pointer tricks — often worth the O(n log n) upfront.

↔️Two pointers & windows: the highest-yield array patterns, turning O(n²) brute force into O(n) with O(1) space.

🔢Prefix sums: precompute once, answer any range sum in O(1) — the base for many subarray problems.