Arrays and Strings

Learning Objectives

By the end of this page you should be able to:

• Explain how arrays are laid out in memory and why that makes indexing O(1)
• Distinguish static arrays from dynamic arrays (like Python lists) and explain amortized O(1) append
• State the time complexity of insertion, deletion, search, and access for arrays and strings
• Apply the two-pointer and sliding window patterns to solve array/string problems in O(n)
• Explain why strings are immutable in languages like Python and Java, and what that costs you
• Identify when an array is the wrong data structure for a problem

Quick Answer

An array is a block of memory holding elements of the same type, stored back-to-back, so any element can be reached instantly by calculating its address from an index. A string is, under the hood, just an array of characters. Arrays matter because they're the fastest possible structure for random access (O(1)) and they underpin nearly every other data structure — hash tables, heaps, and dynamic arrays like Python's list are all built on top of a raw array. The tradeoff is rigidity: inserting or deleting in the middle means shifting every element after it, which costs O(n). Most "array problems" in interviews and coursework are really about working around that shifting cost using techniques like two pointers or sliding windows instead of naive nested loops.

Core Content

Memory Layout: Why Arrays Are Fast

The whole reason arrays exist as a concept is contiguous memory. When you declare arr = [10, 20, 30, 40, 50], the runtime reserves one continuous block of memory and computes the address of any element with simple arithmetic:

address(arr[i]) = base_address + (i * size_of_element)

That formula is why arr[3] takes the same amount of time whether the array has 10 elements or 10 million — there's no searching involved, just one multiplication and one addition. This is the single most important fact about arrays: O(1) random access comes from contiguous memory, not from indexing syntax. A linked list can also give you node.value, but it can't give you O(1) access at position i, because it has to walk the chain from the head.

Static Arrays vs Dynamic Arrays

A static array (raw C-style array, or Java's int[]) has a fixed size decided at creation. You cannot grow it — resizing means allocating a brand-new block and copying everything over.

A dynamic array (Python list, Java ArrayList, C++ vector) looks resizable because the language hides the reallocation from you. Internally, it over-allocates: when the backing array fills up, it allocates a new block roughly 1.5x–2x the size and copies all existing elements into it.

# Dynamic array growth (conceptually what Python's list does internally)
arr = []
for i in range(6):
    arr.append(i)
    # Under the hood: if capacity is full, allocate new block (bigger),
    # copy all old elements, then add the new one.

That occasional expensive copy (O(n)) is why we say append is amortized O(1) — most appends are O(1), and the rare O(n) resize gets "spread" across all the cheap ones when you average over many operations.

Array Operations and Complexity

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

print(arr[0])          # Access by index -> O(1)
arr[2] = 35             # Update by index -> O(1)
arr.append(60)          # Add to end -> amortized O(1)
arr.insert(2, 99)       # Insert in middle -> O(n), shifts everything after index 2
arr.pop()               # Remove from end -> O(1)
arr.remove(99)          # Remove by value -> O(n), search + shift
99 in arr               # Linear search -> O(n)

Operation	Static Array	Dynamic Array (Python list)	Why
Access by index	O(1)	O(1)	Direct address calculation
Update by index	O(1)	O(1)	Same reason
Append at end	N/A (fixed size)	Amortized O(1)	Occasional resize copy is spread out
Insert at arbitrary index	O(n)	O(n)	Every following element shifts right
Delete at arbitrary index	O(n)	O(n)	Every following element shifts left
Delete/insert at end	O(1)	O(1)	Nothing to shift
Search by value	O(n)	O(n)	Must check elements one by one
Search in sorted array	O(log n) with binary search	O(log n)	Halve the search space each step

Strings as Character Arrays

Strings behave like arrays of characters, but with one crucial twist: in Python, Java, JavaScript, and C#, strings are immutable. You cannot change a character in place.

s = "Hello, World!"
print(s[0])        # 'H'  -> O(1) access, same as arrays
print(s[0:5])       # 'Hello' -> slicing creates a NEW string, O(k) where k = slice length
print(s.upper())    # creates a new string entirely, doesn't modify s

# This is illegal in Python:
# s[0] = 'J'   -> TypeError: 'str' object does not support item assignment

# To "modify" a string you must build a new one:
s = 'J' + s[1:]   # O(n) — copies the whole thing

If you're doing heavy string building in a loop, repeated concatenation (result += char) is O(n) per operation in the worst case because each += may create a new string and copy everything, making a naive loop O(n²) overall. The fix is to collect pieces in a list and join once:

# Bad: O(n^2) in the worst case
result = ""
for c in some_chars:
    result += c

# Good: O(n)
pieces = []
for c in some_chars:
    pieces.append(c)
result = "".join(pieces)

Pattern 1: Two Pointers

Two pointers replace nested loops (O(n²)) with a single pass (O(n)) by moving two indices toward each other or in tandem, exploiting some structure (often sortedness) in the data.

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome("racecar"))  # True

Another classic: given a sorted array, find two numbers that sum to a target, in O(n) instead of the O(n²) brute-force pair check.

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return (left, right)
        elif current < target:
            left += 1   # need a bigger sum
        else:
            right -= 1  # need a smaller sum
    return None

Pattern 2: Sliding Window

A sliding window keeps a moving subrange [left, right] and expands/shrinks it, avoiding recomputation from scratch. It's the go-to pattern for "longest/shortest substring/subarray satisfying condition X."

def longest_unique_substring(s: str) -> int:
    seen = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

print(longest_unique_substring("abcabcbb"))  # 3 ("abc")

Each character enters and leaves the window at most once, so even though there's a while loop nested inside a for loop, the total work is O(n), not O(n²).

Real-World Examples

• Image processing: a bitmap is a 2D array of pixel values; contiguous memory layout is exactly why image libraries can process rows so fast (cache-friendly sequential access).
• Text editors: search/replace features rely on string scanning algorithms (like KMP) that are O(n + m) rather than naive O(n·m) matching.
• Database engines: fixed-width row storage uses array-style offset math (base + row_number * row_size) to jump straight to a record without scanning the table.
• Network packet buffers: fixed-size arrays (ring buffers) are used because their size is bounded and predictable, avoiding the overhead of dynamic resizing in a hot path.

Key Terms

Term	Definition	Context/Related
Contiguous memory	Memory addresses allocated back-to-back with no gaps	Enables O(1) index access in arrays
Static array	Fixed-size array whose length is set at creation and cannot change	Contrast with dynamic array
Dynamic array	An array-backed structure that automatically resizes (e.g., Python list)	Uses amortized O(1) append
Amortized complexity	Average cost per operation over a sequence, even if some individual operations are expensive	Explains why append is "O(1)" despite occasional O(n) resizes
Index / subscript	The integer offset used to access an element in an array	arr[i]
Immutable string	A string whose contents cannot be changed after creation	Python, Java, JS strings; forces new-object creation on "modification"
Two pointers	A technique using two indices moving through a structure to avoid nested loops	Palindrome check, sorted two-sum
Sliding window	A technique that maintains a variable-size subrange and expands/shrinks it incrementally	Longest substring problems
In-place operation	An operation that modifies the existing array without allocating a new one	arr.reverse(), arr.sort()
Time complexity	A description of how an algorithm's runtime grows with input size	Big-O notation

Common Mistakes

Misconception 1: "Arrays and lists are always the same thing." Why it's wrong: In low-level languages (C, Java's raw arrays), an array is a fixed-size, contiguous block you cannot resize. In Python, the built-in list is a dynamic array — it's resizable and can hold mixed types, which is a different structure with different guarantees, even though the syntax arr[i] looks identical. Correct explanation: Call a fixed-size, single-type block a "static array" and Python's list (or Java's ArrayList) a "dynamic array." They share O(1) indexed access but differ in resizing behavior and, in Python's case, type flexibility.

Misconception 2: "Inserting into an array is O(1) because I just assign a value." Why it's wrong: Students confuse arr[i] = x (an update to an existing slot, genuinely O(1)) with "inserting a new element at position i" (which requires shifting every element from i onward one slot to the right to make room, an O(n) operation). Correct explanation: Updating an existing index is O(1). Inserting a new element in the middle of an array is O(n) because of the shift. Only inserting/removing at the very end avoids the shift.

Misconception 3: "Since strings act like arrays, I can modify them in place with s[i] = x." Why it's wrong: In Python, Java, JavaScript, and C#, strings are immutable — the language deliberately disallows in-place mutation so strings can be safely shared, hashed, and cached (e.g., used as dictionary keys) without fear of being changed underneath you. Correct explanation: Any "modification" of a string actually creates a brand-new string object. If you need frequent in-place character edits, convert to a mutable structure first (e.g., a list of characters in Python, or StringBuilder in Java), edit that, then rejoin/convert back.

Comparison and Connections

Concept	Array	Linked List
Memory layout	Contiguous block	Scattered nodes connected by pointers
Access by index	O(1)	O(n) — must traverse from head
Insert/delete at known position	O(n) — shifting	O(1) — just relink pointers, once you have a reference to the node
Insert/delete at end	O(1) (dynamic array, amortized)	O(1) if tail pointer kept, else O(n)
Memory overhead	Low (just the data)	Higher (extra pointer per node)
Cache performance	Excellent (sequential memory)	Poor (nodes scattered in memory)

Concept	Static Array	Dynamic Array
Size	Fixed at creation	Grows/shrinks automatically
Resize cost	Not possible without manual reallocation	Occasional O(n) copy, amortized to O(1)
Type	Usually single, fixed type	Python allows mixed types
Example	C's int arr[10]	Python list, Java ArrayList, C++ vector

Concept	Mutable String (e.g., StringBuilder)	Immutable String (Python str, Java String)
In-place edits	Yes, O(1) amortized append	No — every "edit" builds a new string
Safe as dict/hash key	Risky if mutated after insertion	Always safe — content never changes
Best use case	Building strings piece by piece in a loop	Passing around, comparing, hashing text

Practice Questions

Recall

1. What is the time complexity of accessing an element by index in an array, and why? Answer guidance: O(1) — the address is computed directly with base + index * element_size, no traversal needed.
2. Why are strings in Python considered immutable? Answer guidance: The language disallows changing characters in place so strings can be safely shared, hashed, and used as dictionary keys; any "change" creates a new string object.

Understanding

3. Explain why appending to a Python list is called "amortized O(1)" rather than simply "O(1)." Answer guidance: Most appends just place the value in existing spare capacity (O(1)), but occasionally the backing array is full and must be reallocated and copied (O(n)). Averaged over many appends, the cost per operation works out to O(1).
4. Why does inserting an element in the middle of an array cost O(n) but inserting at the end cost O(1) (amortized)? Answer guidance: Middle insertion requires shifting every subsequent element one slot right to preserve contiguity and order; end insertion has nothing after it to shift.

Application

5. You need to check if a sorted array of integers contains any pair summing to a target value, without using extra memory for a hash set. Which pattern would you use and what's its time complexity? Answer guidance: Two pointers starting at both ends, moving inward based on whether the current sum is too high or too low; O(n) time, O(1) extra space.
6. You need to find the longest substring of a string with no repeating characters. What pattern applies, and roughly how would you implement it? Answer guidance: Sliding window with a set tracking characters currently in the window; expand the right pointer, and when a duplicate is found, shrink from the left until the duplicate is removed. O(n) overall.

Analysis

7. Compare using an array versus a linked list for a scenario where you frequently insert/remove at the front of a large collection but rarely access by index. Which is better and why? Answer guidance: Linked list — front insertion/removal is O(1) with a head pointer, versus O(n) for an array because everything must shift. Since index access isn't needed often, the array's main advantage (O(1) access) isn't being used.
8. A junior developer writes a loop that builds a large string using result += next_piece thousands of times, then complains their code is slow. Diagnose the issue and propose a fix. Answer guidance: Because strings are immutable, each += may allocate a new string and copy all previous content, making the loop O(n²) in the worst case. Fix: append pieces to a list and use "".join(pieces) once at the end, which is O(n).

FAQ

Q: Is a Python list actually an array? A: Under the hood, yes — CPython implements list as a dynamic array of pointers to objects, not a linked list. That's why indexing is O(1) and why append is amortized O(1) rather than always O(1).

Q: Why can't I get O(1) insertion in the middle of an array like I can with a linked list? A: Because an array's whole speed advantage (O(1) indexing) depends on every element being at a precise, contiguous offset. Inserting in the middle without shifting would break that contiguity and destroy the O(1) access guarantee for later reads.

Q: When should I use two pointers versus sliding window? A: Use two pointers when you're looking at pairs of positions (often converging from both ends, frequently requiring sorted input) — like two-sum or palindrome checks. Use sliding window when you're tracking a contiguous subrange that grows and shrinks — like longest substring or subarray problems.

Q: Does string immutability mean strings are always slower than mutable alternatives? A: Not for read-heavy use (indexing, comparing, hashing) — those are just as fast as arrays. It only becomes a real cost in write-heavy scenarios like repeated concatenation, which is why languages provide mutable alternatives (StringBuilder, io.StringIO, joining a list) for that specific case.

Q: Why does binary search need a sorted array? A: Binary search works by eliminating half the remaining elements each step based on a comparison with the middle element. That elimination is only valid if you know everything to one side is guaranteed smaller (or larger) — which is only true when the array is sorted.

Q: What's the actual memory cost difference between an array and a linked list holding the same data? A: An array of n integers uses roughly n × (size of int) bytes. A singly linked list needs that same data plus one pointer per node (commonly 8 bytes on a 64-bit system), so it can use noticeably more memory, especially for small element types.

Quick Revision

• Arrays store elements in contiguous memory → O(1) access via base + i * size.
• Static arrays have fixed size; dynamic arrays (Python list) resize automatically.
• Dynamic array append is amortized O(1); occasional resize copy is O(n).
• Insert/delete at an arbitrary index: O(n) due to shifting elements.
• Insert/delete at the end: O(1) (amortized for dynamic arrays).
• Linear search: O(n); binary search on sorted data: O(log n).
• Strings are immutable in Python/Java/JS — every "edit" creates a new string.
• Naive string concatenation in a loop can be O(n²); use "".join() for O(n).
• Two pointers: converge from both ends (or move in tandem) to avoid O(n²) nested loops — needs sorted or structured input.
• Sliding window: maintain a moving subrange, expand/shrink to solve substring/subarray problems in O(n).
• Arrays win on cache performance and index access; linked lists win on cheap insert/delete when you already hold a node reference.
• Choosing the right pattern (two pointers vs sliding window vs brute force) is usually the difference between O(n) and O(n²) on interview problems.

Related Topics

Prerequisites

• Basic understanding of variables, loops, and functions in a programming language
• Big-O notation and how to reason about time/space complexity

Related Topics

• Linked Lists (contrast in memory layout and operation costs)
• Hash Tables (built using arrays plus a hashing function)
• Sorting Algorithms (many rely on array indexing and swapping)

Next Topics

• Stacks and Queues
• Recursion and Backtracking
• Searching Algorithms (linear vs. binary search in depth)