3. Arrays & Strings

What Is an Array?

An array is a contiguous block of memory where each element is at a fixed offset from the start. In Python, list is a dynamic array — it automatically resizes when you add elements.

Analogy: A parking lot with numbered spaces. You can go directly to space 42 ($O(1)$ access), but adding a new space in the middle requires moving all cars to the right.

---

3.1 Slicing and Common Operations

arr = [10, 20, 30, 40, 50]

# Slicing — arr[start:stop:step] — creates a new list
arr[1:4]       # [20, 30, 40]     — index 1 up to (not including) 4
arr[:3]        # [10, 20, 30]     — from start
arr[2:]        # [30, 40, 50]     — to end
arr[::-1]      # [50, 40, 30, 20, 10] — reversed copy
arr[::2]       # [10, 30, 50]     — every other element

# Useful list comprehensions
squares = [x**2 for x in range(6)]          # [0, 1, 4, 9, 16, 25]
evens   = [x for x in range(10) if x % 2 == 0]  # [0, 2, 4, 6, 8]
flat    = [x for row in [[1,2],[3,4]] for x in row]  # [1, 2, 3, 4]

# String as a sequence of characters
s = "hello world"
s[0]           # 'h'
s[6:]          # 'world'
s.upper()      # 'HELLO WORLD'
s.split()      # ['hello', 'world']
" ".join(["hello", "world"])   # 'hello world'
s.replace("world", "Python")   # 'hello Python'
s.startswith("hello")          # True
s.count("l")                   # 3

# IMPORTANT: strings are immutable — don't concatenate in a loop
# Bad  (O(n²)):  result = ""; for w in words: result += w
# Good (O(n)):   result = "".join(words)

---

3.2 Two Pointers

Problem type: Find a pair in a sorted array, remove duplicates, check palindromes.
Idea: Start one pointer at each end and move them toward each other.

# --- Check if a string is a palindrome ---
def is_palindrome(s: str) -> bool:
    # Only consider alphanumeric, ignore case
    cleaned = [c.lower() for c in s if c.isalnum()]
    l, r = 0, len(cleaned) - 1
    while l < r:
        if cleaned[l] != cleaned[r]:
            return False
        l += 1
        r -= 1
    return True

print(is_palindrome("A man, a plan, a canal: Panama"))  # True

# --- Find pair that sums to target (sorted array) ---
def pair_sum(arr: list[int], target: int) -> tuple[int, int] | None:
    l, r = 0, len(arr) - 1
    while l < r:
        total = arr[l] + arr[r]
        if total == target:
            return arr[l], arr[r]   # found it
        elif total < target:
            l += 1   # need larger sum → move left pointer right
        else:
            r -= 1   # need smaller sum → move right pointer left
    return None      # no pair found

# --- Remove duplicates from sorted array (in-place) ---
def remove_duplicates(arr: list[int]) -> int:
    if not arr:
        return 0
    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1   # length of deduplicated portion

---

3.3 Sliding Window

Problem type: Longest/shortest subarray or substring satisfying a condition.
Idea: Maintain a "window" [left, right]. Expand right to include new elements, shrink left when the window becomes invalid.

# --- Maximum sum of any contiguous subarray of size k ---
def max_sum_subarray(arr: list[int], k: int) -> int:
    # Build first window
    window_sum = sum(arr[:k])
    best = window_sum
    # Slide window: remove leftmost, add new rightmost
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        best = max(best, window_sum)
    return best

print(max_sum_subarray([2, 1, 5, 1, 3, 2], k=3))  # 9  (5+1+3)

# --- Longest substring without repeating characters ---
def longest_unique_substring(s: str) -> int:
    char_index: dict[str, int] = {}   # last seen index of each char
    best = left = 0
    for right, c in enumerate(s):
        if c in char_index and char_index[c] >= left:
            left = char_index[c] + 1   # shrink window past the duplicate
        char_index[c] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique_substring("abcabcbb"))  # 3 ("abc")

---

3.4 Prefix Sums

Problem type: Fast range sum queries on a static array.
Idea: Precompute cumulative sums so any range query is $O(1)$.

def build_prefix(arr: list[int]) -> list[int]:
    """prefix[i] = sum of arr[0..i-1]"""
    prefix = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        prefix[i + 1] = prefix[i] + x
    return prefix

def range_sum(prefix: list[int], l: int, r: int) -> int:
    """Sum of arr[l..r] inclusive — O(1)."""
    return prefix[r + 1] - prefix[l]

# Example
arr    = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = build_prefix(arr)
print(range_sum(prefix, 2, 5))  # 4+1+5+9 = 19

---