Arrays are one of the most fundamental data structures in computer science. They are the building block and form the foundation for many other data structures and algorithms.

Arrays appear in basic loops and sorting, in standard library list types, and in advanced interview techniques like two pointers, sliding window, and dynamic programming.

In this chapter, I'll break down:

An array is a data structure used to store a collection of elements of the same type, arranged in a contiguous block of memory.

Integer array:

Boolean array:

String array:

To store 100 numbers, creating separate variables like num1, num2, ..., num100 would be impossible to manage.

Instead, you store them in one structure:

Now you can access any value using an index: arr[0], arr[1], arr[2], ...

Most programming languages use zero-based indexing, so the first element is at index 0.

Accessing an element in an array is fast because elements are stored next to each other in memory.

We can compute the address of any index using simple math:

address of arr[i] = base address + (i × size of each element)

This allows you to retrieve any element in constant time, O(1), no matter how large the array is.

But arrays aren't perfect.

In languages like C++ and Java, arrays have a fixed size. Once you allocate memory for 100 elements, you can't expand it.

If you need more space, you'll have to create a new, larger array and copy the data over, which takes O(n) time.

Most programming languages provide a dynamic array type that resizes automatically as elements are added:

Internally, dynamic arrays allocate more memory than needed. For example, if you insert 5 elements, the underlying buffer might have space for 8 or 10.

This way, the array doesn't need to resize for every insertion.

When the array runs out of space, it typically doubles its capacity, allocating a bigger chunk of memory, and copying all elements from the old array to the new one.

This operation is expensive, it takes O(n) time.

But because it doesn't happen often, the average time for inserting at the end remains O(1).

The most common array operations are accessing by index, traversal, insertion, deletion, and search. Each has a well-known time complexity:

1. Accessing by Index

Since the elements are stored in contiguous memory layout, the address of any element can be calculated directly using a simple formula.

As a result, accessing an element by index always takes constant time, whether the array has 10 elements or 10 million.

2. Traversal

Traversal means going through the array, one element at a time, commonly used for printing values, calculating a sum, or searching for a specific item.

Since each element is visited exactly once, this takes O(n) time, where n is the number of elements in the array.

3. Insertion

The performance of insertion depends entirely on where the new element is placed.

If you insert at the end, it's fast. Place the element at the next index when there is free capacity.

This takes amortized O(1) time in dynamic arrays. Most appends are O(1), but the occasional resize copies every element, which costs O(n). Averaged over many insertions, the cost works out to O(1) per insertion.

If you insert at the beginning or the middle, it gets slower since all elements after the insertion point must be shifted one position to the right to make space. This shifting requires O(n) time in the worst case.

Even though languages like Python (list) or Java (ArrayList) handle the shifting internally, the time complexity does not change, it still costs O(n) for inserting anywhere except the end.

4. Deletion

Removing an element is similar to insertion, it depends on the position.

If you drop the last element, no shifting is required. It takes O(1) time.

But if you delete from start or middle, you'll need to shift all following elements left to fill the gap. That takes O(n) time.

So deleting the first element in a 1,000-element array means 999 elements need to move one step left.

5. Search

The performance of searching depends heavily on whether the array is sorted.

If the array is unsorted, you'll have to scan through each element one by one which takes O(n) time.

But if the array is sorted, you can use Binary Search, which divides the search space in half with each step, reducing the time to O(log n).

Arrays show up in most coding interview questions, not as raw "loop and print" exercises but through a small set of well-known problem-solving patterns.

Here are the most common array patterns you should know.

1. Two Pointer Technique

The two-pointer pattern works on sorted arrays (or any array where the data has some ordered structure) by keeping two indices that move toward each other based on a comparison. One pointer starts at the left end, the other at the right end. At each step we compare the values at the two pointers and decide which pointer to advance.

The visualization below shows the two pointers narrowing the search range step by step:

Here left advances twice while right stays, and then right retreats. Each move shrinks the candidate range without revisiting positions, which is what gives the pattern its O(n) behavior even though the array is being scanned from both directions.

A classic application is Two Sum on a sorted array: find two indices whose values sum to a target.

For nums = [1, 3, 5, 7, 9, 11] and target = 12, the algorithm checks 1 + 11 = 12 immediately and returns [0, 5]. For target = 16, the trace looks like this:

The brute-force version of this problem checks every pair in O(n²) time. Two pointers brings that down to O(n) time and O(1) extra space.

Common use cases for the two-pointer pattern:

2. Sliding Window

Sliding window applies to problems about a contiguous subarray or substring. Instead of recomputing a property (sum, count, frequency, max, etc.) for every possible subarray, you maintain a window that moves across the array, updating the property incrementally as elements enter and leave.

The visualization below shows a fixed-size window of width 3 sliding across the array:

Each time the window slides one position to the right, exactly one element leaves the window and one new element enters. That O(1) update per shift is what makes the whole scan O(n).

A concrete example: find the maximum sum of any contiguous subarray of size k.

Running this on nums = [1, 3, 5, 7, 9, 11] with k = 3:

The maximum is 27. The naive approach (sum every length-k subarray from scratch) would cost O(n × k); the sliding window does it in O(n).

Sliding windows come in two flavors:

This pattern fits problems like longest/shortest subarray with a property, maximum/minimum sum of subarrays, and counting substrings or subarrays that satisfy some constraint.

3. Prefix Sum

A prefix sum array stores the cumulative sum of all elements up to each index. With it, you can answer range-sum queries in O(1) instead of recomputing the sum on every query.

For an input array, prefix[i] is the sum of nums[0] + nums[1] + ... + nums[i].

Input array:

Prefix sum array:

The second array is built from the first one position at a time:

Once the prefix array is built, the sum of any range [L, R] (inclusive) is just one subtraction:

For example, the sum of nums[2..4] is prefix[4] − prefix[1] = 25 − 4 = 21, which matches 5 + 7 + 9.

Construction costs O(n) time and O(n) extra space; each query then runs in O(1). This is the right trade-off when there are many range queries on a static array.

The same idea extends to other associative operations: prefix XOR for range-XOR queries, prefix counts for "how many even numbers in a range", and 2D prefix sums for sub-rectangle sums in matrices.

4. Dynamic Programming with Arrays

Many dynamic programming problems use a 1D or 2D array (the DP table) to cache solutions to smaller subproblems. The DP table is just a flat array where each cell stores the answer to one well-defined subproblem.

The simplest example is climbing stairs: from step 0, you can take 1-step or 2-step jumps; how many ways are there to reach step n?

The recurrence is:

This is just the Fibonacci sequence in disguise. The array-based bottom-up implementation fills the DP table left to right:

For n = 5, the table fills as [1, 1, 2, 3, 5, 8], so there are 8 ways to reach step 5. Each cell is computed in O(1) by reading two earlier cells, so the whole algorithm is O(n) time and O(n) space (and can be reduced to O(1) space by keeping only the last two values).

The recipe behind every array-based DP problem is the same:

Common interview problems that follow this pattern:

Most of these patterns reuse the same array fundamentals covered earlier: indexed access, contiguous memory, and careful management of insertions and deletions. The four patterns above (two pointers, sliding window, prefix sum, dynamic programming) are what turn arrays from a storage container into a core tool for algorithmic problem solving.