Arrays & Strings

Arrays at the hardware level

An array is a block of contiguous memory holding a fixed number of equally-sized elements. Because every element is the same size and they're laid out next to each other, you can compute the address of element i in constant time: `base + i * size`. That's why array indexing is O(1).

Python's `list` and JavaScript's `Array` are dynamic arrays — they grow automatically when full, by allocating a bigger block (typically 2x) and copying. This makes `append` amortized O(1): most appends are O(1), but every so often you pay an O(n) copy.

Inserting or removing in the MIDDLE is O(n) because every element after the insertion point has to shift. Avoid this in tight loops.

Two-pointer technique

Many array problems can be solved by maintaining two indices that move toward or alongside each other. This often turns a naive O(n²) solution into O(n).

# Reverse an array in place
def reverse(s):
    i, j = 0, len(s) - 1
    while i < j:
        s[i], s[j] = s[j], s[i]
        i += 1
        j -= 1
    return s

print(reverse([1, 2, 3, 4, 5]))   # [5, 4, 3, 2, 1]

# Two Sum on a SORTED array — O(n)
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1     # need bigger sum, move left up
        else:
            right -= 1    # need smaller sum, move right down
    return []

print(two_sum_sorted([1, 3, 4, 5, 7], 9))   # [1, 4]

Sliding window

A sliding window is a pair of pointers [left, right] defining a contiguous range. The right pointer expands the window; the left contracts it when some condition is violated. Every element is visited at most twice — O(n) overall.

Use it for any "find the longest/shortest contiguous subarray with property X" problem.

function longestUnique(s) {
  const lastSeen = new Map();
  let best = 0;
  let start = 0;

  for (let i = 0; i < s.length; i++) {
    if (lastSeen.has(s[i]) && lastSeen.get(s[i]) >= start) {
      // collision INSIDE the current window — shrink from the left
      start = lastSeen.get(s[i]) + 1;
    }
    lastSeen.set(s[i], i);
    best = Math.max(best, i - start + 1);
  }
  return best;
}
console.log(longestUnique("abcabcbb"));    // 3 ("abc")
console.log(longestUnique("bbbbb"));        // 1

Strings are arrays

Strings in JS and Python are immutable — every modification creates a new string. If you're building a long string in a loop, prefer a list/array of pieces and join at the end.

# Bad — O(n²) due to string copies
result = ""
for x in items:
    result += str(x)

# Good — O(n)
result = "".join(str(x) for x in items)