Learning DSA in Public, Week 2: Running Totals, Train Engines and Two Pointers

Last week I started NeetCode 150 with Arrays & Hashing: using sets and dictionaries to remember what I've seen instead of searching again.

This week I finished that section and started Two Pointers. Same rule as before: if I can't explain it with an everyday picture, I don't understand it yet.

The big idea this week: stop starting over. Carry a running total, remember what you've seen, or move two pointers toward each other. Each one turns a slow "check everything again" solution into a single pass.

1. Product of Array Except Self: looking left and right

The problem: For each position, multiply every number except the one at that position. No division allowed.

Picture it: People standing in a line. Each person asks: "What do everyone to my left multiply to? And everyone to my right?" Multiply those two answers and you've got everyone except yourself.

def productExceptSelf(nums): n = len(nums) answer = [1] * n left = 1 for i in range(n): answer[i] = left left *= nums[i] right = 1 for i in range(n - 1, -1, -1): answer[i] *= right right *= nums[i] return answer

Slow vs. fast: Recomputing the product for every position is O(n²). Carrying a running total from each side does it in two passes: O(n).

What I learnt the hard way: I understood the left/right idea but still couldn't turn it into code. What fixed it was writing one plain-English instruction per line ("save the running total, then multiply in the current number") before typing anything. The order of those two lines is the whole trick.

2. Valid Sudoku: one notebook, three labels

The problem: Check that no number repeats in any row, column or 3×3 box of a partly filled board.

Picture it: One notebook. Every number gets written down three times, with labels: "5 in row 0", "5 in column 3", "5 in box (0, 1)". If a label is already in the notebook, the board is invalid.

def isValidSudoku(board): seen = set() for r in range(9): for c in range(9): val = board[r][c] if val == ".": continue row_key = ("row", r, val) col_key = ("col", c, val) box_key = ("box", r // 3, c // 3, val) if row_key in seen or col_key in seen or box_key in seen: return False seen.add(row_key) seen.add(col_key) seen.add(box_key) return True

Why the labels matter: without "row" and "col", a 5 in row 0 and a 5 in column 0 would both be saved as (0, "5"), and a valid board would fail.

Slow vs. fast: One pass over 81 cells. r // 3, c // 3 tells each cell which box it lives in.

3. Longest Consecutive Sequence: find the engine

The problem: In an unsorted list, find the length of the longest run of consecutive numbers (like 2, 3, 4, 5), in O(n).

Picture it: Train cars scattered in a yard. Only start counting when you find an engine, a car with nothing in front of it. Then count the cars hooked behind it.

def longestConsecutive(nums): num_set = set(nums) longest = 0 for n in num_set: if n - 1 not in num_set: length = 1 while n + length in num_set: length += 1 longest = max(longest, length) return longest

Slow vs. fast: Sorting first is O(n log n). Because we only count from engines, each number is visited a small, fixed number of times: O(n).

4. Valid Palindrome: two fingers, moving inward

The problem: Does a string read the same forwards and backwards, ignoring spaces, punctuation and capitals?

Picture it: One finger on the first character, one on the last. Skip anything that isn't a letter or number, compare, then move both fingers in.

def isPalindrome(s): left, right = 0, len(s) - 1 while left < right: while left < right and not s[left].isalnum(): left += 1 while left < right and not s[right].isalnum(): right -= 1 if s[left].lower() != s[right].lower(): return False left += 1 right -= 1 return True

Slow vs. fast: Building a cleaned-up copy and reversing it uses extra memory. Two pointers do it in place: O(n) time, O(1) extra space.

5. Two Sum II (sorted input): too much? too little?

The problem: In a sorted list, find the two numbers that add up to a target (positions start at 1).

Picture it: A shelf sorted from cheapest to most expensive. Point at both ends. Total too high? Move off the expensive end. Too low? Move off the cheap end.

def twoSum(numbers, target): left, right = 0, len(numbers) - 1 while left < right: total = numbers[left] + numbers[right] if total == target: return [left + 1, right + 1] if total < target: left += 1 else: right -= 1

Slow vs. fast: Checking every pair is O(n²). Last week's dictionary version is O(n) but uses extra memory. Because the list is sorted, two pointers get O(n) with no extra memory.

6. 3Sum: lock one, pinch two

The problem: Find every unique set of three numbers that adds up to zero.

Picture it: Sort the list. Lock one number in place, then run Two Sum II on everything to its right to find a pair that cancels it out.

def threeSum(nums): nums.sort() result = [] for i in range(len(nums)): if i > 0 and nums[i] == nums[i - 1]: continue left, right = i + 1, len(nums) - 1 while left < right: total = nums[i] + nums[left] + nums[right] if total < 0: left += 1 elif total > 0: right -= 1 else: result.append([nums[i], nums[left], nums[right]]) left += 1 while left < right and nums[left] == nums[left - 1]: left += 1 return result

The tricky part: duplicates. Skip a locked number if it's the same as the one before, and after finding a match, skip repeated values on the left. Otherwise the same triplet shows up more than once.

Slow vs. fast: Three nested loops is O(n³). Sort, then one loop with two pointers inside: O(n²).

Week 2 cheat sheet

Problem	Pattern	Question it answers
Product Except Self	Running totals from both sides	What's everything to my left, and to my right?
Valid Sudoku	Set with labelled keys	Have I seen this number in this row, column or box?
Longest Consecutive	Set + start check	Is this number the start of a chain?
Valid Palindrome	Two pointers, opposite ends	Do the outside characters match?
Two Sum II	Two pointers on sorted input	Is my total too big or too small?
3Sum	Sort + lock one + two pointers	With one number fixed, which pair cancels it?

What's working for me

Trying before looking. Even a slow, messy attempt makes the real solution make sense.
Plain English first, code second. One instruction per line, including whether it sits inside or outside the loop.
Printing checkpoints. Watching a list fill up after the first loop tells me if I'm on track before I write the rest.