Arrays & Two Pointers

Arrays are contiguous memory blocks. Random access is O(1), but insertion/deletion in the middle is O(n) because elements must shift.

Two Pointers is a pattern that uses two indices (left, right or slow, fast) moving through an array to avoid a nested loop — turning O(n²) into O(n).

When to use Two Pointers:
• Sorted array → pair sum, triplet sum, target difference
• Palindrome check → left and right move inward
• Remove duplicates in-place → slow/fast pointers
• Merging two sorted arrays

Sliding Window is a variant — a window [left, right] expands/contracts:
• Fixed window → move both pointers together
• Variable window → expand right until valid, shrink left until invalid

Pattern recognition: "subarray", "substring", "contiguous", "window" → try sliding window first.

1# ── Two Sum (sorted array) ───────────────────────────────────────
2def two_sum_sorted(nums: list[int], target: int) -> list[int]:
3    left, right = 0, len(nums) - 1
4    while left < right:
5        s = nums[left] + nums[right]
6        if s == target:
7            return [left, right]
8        elif s < target:
9            left += 1
10        else:
11            right -= 1
12    return []
13
14# ── Three Sum ─────────────────────────────────────────────────────
15def three_sum(nums: list[int]) -> list[list[int]]:
16    nums.sort()
17    result = []
18    for i in range(len(nums) - 2):
19        if i > 0 and nums[i] == nums[i-1]:   # skip duplicates
20            continue
21        left, right = i + 1, len(nums) - 1
22        while left < right:
23            s = nums[i] + nums[left] + nums[right]
24            if s == 0:
25                result.append([nums[i], nums[left], nums[right]])
26                while left < right and nums[left] == nums[left+1]: left += 1
27                while left < right and nums[right] == nums[right-1]: right -= 1
28                left += 1; right -= 1
29            elif s < 0: left += 1
30            else: right -= 1
31    return result
32
33# ── Sliding Window: longest substring without repeating chars ──────
34def length_of_longest_substring(s: str) -> int:
35    char_set = set()
36    left = max_len = 0
37    for right in range(len(s)):
38        while s[right] in char_set:       # shrink until valid
39            char_set.remove(s[left])
40            left += 1
41        char_set.add(s[right])
42        max_len = max(max_len, right - left + 1)
43    return max_len
44
45# ── Sliding Window: max sum subarray of size k ────────────────────
46def max_sum_subarray(nums: list[int], k: int) -> int:
47    window_sum = sum(nums[:k])
48    max_sum = window_sum
49    for i in range(k, len(nums)):
50        window_sum += nums[i] - nums[i - k]   # slide: add right, drop left
51        max_sum = max(max_sum, window_sum)
52    return max_sum
53
54# Tests
55print(two_sum_sorted([1, 2, 3, 4, 6], 6))  # [1, 3]
56print(three_sum([-1, 0, 1, 2, -1, -4]))    # [[-1,-1,2],[-1,0,1]]
57print(length_of_longest_substring("abcabcbb"))  # 3
58print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3)) # 9