# LeetCode Study Notes (JavaScript) — Solutions + Explanations
These are canonical, interview-ready patterns. I’m using the standard LeetCode JS function
signatures and common node shapes:
- `ListNode { val, next }`
- `TreeNode { val, left, right }`
---
## 1) Add Two Numbers (LC #2)
### Problem
Two non-empty linked lists represent two non-negative integers in **reverse order** (1’s digit
first). Add them and return the sum as a linked list (also reverse order).
### Key idea
Simulate grade-school addition digit-by-digit:
- Keep a `carry`
- Walk both lists until both are done and carry is 0
- Create nodes for each digit of the result
### Time / Space
- Time: `O(max(m, n))`
- Space: `O(max(m, n))` for the output list
### JavaScript Solution
```js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* [Link] = (val===undefined ? 0 : val);
* [Link] = (next===undefined ? null : next);
*}
*/
var addTwoNumbers = function (l1, l2) {
const dummy = new ListNode(0);
let tail = dummy;
let carry = 0;
while (l1 || l2 || carry) {
const v1 = l1 ? [Link] : 0;
const v2 = l2 ? [Link] : 0;
const sum = v1 + v2 + carry;
carry = [Link](sum / 10);
[Link] = new ListNode(sum % 10);
tail = [Link];
if (l1) l1 = [Link];
if (l2) l2 = [Link];
}
return [Link];
};
Why it works
At each step, you compute the exact next digit (sum % 10) and propagate overflow via carry.
Because the list is reversed, you’re naturally adding from least-significant digit to
most-significant digit.
2) Trapping Rain Water (LC #42)
Problem
Given an array of heights, compute how much water can be trapped after raining.
Key idea (Two pointers)
Water above an index is limited by the smaller of max-left and max-right.
Two-pointer trick avoids precomputing arrays:
● Maintain leftMax, rightMax
● Move the pointer on the smaller side because that side’s max is the limiting wall for
trapped water there.
Time / Space
● Time: O(n)
● Space: O(1)
JavaScript Solution
var trap = function (height) {
let left = 0, right = [Link] - 1;
let leftMax = 0, rightMax = 0;
let water = 0;
while (left < right) {
if (height[left] <= height[right]) {
// left side is the bottleneck
if (height[left] >= leftMax) leftMax = height[left];
else water += leftMax - height[left];
left++;
} else {
// right side is the bottleneck
if (height[right] >= rightMax) rightMax = height[right];
else water += rightMax - height[right];
right--;
}
}
return water;
};
Why it works
When height[left] <= height[right], you know there exists a wall on the right at least
as tall as height[left], so the trapped water at left is determined purely by leftMax (the
best left wall seen so far). Symmetric reasoning for the right side.
3) Longest Substring Without Repeating Characters (LC
#3)
Problem
Find the length of the longest substring without repeated characters.
Key idea (Sliding window + last seen index)
Maintain a window [left..right] with unique characters.
When you see a repeated char, jump left to max(left, lastSeen[char] + 1).
Time / Space
● Time: O(n)
● Space: O(min(n, alphabet))
JavaScript Solution
var lengthOfLongestSubstring = function (s) {
const lastSeen = new Map();
let left = 0;
let best = 0;
for (let right = 0; right < [Link]; right++) {
const ch = s[right];
if ([Link](ch)) {
left = [Link](left, [Link](ch) + 1);
}
[Link](ch, right);
best = [Link](best, right - left + 1);
}
return best;
};
Why it works
left only moves forward, never backward. Each character enters and exits the window at most
once → linear time.
4) Validate Binary Search Tree (LC #98)
Problem
Determine if a binary tree is a valid BST.
Key idea (Bounds)
A node must satisfy:
● min < [Link] < max
and those bounds tighten as you traverse:
● left child gets upper bound = current node value
● right child gets lower bound = current node value
Important: use strict inequalities; duplicates invalidate BST in LeetCode’s usual definition.
Time / Space
● Time: O(n)
● Space: O(h) recursion stack (h = tree height)
JavaScript Solution
var isValidBST = function (root) {
function dfs(node, min, max) {
if (!node) return true;
if ([Link] <= min || [Link] >= max) return false;
return dfs([Link], min, [Link]) && dfs([Link], [Link], max);
}
return dfs(root, -Infinity, Infinity);
};
Why it works
This catches “global” violations that local parent-child checks miss (e.g., a node deep in the left
subtree that’s bigger than the root).
5) Same Tree (LC #100)
Problem
Check whether two binary trees are identical (structure + values).
Key idea
Recursive compare:
● both null → true
● one null → false
● values differ → false
● compare left and right subtrees
Time / Space
● Time: O(n) (n = min nodes visited until mismatch)
● Space: O(h) recursion stack
JavaScript Solution
var isSameTree = function (p, q) {
if (!p && !q) return true;
if (!p || !q) return false;
if ([Link] !== [Link]) return false;
return isSameTree([Link], [Link]) && isSameTree([Link], [Link]);
};
6) Unique Binary Search Trees I (LC #96)
Problem
Given n, return the number of structurally unique BSTs storing values 1..n.
Key idea (Catalan DP)
Let dp[k] = number of unique BSTs with k nodes.
Pick root i (1..k):
● left subtree has i-1 nodes
● right subtree has k-i nodes
So:
dp[k] = sum_{i=1..k} dp[i-1] * dp[k-i]
Base: dp[0] = 1 (empty tree counts as one way), dp[1] = 1
Time / Space
● Time: O(n^2)
● Space: O(n)
JavaScript Solution
var numTrees = function (n) {
const dp = Array(n + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let nodes = 2; nodes <= n; nodes++) {
let total = 0;
for (let root = 1; root <= nodes; root++) {
total += dp[root - 1] * dp[nodes - root];
}
dp[nodes] = total;
}
return dp[n];
};
Why it works
BST structure depends only on how many nodes go left vs right, not on the exact values,
because values are ordered.
7) Unique Binary Search Trees II (LC #95)
Problem
Generate all structurally unique BSTs that store values 1..n.
Key idea (Recursive generation + memo)
Use recursion on ranges:
build(lo, hi) returns all BSTs using values in [lo..hi].
Pick each root in [lo..hi]:
● all left trees = build(lo, root-1)
● all right trees = build(root+1, hi)
Combine every pair (L, R) with a new root node.
Memoize by (lo, hi) to avoid recomputation.
Time / Space
● Output size is the Catalan number, so time is proportional to number of trees generated.
● Memo helps a lot; still inherently exponential in output.
JavaScript Solution
var generateTrees = function (n) {
if (n === 0) return [];
const memo = new Map(); // key: "lo,hi" -> array of TreeNode
function build(lo, hi) {
const key = `${lo},${hi}`;
if ([Link](key)) return [Link](key);
const res = [];
if (lo > hi) {
[Link](null);
[Link](key, res);
return res;
}
for (let rootVal = lo; rootVal <= hi; rootVal++) {
const leftTrees = build(lo, rootVal - 1);
const rightTrees = build(rootVal + 1, hi);
for (const L of leftTrees) {
for (const R of rightTrees) {
const root = new TreeNode(rootVal);
[Link] = L;
[Link] = R;
[Link](root);
}
}
}
[Link](key, res);
return res;
}
return build(1, n);
};
Why it works
This is literally the definition of unique BST construction: choose a root, then independently
choose any valid left and right BSTs from the remaining values.
8) Recover Binary Search Tree (LC #99)
Problem
A BST has exactly two nodes swapped by mistake. Restore it without changing structure.
Key idea (In-order traversal detects inversions)
In-order traversal of a BST should be strictly increasing.
If two nodes are swapped, the in-order sequence will have inversions:
● Case A: swapped nodes are adjacent → one inversion
● Case B: swapped nodes are far apart → two inversions
Track:
● prev node visited in-order
● On inversion ([Link] > [Link]):
○ first time: first = prev, second = curr
○ second time: update second = curr
Finally swap [Link] and [Link].
Time / Space
● Time: O(n)
● Space: O(h) recursion stack
JavaScript Solution
var recoverTree = function (root) {
let first = null;
let second = null;
let prev = null;
function inorder(node) {
if (!node) return;
inorder([Link]);
if (prev && [Link] > [Link]) {
if (!first) first = prev;
second = node; // update both on first inversion and again on second
}
prev = node;
inorder([Link]);
}
inorder(root);
// swap the misplaced values
const tmp = [Link];
[Link] = [Link];
[Link] = tmp;
};
Why it works
In-order traversal is the BST truth serum. Swapping two values corrupts the monotonic order in
a predictable way; capturing the endpoints of the inversions identifies the swapped nodes.
Pattern Map (What to memorize)
● Linked list addition → “dummy head + carry”
● Rain water → “two pointers + leftMax/rightMax; move smaller side”
● Longest substring → “sliding window + lastSeen jump”
● Validate BST → “DFS with min/max bounds”
● Same tree → “structural recursion”
● Unique BST count → “Catalan DP: dp[left]*dp[right]”
● Generate BSTs → “range recursion + combine left/right + memo”
● Recover BST → “inorder + detect inversions + swap”
If you want extra practice: I can add a mini “common bugs” section per problem (JS pitfalls,
off-by-one, recursion depth, etc.) and a set of custom test cases to run mentally.