Arrays

A collection of items stored at contiguous memory locations. Elements can be accessed randomly using indices.

What is it?

An array is the simplest and most widely used data structure. Think of a playlist in Spotify. Each song is an element in the array. Because arrays store elements in a contiguous block of memory, Spotify can instantly jump to the 5th or 100th song in your playlist without checking the ones before it. This is called random access and has a time complexity of O(1), making it incredibly fast. However, this structure has tradeoffs. If you want to insert a new song in the middle of your playlist, the application has to shift all the subsequent songs down to make room, which can be an expensive operation (O(n)). This is why adding to the end of a playlist is always instantaneous.

Time Complexity

AccessO(1)

SearchO(n)

InsertionO(n)

DeletionO(n)

Implementation Example

// Declaration
const arr = [1, 2, 3, 4, 5];

// Access
console.log(arr[2]); // Output: 3

// Insertion (at the end)
arr.push(6);

// Deletion (from the end)
arr.pop();

// Iteration
arr.forEach(item => console.log(item));

Arrays

Arrays Deep Dive

Arrays shine when you need predictable memory layout and cache-friendly iteration. They power everything from GPU buffers to recommendation feeds.

?But why does this matter?

Because arrays are contiguous, CPUs can prefetch data and vectorize operations, giving arrays a practical advantage beyond the theoretical O(1) access.

Visual Flow

How it actually moves

Random access

O(1)

Direct pointer arithmetic retrieves any element instantly.

Insert/delete middle

O(n)

Items to the right must shift, which can thrash caches.

Append (dynamic array)

Amortized O(1)

Occasional resize copies data but is rare.

Sliding window average

Keep two pointers (start/end) and a running sum of the current window.

Expand the end pointer while adding the new value to the sum.

Once the window reaches size k, record sum / k, then subtract arr[start] and move start forward.

Repeat until the end pointer reaches the array tail.

Because arrays are contiguous, advancing pointers simply increments indices—no pointer chasing required.

Watch the best explainer

What is an Array?

The Coding Train · Daniel Shiffman

Daniel Shiffman’s beloved whiteboard-and-code intro to arrays — millions of views for a reason.

Think of a theatre seating chart

Every seat has a fixed position. Ushers can jump directly to seat 42 without counting from the beginning, but inserting a VIP row in the middle requires shifting everyone down.

Real-world analogy

Ticketing systems keep each seat in order so scanning and printing labels is instant.

Takeaway

Arrays feel great for predictable lookups and iteration, but rearranging the middle is expensive.

Practical applications

• Rendering ordered UI like Instagram feeds or spreadsheet rows.
• Analytics platforms scanning billions of metrics in memory.
• Signal processing buffers that require predictable offsets.

Technical insights

• CPU caches load data in cache lines; contiguous arrays minimize cache misses.
• Fixed-size arrays map well to SIMD/vector instructions, enabling fast math operations.
• Dynamic arrays (vectors/slices) trade occasional O(n) resizes for amortized O(1) append.

When to reach for it

• Tight numeric loops or data science workloads that benefit from vectorization.
• Lookups by stable index (seat numbers, leaderboard ranks).
• Any situation where predictable traversal order matters.

Operations Breakdown

Random access

O(1)

Direct pointer arithmetic retrieves any element instantly.

Insert/delete middle

O(n)

Items to the right must shift, which can thrash caches.

Append (dynamic array)

Amortized O(1)

Occasional resize copies data but is rare.

Best practices

• Reserve capacity when the approximate size is known to avoid repeated growth.
• Favor immutable operations (returns new array) only when working with functional pipelines; otherwise mutate in place to reuse memory.
• Chunk large arrays for multi-threaded processing to avoid contention.

Common pitfalls

• Frequent inserts at the front cause constant copying; consider deque or linked list instead.
• Growing beyond CPU cache lines degrades performance even if Big-O stays the same.
• Copying arrays across worker threads can dominate the runtime when payloads are large.

Every kind of Arrays

Interviewers rarely say which flavor they mean — they expect you to recognize it from the problem. Each variant below comes with the algorithms it unlocks.

Type 1 of 5

Static & Dynamic Arrays

→ full page

The contiguous block itself. Static arrays fix capacity at creation; dynamic arrays (JS arrays, Python lists, Go slices) resize by doubling.

What to know

Doubling growth gives amortized O(1) append — each element is copied O(1) times on average.
Indexing is pointer arithmetic: base + index × element size.
Contiguity is why arrays beat linked structures in practice: cache lines and prefetching.

Algorithms to reach for

Kadane’s algorithm

O(n)

Maximum subarray sum in one pass

Dutch national flag

O(n)

Three-way partition (sort colors) in place

In-place reversal / rotation

O(n)

Rotate array by k using triple reverse

In the wild: Every language’s default list type; the backing store of hash tables, heaps, and stacks.

Practice problems — hints, approach & solution on their own pages

Maximum SubarrayMedium Sort ColorsMedium Rotate ArrayMedium

Type 2 of 5

Sorted Array

→ full page

Order unlocks logarithmic search and linear merging — most classic array algorithms assume or create sortedness.

What to know

Binary search needs random access — it is an array algorithm, not a list algorithm.
Two pointers from both ends solve pair-sum problems without extra memory.
Merging two sorted arrays is the heart of merge sort and external sorting.

Algorithms to reach for

Binary search

O(log n)

Find element or insertion point

Two pointers (opposite ends)

O(n)

Two-sum sorted, container with most water

Merge of sorted arrays

O(n + m)

Combine sorted runs stably

In the wild: Database indexes, sorted ID lists in search engines, time-series query windows.

Practice problems — hints, approach & solution on their own pages

Two Sum II — Input Array Is SortedMedium Container With Most WaterMedium Merge Sorted ArrayEasy

Type 3 of 5

Prefix-Sum & Difference Arrays

→ full page

Preprocess once, answer range questions forever. Prefix sums answer range-sum queries in O(1); difference arrays apply range updates in O(1).

What to know

prefix[i] = prefix[i−1] + arr[i]; sum(l..r) = prefix[r] − prefix[l−1].
Difference array: add v at l, subtract v after r, then prefix-sum to materialize.
2D prefix sums answer rectangle sums with four lookups (inclusion-exclusion).
Prefix sum + hash map solves "subarray sum equals K" in one pass.

Algorithms to reach for

Range-sum query

O(1) query

Instant subarray totals after O(n) prep

Subarray sum = K (prefix + hashmap)

O(n)

Count subarrays hitting a target

Range update via difference array

O(1) per update

Bulk +v on many ranges, one materialize

In the wild: Analytics dashboards (sum over date range), flight booking seat-count changes, image integral tables.

Practice problems — hints, approach & solution on their own pages

Subarray Sum Equals KMedium Range Sum Query — ImmutableEasy Product of Array Except SelfMedium

Type 4 of 5

2D Array / Matrix

→ full page

Rows × columns of contiguous data. Traversal patterns (spiral, diagonal, transpose) and grid-graph algorithms live here.

What to know

Row-major traversal is dramatically faster than column-major due to cache lines.
In-place rotation = transpose + reverse each row.
Many DP problems (edit distance, unique paths) are matrices where each cell depends on neighbors.

Algorithms to reach for

Spiral / diagonal traversal

O(rows · cols)

Layer-by-layer boundary walking

Matrix rotation in place

O(n²)

Rotate image 90° without extra memory

Staircase search

O(rows + cols)

Search a row-and-column sorted matrix from a corner

In the wild: Image pixels, spreadsheets, game boards, ML tensors before they grow more dimensions.

Practice problems — hints, approach & solution on their own pages

Rotate ImageMedium Spiral MatrixMedium Search a 2D Matrix IIMedium

Type 5 of 5

Circular Array (Ring Buffer)

→ full page

Wrap the end back to the start with modulo indexing. Fixed memory, no shifting — the standard bounded queue.

What to know

head and tail chase each other; (i + 1) % n wraps the index.
Full vs empty is disambiguated by a count or by sacrificing one slot.
Powers-of-two capacity turns modulo into a bit-mask AND.

Algorithms to reach for

Circular queue ops

O(1)

O(1) enqueue/dequeue in fixed memory

Circular Kadane

O(n)

Max subarray sum when wrapping is allowed

Next greater element II

O(n)

Monotonic stack over a doubled index range

In the wild: Audio/video buffers, keyboard input queues, log ring buffers (dmesg), producer-consumer channels.

Practice problems — hints, approach & solution on their own pages

Design Circular QueueMedium Maximum Sum Circular SubarrayMedium Next Greater Element IIMedium

Pseudo Code • Sliding window average

Flow Diagram

Keep two pointers (start/end) and a running sum of the current window.
Expand the end pointer while adding the new value to the sum.
Once the window reaches size k, record sum / k, then subtract arr[start] and move start forward.
Repeat until the end pointer reaches the array tail.

Because arrays are contiguous, advancing pointers simply increments indices—no pointer chasing required.

Hands-on code

Compare how the same idea looks in JavaScript, Python, and Go.

function movingAverage(readings, windowSize) {
  const result = [];
  let sum = 0;
  let start = 0;

  for (let end = 0; end < readings.length; end += 1) {
    sum += readings[end];

    if (end - start + 1 === windowSize) {
      result.push(sum / windowSize);
      sum -= readings[start];
      start += 1;
    }
  }
  return result;
}