2. Arrays & Strings

What Interviewers Test Here

• Pattern recognition: two pointers, sliding window, prefix sums
• In-place manipulation without extra space
• Careful index management (off-by-one errors are common)
• String immutability awareness in Python

Core Templates

# --- Two pointers on sorted array ---
def two_sum_sorted(arr: list[int], target: int) -> list[int]:
    l, r = 0, len(arr) - 1
    while l < r:
        s = arr[l] + arr[r]
        if s == target:   return [l, r]
        elif s < target:  l += 1
        else:             r -= 1
    return []

# --- Sliding window (variable size) ---
from collections import defaultdict

def longest_k_distinct(s: str, k: int) -> int:
    freq: dict[str, int] = defaultdict(int)
    best = left = 0
    for right, c in enumerate(s):
        freq[c] += 1
        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

# --- Prefix sum for range queries ---
def build_prefix(arr: list[int]) -> list[int]:
    p = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        p[i+1] = p[i] + x
    return p

def range_sum(p: list[int], l: int, r: int) -> int:
    return p[r+1] - p[l]

# --- Kadane's: maximum subarray sum ---
def max_subarray(nums: list[int]) -> int:
    best = cur = nums[0]
    for x in nums[1:]:
        cur  = max(x, cur + x)
        best = max(best, cur)
    return best

---

Conceptual Q&A

Q1: "Given a string, find the length of the longest substring without repeating characters."

Walkthrough — think aloud:

"Let me start with the brute force: I generate all substrings and check each for duplicates. That's $O(n^3)$ — too slow.

What signal do I see? 'Substring' and 'constraint' (no repeating) — that's a sliding window signal. I'll maintain a window [left, right] that is always valid (no duplicates). I expand right one character at a time. When I hit a duplicate, I need to shrink from left until the duplicate is gone.

To check for duplicates efficiently, I'll use a dict mapping each character to its most recent index. When I see a character already in the window, I jump left past its last occurrence.

Complexity: $O(n)$ time, $O(min(n, 26))$ = $O(1)$ space for lowercase letters."

def length_of_longest_substring(s: str) -> int:
    char_index: dict[str, int] = {}   # char → most recent index
    best = left = 0
    for right, c in enumerate(s):
        # If c is in the current window, move left past it
        if c in char_index and char_index[c] >= left:
            left = char_index[c] + 1
        char_index[c] = right
        best = max(best, right - left + 1)
    return best

# Trace: s = "abcabcbb"
# right=0 'a': window=[0,0] best=1
# right=1 'b': window=[0,1] best=2
# right=2 'c': window=[0,2] best=3
# right=3 'a': 'a' last at 0, left moves to 1. window=[1,3] best=3
# right=4 'b': 'b' last at 1, left moves to 2. window=[2,4] best=3
# right=5 'c': 'c' last at 2, left moves to 3. window=[3,5] best=3
# Answer: 3 ("abc")

---

Q2: "Given an array of integers, find the maximum product of any two elements."

Walkthrough:

"Brute force: check every pair — $O(n^2)$. Can I do better?

I think about what pair gives maximum product. Since we could have negative numbers, the maximum product is either: (a) the two largest positives, or (b) the two most negative numbers (negative × negative = positive). So I need to track: max1, max2, min1, min2.

Actually, simpler: if I sort the array, the answer is either arr[-1] * arr[-2] (two largest) or arr[0] * arr[1] (two most negative). One pass to find these extremes is $O(n)$."

def max_product_two(nums: list[int]) -> int:
    # Sort and compare endpoints — O(n log n)
    nums.sort()
    return max(nums[-1] * nums[-2], nums[0] * nums[1])

# O(n) version — single pass
def max_product_two_linear(nums: list[int]) -> int:
    max1 = max2 = float("-inf")
    min1 = min2 = float("inf")
    for x in nums:
        if x >= max1:   max1, max2 = x, max1
        elif x > max2:  max2 = x
        if x <= min1:   min1, min2 = x, min1
        elif x < min2:  min2 = x
    return max(max1 * max2, min1 * min2)

---

Q3: "You have a mountain array (increases then decreases). Find the peak index."

Walkthrough:

"I see 'find position' + 'sorted-like structure' → binary search signal. The array increases on the left side of the peak and decreases on the right. I can binary search by comparing arr[mid] with arr[mid+1]: if arr[mid] < arr[mid+1], the peak is to the right; otherwise it's at mid or to the left. Complexity: $O(\log n)$."

def peak_index_mountain(arr: list[int]) -> int:
    l, r = 0, len(arr) - 1
    while l < r:
        mid = (l + r) // 2
        if arr[mid] < arr[mid + 1]:
            l = mid + 1   # ascending: peak is to the right
        else:
            r = mid       # descending: peak is at mid or left
    return l

---