Arrays in DSA: Introduction

The array is the most fundamental data structure in computing. Almost every other structure you’ll learn — strings, stacks, queues, hash maps, heaps — is built on top of one. Before we start solving problems with arrays, we need a clear picture of what they actually are at the memory level, and how that shape determines their cost.

What an array really is

An array is a block of contiguous memory holding values of the same size, laid out one after another. Each value sits at a known offset from the start, so the computer can compute its address with a single multiplication:

address_of(arr[i]) = base_address + i * element_size

That’s why indexing into an array is O(1) — no scanning, no comparisons, just an arithmetic shortcut. This is the property that makes arrays special.

index:    0     1     2     3     4
arr:    [ 10 | 20 | 30 | 40 | 50 ]
address: 100   104   108   112   116   (if each int takes 4 bytes)

The CPU loves this layout. When you read arr[0], modern processors typically pull a whole chunk of nearby memory into cache, so reading arr[1] and arr[2] afterwards is nearly free. This is called cache locality and it’s why arrays are not just theoretically fast — they’re practically fast too.

The Python lists caveat

Here’s where beginners get confused. In Python, “list” is what we usually call an array — but it isn’t quite the same as a classical C array.

nums = [10, 20, 30, 40, 50]
print(nums[2])    # 30

That looks like an array, and indexing it is O(1) just like an array. But under the hood, a Python list stores references to objects, not the values themselves. The list is a contiguous block of pointers; each pointer can point to an integer, a string, or any other object.

mixed = [1, "two", 3.0]    # legal in Python — impossible in a C array

For DSA purposes this distinction rarely matters — Python lists give you O(1) indexing, O(1) amortized append, and O(n) insert/delete in the middle, which is exactly what a classical array provides. Just be aware that:

• A “true” fixed-type array exists in Python via the standard array module or with NumPy.
• A Python list is dynamic — it grows automatically. C arrays are fixed in size at creation.
• In JavaScript, the Array type is similar to Python’s list — dynamic, can hold mixed types.

In this series we’ll use the word “array” to mean the abstract structure and the language’s natural ordered-collection type (list in Python, Array in JavaScript) interchangeably.

Creating arrays

In Python:

empty = []
nums = [10, 20, 30, 40, 50]
zeros = [0] * 5            # [0, 0, 0, 0, 0]
range_arr = list(range(5)) # [0, 1, 2, 3, 4]

In JavaScript:

const empty = [];
const nums = [10, 20, 30, 40, 50];
const zeros = new Array(5).fill(0);
const range = Array.from({ length: 5 }, (_, i) => i);

Indexing — the cheap operation

Reading and writing by index is the defining operation of an array.

nums = [10, 20, 30, 40, 50]

# Read — O(1)
print(nums[2])      # 30

# Write — O(1)
nums[2] = 99
print(nums)         # [10, 20, 99, 40, 50]

Negative indices in Python count from the end:

print(nums[-1])     # 50  (last element)
print(nums[-2])     # 40

JavaScript supports the same with .at():

const nums = [10, 20, 30, 40, 50];
console.log(nums.at(-1));   // 50

Out-of-range access:

• Python raises IndexError.
• JavaScript returns undefined.

Always check your bounds in a loop. Off-by-one errors are the most common bug in array code.

Time complexity at a glance

This is the table to memorise. It’s the heart of why we pick or avoid arrays for a given problem.

The asymmetry between “end” and “middle/front” is the most important insight here. Stack-like patterns (push and pop at the end) are essentially free. Queue-like patterns (insert at end, remove from front) cost O(n) per removal unless you switch to a different structure.

# Cheap
nums = [1, 2, 3]
nums.append(4)            # O(1) amortized
last = nums.pop()         # O(1)

# Expensive
nums.insert(0, 0)         # O(n) — shifts 1, 2, 3, 4 right
first = nums.pop(0)       # O(n) — shifts everything left

In Python, when you need a queue (FIFO), use collections.deque — its appendleft and popleft are O(1).

nums = [1, 2, 3, 4, 5]

a = nums[2]              # ?
nums[0] = 99             # ?
nums.append(6)           # ?
nums.insert(1, 100)      # ?
b = nums.pop()           # ?
c = nums.pop(0)          # ?
d = 99 in nums           # ?

Insertion — what really happens

When you insert at the middle of an array, the computer has to shift every later element one slot to the right to make room.

Before insert at index 1:
[ 10 | 20 | 30 | 40 | 50 |    ]

Inserting 99 at index 1:
[ 10 | 99 | 20 | 30 | 40 | 50 ]   ← 20, 30, 40, 50 all shifted right

For an array of length n, inserting at the front shifts all n elements. That’s O(n). If you insert n items at the front one by one, you’ve done O(n²) total work. This is why algorithms that build collections by repeatedly prepending are slow.

The fix: append at the end and reverse at the end, or use a structure designed for two-ended insertion.

Deletion — same story

Deleting from the middle is the mirror image: every element to the right shifts left.

nums = [10, 20, 30, 40, 50]
del nums[1]
print(nums)    # [10, 30, 40, 50]

If you need to delete many elements while iterating, don’t do it in place — build a new list with a comprehension or filter:

# Slow — O(n^2) if many deletes
nums = [1, 2, 3, 4, 5, 6]
for x in list(nums):
    if x % 2 == 0:
        nums.remove(x)      # O(n) each time

# Fast — O(n) total
nums = [1, 2, 3, 4, 5, 6]
nums = [x for x in nums if x % 2 != 0]
print(nums)    # [1, 3, 5]

1D arrays

Everything above is about one-dimensional arrays — a single sequence of values. This is the form you’ll use most.

prices = [9.99, 14.50, 7.25, 3.00]
total = sum(prices)
print(total)    # 34.74

2D arrays — a grid

A 2D array is an array of arrays. The natural shape is a grid — rows and columns.

grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]

print(grid[0][2])    # 3   — row 0, column 2
print(grid[2][0])    # 7

Building a 2D array of a fixed size:

rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]
print(grid)
# [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

A common bug — do not do this:

grid = [[0] * cols] * rows    # WRONG — all rows are the same object
grid[0][0] = 99
print(grid)    # every row's first cell is now 99

The * rows repeats the reference, not the row. Use a list comprehension instead.

Iterating a 2D array:

for r in range(len(grid)):
    for c in range(len(grid[0])):
        print(grid[r][c], end=" ")
    print()

Or more idiomatic Python:

for row in grid:
    for value in row:
        print(value, end=" ")
    print()

A 2D array of m × n elements takes O(m × n) to traverse fully. This is the cost floor of any algorithm that has to look at every cell — image filtering, grid pathfinding, dynamic programming tables.

When to reach for an array

Use an array when:

• You need fast access by index.
• You’re appending at the end and rarely (or never) inserting in the middle.
• You need to scan through values in order.
• The dataset fits in memory and order matters.

Reach for something else when:

• You need O(1) lookup by key, not by index → hash map.
• You need O(1) insertion at the front → deque or linked list.
• You need the smallest/largest element fast → heap.
• You need to avoid duplicates → set.

The job of a DSA learner is not to use arrays everywhere — it’s to recognise when they’re the right tool.

Practice problems

Try these to build intuition. For each, write the time and space complexity.

1. Given an array, return its sum without using sum().
2. Given an array, return a new array with each value doubled.
3. Given an array, return the largest value. Don’t use max().
4. Given an array and an index i, swap the element at index i with the last element.
5. Given two arrays of the same length, return a new array where each element is the sum of the two at that index.
6. Given a 2D grid, return the sum of all values in the top row.
7. Given a 2D grid of size n × n, return the sum of values along both diagonals. Be careful not to double-count the centre when n is odd.
8. Given an array, return a new array that contains only the elements at even indices (0, 2, 4, …).

Recap

You now know:

• An array is a block of contiguous memory with O(1) indexing
• Python lists and JavaScript arrays are dynamic, mixed-type relatives of classical arrays
• Read/write are O(1); insert/delete at the end are O(1); insert/delete in the middle are O(n)
• 2D arrays are arrays of arrays, indexed by [row][col]
• The asymmetry between “end” and “middle” drives most array-based design decisions

Next steps

Now that you know what arrays cost, it’s time to look at the patterns that come up again and again — traversal, search, reversal, rotation, prefix sums, and the famous Kadane’s algorithm preview.

→ Next: Arrays — Common Operations and Patterns

Questions or feedback? Email codeloomdevv@gmail.com.