DSA Prep

Data structures & algorithms practice, grouped LeetCode Top Interview 150 style.

Workflow now:

1. Solve the problem on LeetCode (Top Interview 150) first.
2. Immediately cold-redo it here in Python (no peeking).
3. Log it in the table below with its difficulty.
4. Alongside: 1–2 system design per cycle.

Language: older solutions are in TypeScript + Python (kept as-is). New solves are Python-only — no TS requirement anymore.

Difficulty: 🟢 Easy · 🟡 Medium · 🔴 Hard. ✅ = solved + logged. Lang columns show which files exist (✅ present, — not done in that language).

Approach

Each problem worked the way an interview tests it:

1. Restate the problem
2. Talk through the approach — brute force first, then optimize
3. Code it clean, narrating the thinking
4. State time & space complexity
5. Redo cold days later (spaced repetition)

Progress

Arrays & Hashing

Problem	Diff	TS	Py	Pattern	Time	Space
Two Sum	🟢	✅	✅	Hash map (value → index)	O(n)	O(n)
Contains Duplicate	🟢	✅	✅	Set membership	O(n)	O(n)
Valid Anagram	🟢	✅	✅	Char-count map	O(n)	O(1)
Group Anagrams	🟡	✅	✅	Canonical-key bucketing (sorted / count)	O(n·k)	O(n·k)
Top K Frequent	🟡	✅	✅	Count map + sort/bucket by frequency	O(n log n)	O(n)
Product of Array Except Self	🟡	✅	✅	Prefix × suffix products (no division)	O(n)	O(1) extra
Merge Sorted Array	🟢	—	✅	Two pointers from the back, write in place	O(m+n)	O(1)
Remove Element	🟢	—	✅	Two pointers, swap val at L with non-val from R	O(n)	O(1)
Remove Duplicates from Sorted Array	🟢	—	✅	Two pointers, write pointer L lags read pointer R	O(n)	O(1)
Remove Duplicates from Sorted Array II	🟡	—	✅	Same two pointers, keep if nums[R] != nums[L-2] (generalizes to at-most-k)	O(n)	O(1)
Majority Element	🟢	—	✅	Boyer-Moore voting; candidate + count, flip when count hits 0	O(n)	O(1)
Rotate Array	🟡	—	✅	Triple reverse: whole, first k, rest (k %= n first)	O(n)	O(1)
Best Time to Buy/Sell Stock	🟢	—	✅	LC 150 redo of the dsa/ solve — running min, best profit selling today	O(n)	O(1)

Two Pointers

Problem	Diff	TS	Py	Pattern	Time	Space
Valid Palindrome	🟢	✅	✅	Two pointers, skip non-alnum on the fly	O(n)	O(1)
Two Sum II (sorted)	🟡	✅	✅	Two pointers converge on target	O(n)	O(1)
3Sum	🟡	✅	✅	Sort + fix one + two-pointer inner + dedup	O(n²)	O(1)
Container With Most Water	🟡	✅	✅	Two pointers, move the shorter wall (greedy)	O(n)	O(1)

Sliding Window

Problem	Diff	TS	Py	Pattern	Time	Space
Best Time to Buy/Sell Stock	🟢	✅	✅	Track min-so-far, best profit selling today	O(n)	O(1)
Longest Substring Without Repeating	🟡	✅	✅	Window + set; shrink L on repeat	O(n)	O(min(n,charset))
Longest Repeating Character Replacement	🟡	✅	✅	Window valid if windowLen − maxFreq ≤ k	O(n)	O(26)
Minimum Window Substring	🔴	✅	✅	Variable window; need/have counter; grow to valid, shrink to min	O(s+t)	O(t)

Stack

Problem	Diff	TS	Py	Pattern	Time	Space
Valid Parentheses	🟢	✅	✅	Stack (LIFO); map closer→opener, pop & match	O(n)	O(n)
Min Stack	🟡	✅	✅	Parallel min-stack; push min-so-far, pop together	O(1) all ops	O(n)
Evaluate RPN	🟡	✅	✅	Stack; push nums, operator pops 2 & pushes result	O(n)	O(n)
Daily Temperatures	🟡	✅	✅	Monotonic stack of indices; pop when warmer, gap = i−idx	O(n)	O(n)
Car Fleet	🟡	✅	✅	Sort by pos desc; stack of arrival times; new fleet if time > top	O(n log n)	O(n)
Largest Rectangle in Histogram	🔴	✅	✅	Monotonic stack; width = i−stack[-1]−1, drain with n	O(n)	O(n)

Trees

Solved in Python under toptal_drill/ (see below). Re-log here as they get cold-redone.

Problem	Diff	TS	Py	Pattern	Time	Space
Maximum Depth of Binary Tree	🟢	—	✅	DFS, max(left,right)+1	O(n)	O(h)
Diameter of Binary Tree	🟡	—	✅	DFS returns height, track best	O(n)	O(h)
Level Order Traversal	🟡	—	✅	BFS + deque, row-size snapshot	O(n)	O(n)
Vertical Order Traversal	🔴	—	✅	BFS + (node, col) pairs + column map	O(n log n)	O(n)

Fundamentals / Warmups

Classic phone-screen warmups (not LC 150, but frequently asked).

Problem	TS	Py	Pattern	Time	Space
Fibonacci	✅	✅	Iterative — series (array) + nth value (two-var slide)	O(n)	O(n) series / O(1) value
Prime Check	✅	✅	Trial division to √n (i*i <= n)	O(√n)	O(1)
Factorial	✅	✅	Recursive (base + shrink) + iterative	O(n)	O(n) rec / O(1) iter
Sorting	✅	✅	Built-in (asc/desc, array + string) + manual bubble	O(n log n) built-in / O(n²) bubble	O(1)
Reverse	✅	✅	Two-pointer swap ends inward (string + array)	O(n)	O(1)
FizzBuzz	✅	✅	Modulo, most-specific-first (%15 before %3/%5)	O(n)	O(n)
Digits (sum + count)	✅	✅	Peel digits with % 10 + // 10, no string	O(d)	O(1)
Palindrome Number	✅	✅	Reverse int via math (rev*10+digit), compare	O(d)	O(1)
Max / Min in Array	✅	✅	Single pass, seed from nums[0] (not 0)	O(n)	O(1)
GCD / LCM	✅	✅	Euclid: gcd(a,b)=gcd(b,a%b); lcm=a*b/gcd	O(log min(a,b))	O(1)

System Design

Co-equal track — 1–2 designs per cycle, laddered easy→hard. Format is reasoning + tradeoffs + ASCII diagrams (not code), each exported to PDF. Core drill: defend every choice against the obvious alternative. Terms surfaced go in VOCAB_MAP.md.

Design	Doc	PDF	Focus
URL Shortener	✅	✅	Read-heavy, 302 vs 301, base62 codes, cache-aside, async counter, hot-key

Backlog: Rate Limiter · Pastebin/Image Host · Web Crawler · Chat/Messaging · News Feed · Video Streaming · Ticketing (concurrency) · RAG/LLM Serving. Plus LLD: Elevator, Parking Lot.

Extra Python drills — toptal_drill/

Timed cold-redos from an earlier sprint, kept as extra reps (Python only). Not part of the LC 150 tables above; folded in as they get re-logged.

Invalid Transactions · Subarray Sum Equals K · Isomorphic Strings · Accounts Merge · Zero Array Transformation II · Continuous Subarrays · Maximum Sum Circular Subarray · Reorganize String · Number of Distinct Islands · Check If N and Its Double Exist · Find K Pairs with Smallest Sums · Combination Sum II · Number of Islands · heapq basics · Difference Array · Monotonic Deque.

Structure

New solves: one Python file per problem, grouped by topic. Tests live in a if __name__ == "__main__" block at the bottom.

leetcode/                 # new solves (Python only)
  <topic>/
    <problem_name>.py     # solution + inline test cases

dsa/                      # older NeetCode-style solves (.ts + .py)
  <problem_name>/
    <problem_name>.py
    <problem_name>.ts

system_design/
  <design_name>/
    design.md             # reasoning, tradeoffs, ASCII diagrams
    <design_name>.pdf     # exported PDF

Running

# New solves
python3 leetcode/arrays_hashing/merge_sorted_array.py

# Older solutions
python3 dsa/two_sum/two_sum.py
npx tsx dsa/two_sum/two_sum.ts