Pointer Manipulation

The fundamental swap is used in partition, sorting, and two-pointer algorithms. Must be instant.

a[i], a[j] = a[j], a[i]

Single-pass min/max tracking is the basis for best-time-to-buy-stock and range queries.

mn, mx = min(a), max(a)

# Manual loop:
mn = mx = a[0]
for x in a[1:]:
    if x < mn: mn = x
    if x > mx: mx = x

Correct 2D init avoids the shared-row aliasing bug. Foundation for all grid DP.

grid = [[0]*cols for _ in range(rows)]

Array rotation underpins circular buffer logic and modular index arithmetic.

a[-1:] + a[:-1]
# or
a.insert(0, a.pop())

Sortedness check is a precondition guard for binary search and merge operations.

all(a[i] <= a[i+1] for i in range(len(a)-1))

In-place segment reversal is the building block for rotate-array and next-permutation.

# Reverse a[l:r+1] in-place
while l < r:
    a[l], a[r] = a[r], a[l]
    l += 1; r -= 1

Flattening linearizes grid traversal and simplifies nested iterations.

flat = [x for row in grid for x in row]

Two-pointer write keeps unique elements in-place with O(1) space. Core array cleanup technique.

# Two-pointer write — keep unique in-place
w = 1
for r in range(1, len(a)):
    if a[r] != a[r - 1]:
        a[w] = a[r]
        w += 1
# a[:w] has unique elements

Lomuto partition is the core of quicksort and quickselect. Know it cold for kth-element problems.

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

Three-way partition handles duplicates efficiently. Classic for sort-colors type problems.

lo, mid, hi = 0, 0, len(a) - 1
while mid <= hi:
    if a[mid] < pivot:
        a[lo], a[mid] = a[mid], a[lo]
        lo += 1; mid += 1
    elif a[mid] == pivot:
        mid += 1
    else:
        a[mid], a[hi] = a[hi], a[mid]
        hi -= 1

String reversal is the most basic pointer drill. Used in palindrome checks and word reversal.

s[::-1]

Character classification is needed for parsing, validation, and the valid-palindrome problem.

c.isalnum()

Case normalization is a preprocessing step for anagram detection and string matching.

s.lower()
# Manual: chr(ord(c) + 32)

Counting specific characters is a frequency-analysis building block for string problems.

sum(1 for c in s if c in 'aeiou')

Splitting tokenizes input for word-count, reverse-words, and parsing problems.

s.split(',')

Join reconstructs strings after manipulation. Paired with split in word-reversal problems.

','.join(lst)

Stripping removes noise before comparison. Needed for valid-palindrome and input parsing.

s.strip()

Character counting is the core technique for anagram detection and frequency-based problems.

from collections import Counter
freq = Counter(s)

The node class is the foundation for all linked list operations. Know the constructor cold.

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

Linear traversal is how you access linked list elements. Basis for search and length calculation.

while cur: cur = cur.next

Length calculation requires full traversal. Used as a helper in remove-nth-from-end.

length = 0
while cur:
    length += 1
    cur = cur.next

Tail insertion requires traversal to end. Know this for list construction problems.

while cur.next:
    cur = cur.next
cur.next = Node(val)

Head insertion is O(1) and builds lists in reverse. Core for reverse-linked-list.

new = Node(val)
new.next = head
head = new

Dummy-head deletion avoids special-casing the head node. Essential linked list technique.

dummy = Node(0)
dummy.next = head
prev, cur = dummy, head
while cur:
    if cur.val == target:
        prev.next = cur.next
        break
    prev, cur = cur, cur.next
head = dummy.next

Fast/slow pointer finds the middle in one pass. Core technique for merge sort on lists.

slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow is at the middle

Converging pointers shrink the search space from both ends. Core of two-sum-sorted and palindrome.

l, r = 0, len(a) - 1
while l < r:
    # process a[l], a[r]
    l += 1; r -= 1

Same-direction (slow/fast) pointers power sliding window and linked list cycle detection.

slow, fast = 0, 0
while fast < len(a):
    # expand fast, conditionally advance slow
    fast += 1

Write-pointer skips unwanted values. O(1) space removal pattern.

w = 0
for r in range(len(a)):
    if a[r] != val:
        a[w] = a[r]
        w += 1
# a[:w] has val removed

Move-zeroes is remove-element followed by a fill. Classic two-pointer warm-up.

w = 0
for r in range(len(a)):
    if a[r] != 0:
        a[w] = a[r]
        w += 1
while w < len(a):
    a[w] = 0
    w += 1

Greedy narrowing of left/right pointers maximizes area. Proof relies on the shorter-wall argument.

l, r = 0, len(h) - 1
best = 0
while l < r:
    area = min(h[l], h[r]) * (r - l)
    best = max(best, area)
    if h[l] < h[r]: l += 1
    else: r -= 1

Fixed-window sliding avoids re-summing by adding the new element and removing the old one.

window = sum(a[:k])
best = window
for i in range(k, len(a)):
    window += a[i] - a[i - k]
    best = max(best, window)

Variable window expands right and shrinks left when the condition is met. Classic pattern.

left = 0
cur_sum = 0
best = float('inf')
for right in range(len(a)):
    cur_sum += a[right]
    while cur_sum >= target:
        best = min(best, right - left + 1)
        cur_sum -= a[left]
        left += 1

Set-based window tracks unique characters. Shrink left when a duplicate enters.

seen = set()
left = 0
best = 0
for right in range(len(s)):
    while s[right] in seen:
        seen.remove(s[left])
        left += 1
    seen.add(s[right])
    best = max(best, right - left + 1)

Counter-based window matching powers minimum-window-substring and anagram problems.

from collections import Counter
need = Counter(t)
have, required = 0, len(need)
left = 0
for right in range(len(s)):
    c = s[right]
    need[c] -= 1
    if need[c] == 0: have += 1
    while have == required:
        # record window [left, right]
        need[s[left]] += 1
        if need[s[left]] > 0: have -= 1
        left += 1

Greedy two-pointer moves the shorter wall inward. O(n) time, O(1) space.

l, r = 0, len(h)-1
mx = 0
while l < r:
    mx = max(mx, min(h[l], h[r]) * (r - l))
    if h[l] < h[r]: l += 1
    else: r -= 1

Two-pointer with running left/right max computes trapped water in O(n).

l, r = 0, len(h)-1
lm = rm = res = 0
while l < r:
    if h[l] < h[r]:
        lm = max(lm, h[l])
        res += lm - h[l]
        l += 1
    else:
        rm = max(rm, h[r])
        res += rm - h[r]
        r -= 1

Sort + fix first + two-pointer on remainder. Skip duplicates at all three levels.

a.sort()
for i in range(len(a)-2):
    if i and a[i] == a[i-1]: continue
    l, r = i+1, len(a)-1
    while l < r:
        s = a[i] + a[l] + a[r]
        if s < 0: l += 1
        elif s > 0: r -= 1
        else:
            res.append([a[i], a[l], a[r]])
            l += 1
            while l < r and a[l] == a[l-1]: l += 1

Write-pointer compaction for sorted arrays. Returns new length.

w = 1
for i in range(1, len(a)):
    if a[i] != a[i-1]:
        a[w] = a[i]
        w += 1
return w

Prefix/suffix product arrays avoid division. O(n) time, O(1) extra space with in-place right pass.

n = len(a)
res = [1] * n
for i in range(1, n): res[i] = res[i-1] * a[i-1]
right = 1
for i in range(n-2, -1, -1):
    right *= a[i+1]
    res[i] *= right

Track farthest reachable and current boundary. Increment jumps when boundary is hit.

jumps = cur_end = farthest = 0
for i in range(len(nums) - 1):
    farthest = max(farthest, i + nums[i])
    if i == cur_end:
        jumps += 1
        cur_end = farthest

Track running surplus and total balance. Reset start when tank goes negative.

total = tank = start = 0
for i in range(len(gas)):
    diff = gas[i] - cost[i]
    total += diff
    tank += diff
    if tank < 0:
        start = i + 1
        tank = 0
return start if total >= 0 else -1

Track low/high range of possible open counts. Wildcard expands the range.

lo = hi = 0
for c in s:
    lo += 1 if c == '(' else -1
    hi += 1 if c != ')' else -1
    if hi < 0: return False
    lo = max(lo, 0)
return lo == 0

Arrays win on access and cache locality. Linked lists win on insert/delete at known positions. Arrays are default choice.

ARRAY vs LINKED LIST TRADEOFFS
──────────────────────────────
                ARRAY       LINKED LIST
Access [i]:     O(1)        O(n)
Search:         O(n)/O(logn) O(n)
Insert front:   O(n)        O(1)
Insert end:     O(1)*       O(1)**
Insert middle:  O(n)        O(1)***
Delete:         O(n)        O(1)***
Memory:         contiguous  scattered + pointer overhead
Cache:          excellent   poor (pointer chasing)

* amortized with dynamic array
** with tail pointer
*** given pointer to position

USE ARRAY when:
  □ Need random access (a[i])
  □ Cache performance matters
  □ Fixed or mostly-append workload
  □ Binary search needed

USE LINKED LIST when:
  □ Frequent insert/delete at arbitrary positions
  □ Need O(1) insert/delete given position
  □ Implementing LRU cache (doubly linked + hash)
  □ Merging sorted lists

Converging: start from both ends, narrow down. Same-direction: fast pointer reads, slow pointer writes. Both are O(n).

TWO POINTERS — CONVERGING vs SAME-DIRECTION
────────────────────────────────────────────
CONVERGING (opposite ends → middle):
  l, r = 0, n - 1
  while l < r:
      if condition: l += 1
      else: r -= 1
  → Sorted array: two sum, 3sum, container with most water
  → Palindrome check
  → Partitioning (Dutch national flag)

SAME-DIRECTION (both move forward):
  slow, fast = 0, 0
  while fast < n:
      if condition:
          a[slow] = a[fast]
          slow += 1
      fast += 1
  → Remove duplicates in-place
  → Move zeros to end
  → Linked list: fast/slow for cycle detection, middle

DECISION:
  Sorted + pair sum?     → converging
  Palindrome?            → converging
  Remove/compact?        → same-direction (read/write)
  Cycle in linked list?  → same-direction (fast/slow)
  Merge two sorted?      → same-direction (one per array)

This framework prevents freezing in interviews. Spend more time understanding and planning, less time debugging.

INTERVIEW PROBLEM-SOLVING FRAMEWORK
────────────────────────────────────
STEP 1: UNDERSTAND (2-3 min)
  □ Restate the problem in your own words
  □ Ask clarifying questions (edge cases, constraints)
  □ Walk through 1-2 examples by hand
  □ Confirm input/output format

STEP 2: PLAN (3-5 min)
  □ Identify pattern (see checklist below)
  □ State approach in plain English
  □ Discuss time/space complexity BEFORE coding
  □ Get interviewer buy-in

STEP 3: CODE (10-15 min)
  □ Write clean, modular code
  □ Use descriptive variable names
  □ Talk while coding

STEP 4: VERIFY (3-5 min)
  □ Trace through your example
  □ Test edge cases: empty, single element, all same
  □ Fix bugs calmly

PATTERN CHECKLIST:
  Sorted array?     → binary search or two pointers
  All subsets/perms? → backtracking
  Optimal value?    → DP or greedy
  Tree/graph?       → DFS or BFS
  Top-k?            → heap
  Stream/window?    → sliding window
  Parentheses?      → stack

Converging two pointers from both ends. The most basic symmetric array operation — used in reverse, palindrome check, etc.

l, r = 0, len(a) - 1
while l < r:
    a[l], a[r] = a[r], a[l]
    l += 1
    r -= 1

Prefix sum gives O(1) range queries after O(n) build. p[r+1] - p[l] = sum(a[l..r]). Off-by-one: p has length n+1.

p = [0] * (len(a) + 1)
for i in range(len(a)):
    p[i+1] = p[i] + a[i]
# range sum [l, r] inclusive:
total = p[r+1] - p[l]

Phase 1: detect cycle with slow/fast. Phase 2: reset slow to head, advance both by 1 — they meet at cycle start.

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return slow  # cycle start