Arrays & Strings

Arrays & Strings

Arrays store elements in contiguous memory — O(1) random access, O(n) insert/delete at arbitrary positions.

Static vs Dynamic Arrays

• Static: Fixed size at creation (C arrays)
• Dynamic (Python list, Java ArrayList): Resize by doubling when full
  • Append: O(1) amortized — occasional O(n) resize is averaged out over all appends

Complexity

| Operation | Array | Dynamic Array (Python list) | |-------------------|--------|-----------------------------| | Access by index | O(1) | O(1) | | Append | — | O(1) amortized | | Insert at front | O(n) | O(n) | | Delete at index | O(n) | O(n) | | Search (unsorted) | O(n) | O(n) | | Search (sorted) | O(log n) | O(log n) |

String Immutability in Python

Strings are immutable — building with += in a loop is O(n²) because each concatenation copies the whole string. Use list + "".join():

# Bad — O(n^2): each += creates a new string
result = ""
for c in chars:
    result += c

# Good — O(n): build list, join once at the end
parts = []
for c in chars:
    parts.append(c)
result = "".join(parts)

Two Pointer Variations

There are three distinct two-pointer patterns:

1. Opposite ends — sorted array pair problems

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:   return [left, right]
        elif s < target:  left += 1
        else:             right -= 1
    return []

2. Different speeds — fast/slow (cycle, middle)

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

3. Same direction with offset — string comparison when lengths differ

def is_one_edit_away_insert(shorter, longer):
    i = j = diff = 0
    while i < len(shorter):
        if shorter[i] != longer[j]:
            diff += 1
            if diff > 1: return False
            j += 1        # skip one char in longer
        else:
            i += 1; j += 1
    return True

Sliding Window Pattern

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    best = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # slide
        best = max(best, window_sum)
    return best

Prefix Sum

def subarray_sum(arr, k):
    """Count subarrays summing to k — O(n) with prefix hash."""
    prefix_count = {0: 1}
    total = count = 0
    for x in arr:
        total += x
        count += prefix_count.get(total - k, 0)
        prefix_count[total] = prefix_count.get(total, 0) + 1
    return count

In-Place Matrix Rotation

Rotate NxN matrix 90° clockwise in place — two approaches:

Transpose + reverse each row (clean):

def rotate_90_cw(matrix):
    n = len(matrix)
    # Transpose: swap [i][j] with [j][i]
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row
    for row in matrix:
        row.reverse()

Layer-by-layer 4-cycle (classic in-place):

def rotate_layers(matrix):
    n = len(matrix)
    for layer in range(n // 2):
        last = n - layer - 1
        for i in range(layer, last):
            offset = i - layer
            top = matrix[layer][i]
            # left → top
            matrix[layer][i] = matrix[last - offset][layer]
            # bottom → left
            matrix[last - offset][layer] = matrix[last][last - offset]
            # right → bottom
            matrix[last][last - offset] = matrix[i][last]
            # top → right
            matrix[i][last] = top

Formula: new_row = old_col, new_col = size - old_row - 1 Time: O(n²), Space: O(1)

Character Frequency Counting

from collections import Counter

# Palindrome permutation check
def is_palindrome_permutation(s):
    freq = Counter(c.lower() for c in s if c != ' ')
    return sum(v % 2 for v in freq.values()) <= 1

# Anagram check
def is_anagram(s, t):
    return Counter(s) == Counter(t)

Key Interview Tips

• Off-by-one errors are the #1 bug — always trace boundary conditions on paper
• Consider sorting first if order doesn't matter (often unlocks O(n log n))
• Two-pointer technique eliminates a nested loop → O(n²) → O(n)
• For in-place 2D rotation: transpose + reverse-rows is the cleanest approach