NeetCode150

Solutions for NeetCode 150 problems, solved in multiple languages (Java, Python, C++, Javascript, Go Rust, C). Detailed lessons about the topics, techniques and algorithms are included. The repo covers also SQL, Databases, Storage internal data structures and Business logic mocks.

Lessons

To pick a technique for a new problem, start with pattern recognition. It maps problem signals to the lessons below.

Foundations

Complexity analysis: Big-O, the common complexity classes, and how to analyse your own solutions.
Pattern recognition: which technique a problem wants, from its constraints and wording.
P, NP, NP-hard and NP-complete: the complexity classes, reductions, and pseudo-polynomial algorithms.

Data structures

Hashing: hash maps and sets, collisions, load factor, and the ordered versions.
Array and hashing problems: Product Except Self, Longest Consecutive Sequence, length-prefixed encoding, the Sudoku box index, anagram keys, and four ways to find the top K.
Prefix sums: range sums with one subtraction, Subarray Sum Equals K with a hash map, prefix products, and 2D prefix sums.
Stacks: LIFO, matching brackets, undo, and deferred evaluation.
Monotonic stack: nearest greater or smaller element in one pass; Daily Temperatures, Largest Rectangle, Trapping Rain Water, Car Fleet and Max Chunks.
Queues and deques: FIFO, BFS queues, and deques.
Heaps and priority queues: binary heaps, top-K, two-heap medians, and lazy deletion.
Heap problems: a heap kept at size k, Last Stone Weight, Task Scheduler with its formula, two heaps for the median, and merging feeds in Design Twitter.
Tries: prefix trees for word and prefix lookups.
Trie problems: Implement Trie, wildcard search that branches at each ., and Word Search II with one grid search pruned by the trie.

Two pointers

Two pointers from opposite ends: why moving one pointer is safe; Two Sum II, Container With Most Water, 3Sum and Trapping Rain Water.
Two pointers in the same direction: read/write pointers for in-place filtering, and merging from the back.

Sliding window

Fixed-size sliding windows: add one element, remove one, and track letter counts with a match counter.
Variable-size sliding windows: longest vs shortest windows, why the cost is O(n), and when a window does not work.
Sliding window maximum: the monotonic deque, traced step by step.

Sorting and searching

Sorting: the comparison-sort lower bound, stability, counting and radix sort, and quickselect.
Bucket sort: sorting by using the key as an index, as in Top K Frequent Elements.
Binary search: monotonic predicates, boundary searches, floor vs. ceiling, binary search on the answer, and rotated arrays.

Linked lists

Linked list basics: nodes, the dummy head, why removal needs the previous node, Remove Nth From End and Merge Two Sorted Lists.
Reversing a linked list: the three-pointer loop drawn step by step, the recursive version, and Reverse Nodes in k-Group.
Reordering and merging lists: Reorder List, Add Two Numbers, and three ways to Merge k Sorted Lists.
Copy list and LRU cache: Copy List with Random Pointer with a map or by weaving, and the LRU cache's map plus doubly linked list.
Floyd's cycle detection: finding a cycle and its entrance in O(1) space, on lists, arrays and number sequences.

Trees

Tree basics and traversals: terms, height in nodes or edges, iterative DFS with a stack, BFS by level, and Right Side View.
Recursion on trees: passing information down or up, a special return value for Balanced Tree, and Diameter and Max Path Sum.
Binary search trees: the ordering rule, Validate BST with bounds, Kth Smallest by inorder, and LCA in a BST.
Building and serialising trees: rebuilding from preorder and inorder, and preorder with null markers.

Backtracking

Backtracking basics: choose, explore, undo; the decision tree drawn two ways for Subsets; why paths are copied; and the cost.
Combinations, permutations and duplicates: reuse with i vs i + 1, skipping equal values in Subsets II and Combination Sum II, and permutations by swapping.
Backtracking with constraints: pruning in Generate Parentheses, N-Queens diagonals, Word Search marking, and Palindrome Partitioning.

Greedy

Greedy and how to prove it: the exchange argument and greedy-stays-ahead, with counterexamples that break wrong greedy rules.
Greedy problems: Kadane, Jump Game I and II, Gas Station, Hand of Straights, Merge Triplets, Partition Labels and Valid Parenthesis String, each proved and traced.

Intervals

Overlap, merging and inserting: the overlap test, touching intervals, Merge Intervals, Insert Interval in one pass, and Meeting Rooms.
Scheduling, rooms and queries: Non-overlapping Intervals, Meeting Rooms II with a heap or a sweep, and offline queries with lazy deletion.

Graphs

Graphs, BFS and DFS: representations, traversals, grids, and connected components.
Topological sort: ordering a DAG with Kahn's algorithm or DFS post-order, and directed cycle detection.
Union-Find: disjoint sets with path compression and union by size, for connectivity and undirected cycles.
Dijkstra: single-source shortest paths with non-negative weights, and its variants.
Bellman-Ford: shortest paths with negative weights, negative cycles, and paths with at most k edges.
Minimum spanning tree: Prim and Kruskal, and how an MST differs from shortest paths.
Eulerian paths and Hierholzer's algorithm: using every edge exactly once.

Dynamic programming

Dynamic programming: memoization, tabulation, and the common state shapes.
1D vs 2D DP: how many dimensions the table needs, and how to shrink it.
Knapsack: 0/1 and unbounded, counting and min/max variants, and disguised knapsacks.
String DP: two-sequence tables for LCS, Edit Distance, Distinct Subsequences, Interleaving String and Regex Matching.
Interval DP: answers for every range [i, j], filled by length; shrink-the-ends and split-point recurrences.

Bit manipulation

Integer representation: bit positions, two's complement, and integer type limits in each language.
Overflow: what each language does on overflow, negating the smallest value, and division of negative numbers.
Operators and shifts: & | ^ ~, logical and arithmetic shifts, oversized shifts, and precedence.
Masking: single-bit and multi-bit masks, 32-bit masking in Python, and an integer as a set.
Bit tricks: XOR cancellation, x & (x - 1), x & -x, and step-by-step walkthroughs of the bit problems.

Math and geometry

Math and geometry: matrix rotation, overflow, modular arithmetic, and other non-structural problems.
Integer formulas: splitting a count in halves, ceiling division, an overflow-free midpoint, flattening a grid index, counting formulas, and the k-largest heap rule.
Number theory: Euclid's GCD and why it works, LCM without overflow, modular arithmetic and the modular inverse, fast exponentiation, and primes.

Databases

SQL basics: the example schema, filtering and sorting, undefined order on ties, NULL and three-valued logic, and the order clauses are evaluated in.
Joins: inner, outer and self-joins, conditions in ON vs WHERE, anti-joins and the NOT IN trap, and joins that inflate totals.
Grouping and aggregates: GROUP BY, aggregates and NULL, count(*) after a left join, WHERE vs HAVING, and FILTER.
Subqueries, CTEs and set operations: scalar and correlated subqueries, EXISTS, derived tables, CTE inlining, recursive CTEs, and UNION/EXCEPT.
Window functions: aggregates next to each row, ranking and top N per group, running totals, lag and lead, and frames.
Views and virtual tables: views, updatable views and CHECK OPTION, materialized views, temporary tables, VALUES, generate_series and LATERAL.
Changing data and transactions: INSERT/UPDATE/DELETE with RETURNING, upserts, constraints, transactions and savepoints, isolation levels and lost updates.
Triggers: BEFORE, AFTER and INSTEAD OF, row and statement level, audit logs, derived counters, recursion, and simpler alternatives.
SQL query planning and indexes: how a query becomes an execution plan, and how indexes change it.