DSData Structures & Algorithms · Lesson 2 of 9

Arrays & Strings

The array is the simplest data structure: items in a row, side by side in memory. Almost everything else is built on top of it — and its strengths and weaknesses explain half of Big-O in practice.

An array stores elements in one contiguous block of memory. That layout gives its superpower: to find item 500, the computer multiplies 500 by the item size and jumps straight there — O(1) access by index, no searching. The weakness is the flip side of the same layout: inserting at the front means shifting every other element right one slot, O(n). Python's list, JavaScript's array, and Java's ArrayList are all dynamic arrays — arrays that grow by allocating a bigger block and copying when full.

Python


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

nums[2]           # O(1) — jump straight to index 2
nums.append(60)   # O(1) — write at the end (amortized)
nums.pop()        # O(1) — remove from the end

nums.insert(0, 5) # O(n) — shifts ALL elements right
nums.pop(0)       # O(n) — shifts ALL elements left
30 in nums        # O(n) — checks each item until found

# Classic pattern: two pointers. Reverse in place, O(n), no extra memory:
def reverse(items):
    left, right = 0, len(items) - 1
    while left < right:
        items[left], items[right] = items[right], items[left]
        left += 1
        right -= 1

Strings are arrays of characters with one twist in most languages: they're immutable. "Changing" a string actually builds a new one, copying everything — so concatenating in a loop is a hidden O(n²) trap. Every language has an escape hatch: collect pieces in a list and join once at the end.

Python


# TRAP — O(n^2): each += copies the whole string so far
def bad_join(words):
    s = ''
    for w in words:
        s += w        # copy, copy, copy...
    return s

# FIX — O(n): build list, join once
def good_join(words):
    return ''.join(words)

# Second classic pattern: sliding window.
# Longest substring without repeated characters, one pass:
def longest_unique(s):
    seen = {}          # char -> last index
    start = best = 0
    for i, ch in enumerate(s):
        if ch in seen and seen[ch] >= start:
            start = seen[ch] + 1     # jump window past the repeat
        seen[ch] = i
        best = max(best, i - start + 1)
    return best

longest_unique('abcabcbb')   # 3 ('abc')

◆ Note
Two pointers and sliding window are the two most common array interview patterns. Both replace a nested loop (O(n²)) with a single coordinated pass (O(n)). If a problem says 'subarray', 'substring', or 'pair that sums to', one of these is usually the answer.