Arrays, Strings & Matrices

Arrays in memory

An array is a contiguous block of memory. Element i lives at base + i × size, so:

Strings are arrays of characters. In Python and Java, strings are immutable — every “modification” creates a new string. In C++, std::string is mutable.

Core techniques

1. Running aggregates in one pass

Many array problems reduce to carrying a small amount of state through a single scan: min so far, max so far, count, sum.

def max_profit(prices):
    min_price, best = float("inf"), 0
    for p in prices:
        min_price = min(min_price, p)
        best = max(best, p - min_price)
    return best

2. Kadane's algorithm (maximum subarray)

At each index decide: extend the previous subarray, or start fresh here?

def max_subarray(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)      # best subarray ENDING at this index
        best = max(best, cur)
    return best

int maxSubArray(vector<int>& nums) {
    int cur = nums[0], best = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        cur = max(nums[i], cur + nums[i]);
        best = max(best, cur);
    }
    return best;
}

This is really a tiny dynamic program: dp[i] = max(nums[i], dp[i-1] + nums[i]). Variants: max product (track min too, since negatives flip), circular max subarray (max(normal Kadane, total − min subarray), unless all negative).

3. Read/write pointers (in-place filtering)

Overwrite the array as you go; write marks the end of the kept region.

def remove_element(nums, val):
    write = 0
    for x in nums:
        if x != val:
            nums[write] = x
            write += 1
    return write           # new length

Same shape solves Move Zeroes, Remove Duplicates from Sorted Array, String Compression. This is a flavour of Two Pointers.

4. Reversal tricks

Rotating right by k: reverse whole, reverse first k, reverse rest.

def rotate(nums, k):
    n = len(nums); k %= n
    def rev(l, r):
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1; r -= 1
    rev(0, n - 1); rev(0, k - 1); rev(k, n - 1)

The same trick reverses the words in a sentence in place: reverse the whole string, then reverse each word.

5. Prefix and suffix passes

When each answer depends on “everything to the left” and “everything to the right”, do two passes.

def product_except_self(nums):
    n = len(nums)
    ans = [1] * n
    for i in range(1, n):             # ans[i] = product of nums[0..i-1]
        ans[i] = ans[i - 1] * nums[i - 1]
    suffix = 1
    for i in range(n - 1, -1, -1):    # multiply by product of nums[i+1..]
        ans[i] *= suffix
        suffix *= nums[i]
    return ans

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, 1);
    for (int i = 1; i < n; i++) ans[i] = ans[i - 1] * nums[i - 1];
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) { ans[i] *= suffix; suffix *= nums[i]; }
    return ans;
}

Trapping Rain Water is the same idea: water above bar i is min(maxLeft[i], maxRight[i]) − h[i].

6. Encoding two values in one cell

To update in place when new values depend on old ones (Game of Life, Set Matrix Zeroes), store the new state in unused bits or use the first row/column as marker storage, then do a final pass.

Strings

Character arithmetic

idx = ord(c) - ord('a')        # 'a'..'z' → 0..25
c = chr(ord('a') + idx)
c.isalnum(); c.isdigit(); c.lower()

int idx = c - 'a';
char c2 = 'a' + idx;
isalnum(c); isdigit(c); tolower(c);

Useful built-ins

s.split()               # split on whitespace, drops empties
" ".join(words)
s[::-1]                 # reversed copy
s.find("ab")            # -1 if absent
s.startswith("pre")
s.count("a")

reverse(s.begin(), s.end());
s.substr(pos, len);          // O(len) copy!
s.find("ab");                // string::npos if absent
stringstream ss(s); string w; while (ss >> w) { /* words */ }
to_string(42); stoi("42");

Palindromes

• Check: two pointers from both ends.
• Longest palindromic substring: expand around each center (2n − 1 centers), O(n²), or Manacher's O(n) (see String Algorithms).

def longest_palindrome(s):
    best = ""
    for center in range(2 * len(s) - 1):
        l, r = center // 2, (center + 1) // 2      # odd and even centers
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        if r - l - 1 > len(best):
            best = s[l + 1:r]
    return best

Matrices (2D arrays)

Traversal helpers

R, C = len(grid), len(grid[0])
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for r in range(R):
    for c in range(C):
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C:
                ...

int R = grid.size(), C = grid[0].size();
int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++)
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            // ...
        }

Rotation and transposition

def rotate(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

Spiral order

def spiral_order(m):
    out = []
    top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1): out.append(m[top][c])
        top += 1
        for r in range(top, bottom + 1): out.append(m[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1): out.append(m[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1): out.append(m[r][left])
            left += 1
    return out

Diagonals

Cells on the same main diagonal share r − c; on the same anti-diagonal they share r + c. Useful for N-Queens and diagonal traversal problems.

Common mistakes

• Off-by-one on inclusive vs exclusive ranges. Decide once ([lo, hi) or [lo, hi]) and stick with it.
• Modifying an array while iterating it with a for x in arr loop.
• Python [[0] * C] * R creates R references to the same row. Use [[0] * C for _ in range(R)].
• Integer overflow in C++ when summing/multiplying — use long long.
• Assuming the grid is square when it's R × C.
• Forgetting empty input ([], "", [[]]).