Lesson 2 of 9

Arrays & Strings

An stores items in a row, side by side in . You'll learn which operations are fast or slow on arrays and , and two common patterns for working with them.

An array stores elements in one contiguous block of memory. That layout is its main strength: 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 , JavaScript's array, and Java's ArrayList are all dynamic arrays — arrays that grow by allocating a bigger block and copying when full.


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 . "Changing" a string actually builds a new one, copying everything — so concatenating in a is a hidden O(n²) trap. Every language has an escape hatch: collect pieces in a list and join once at the end.


# 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')

Finished reading?Mark it done to track your progress.

Tip: use the ← and → keys to move between lessons.