Arrays & Strings

What is an array?

An array is a collection of elements of the same type stored next to each other in memory — like a row of numbered lockers. Each locker has an index: 0, 1, 2, …

index:    0    1    2    3    4
value:  [12] [45] [ 7] [30] [21]
address: 1000 1004 1008 1012 1016

In the 3D model, the small numbers above each box are the indexes and the grey numbers in front are the memory addresses.

Analogy: houses on a street with numbered plots of equal width. If you know where the street starts and how wide each plot is, you can walk straight to house number 57 — you don’t need to visit houses 1 to 56 first.

The superpower: O(1) access

Because elements are the same size and contiguous, the computer can calculate where any element lives:

address of a[i] = base address + i × size of one element

So a[0] and a[999999] take exactly the same time. This is called random access, and it is why arrays are the backbone of almost every program.

The weakness: inserting and deleting in the middle

Arrays can’t have gaps. To insert at index i, every element from i onward must shift one place right. To delete, everything after it must shift left. With n elements that can be n moves → O(n). Try it in the model and count the moves.

Adding or removing at the end is cheap, because nothing has to move.

Static vs dynamic arrays

A static array (int a[10] in C) has a fixed capacity. A dynamic array (Python list, C++ vector, Java ArrayList) grows automatically: when full, it allocates a bigger block (usually 2×) and copies everything over. Copying is O(n), but it happens so rarely that appending is still O(1) on average (this is called amortised O(1)).

Strings are arrays of characters

A string like "level" is stored as an array of characters: ['l','e','v','e','l']. Everything you learn about arrays applies: s[i] is O(1), searching is O(n), and many string problems are solved with array techniques.

In Python and Java, strings are immutable — “changing” a string creates a new one. That’s why building a long string with += in a loop is slow; use a list and ''.join() (Python) or StringBuilder (Java).

The two-pointer technique

Many array and string problems are solved with two indexes moving towards each other:

• Reverse: swap a[L] and a[R], then move L right and R left until they meet.
• Palindrome check: compare s[L] and s[R]; any mismatch means “not a palindrome”.

Both take O(n) time and O(1) extra space — no second array needed.

Code

a = [12, 45, 7, 30, 21]

print(a[3])          # O(1) access → 30
a.append(99)         # O(1) amortised, at the end
a.insert(0, 5)       # O(n): everything shifts right
a.pop(2)             # O(n): everything after index 2 shifts left
print(45 in a)       # O(n) linear search

def reverse(arr):
    L, R = 0, len(arr) - 1
    while L < R:
        arr[L], arr[R] = arr[R], arr[L]
        L += 1
        R -= 1

def is_palindrome(s):
    L, R = 0, len(s) - 1
    while L < R:
        if s[L] != s[R]:
            return False
        L += 1
        R -= 1
    return True

print(is_palindrome("racecar"))   # True
print(is_palindrome("hello"))     # False

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool isPalindrome(const string& s) {
    int L = 0, R = (int)s.size() - 1;
    while (L < R) {
        if (s[L] != s[R]) return false;
        L++; R--;
    }
    return true;
}

int main() {
    vector<int> a = {12, 45, 7, 30, 21};
    cout << a[3] << "\n";                 // O(1) → 30
    a.push_back(99);                      // O(1) amortised
    a.insert(a.begin(), 5);               // O(n)
    a.erase(a.begin() + 2);               // O(n)
    reverse(a.begin(), a.end());          // two pointers inside
    cout << boolalpha << isPalindrome("level") << "\n";   // true
}

2D arrays (matrices)

A 2D array grid[rows][cols] is stored row by row in one long block (row-major order). The address of grid[r][c] is base + (r × cols + c) × size. Images, game boards and DP tables are all 2D arrays.

Where are arrays used?

• Practically everywhere: lists of marks, pixels of an image, audio samples, game boards.
• As the base for other structures: stacks, queues, heaps and hash tables are usually built on arrays.
• Because elements sit together in memory, arrays are very cache-friendly — the CPU loads neighbours in one go, making loops over arrays extremely fast.

Common mistakes

• Off-by-one errors: the last index is n − 1, not n.
• Inserting/removing at the front of a big array inside a loop (accidentally O(n²)).
• Forgetting that strings are immutable in Python/Java.