NeetCode 150 · revision

Revision cards: all 150 in one page

One card per problem: the key idea, the difficulty and the solution one tap away. Try to recall the approach before you open the code. Filter to what you have not solved yet, or to the problems you flagged for review.

Arrays & Hashing ·

  • LeetCode 217Easy

    Contains Duplicate

    A set answers “have I seen this before?” in one step, so one pass over the list is enough: O(n) time instead of comparing every pair.

    Show the Python solution
    def contains_duplicate(nums):
        album = set()
        for x in nums:
            if x in album:
                return True
            album.add(x)
        return False
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 242Easy

    Valid Anagram

    Count letters with a dictionary (add for one word, subtract for the other). Equal counts mean an anagram, with no sorting needed.

    Show the Python solution
    def is_anagram(s, t):
        if len(s) != len(t):
            return False
        count = Counter()
        for ch in s:
            count[ch] += 1
        for ch in t:
            count[ch] -= 1
            if count[ch] < 0:
                return False
        return True
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 1Easy

    Two Sum

    For each number x, the partner you need is target − x. Store what you have seen in a dictionary and look the partner up in O(1).

    Show the Python solution
    def two_sum(nums, target):
        seen = {}  # coat rack: number -> ticket
        for i, x in enumerate(nums):
            need = target - x
            if need in seen:
                return [seen[need], i]
            seen[x] = i
        return []
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 49Medium

    Group Anagrams

    Give every word a “signature” that all its anagrams share (its sorted letters) and use it as a dictionary key.

    Show the Python solution
    def group_anagrams(words):
        jars = defaultdict(list)
        for w in words:
            key = "".join(sorted(w))     # same letters, same key
            jars[key].append(w)
        return list(jars.values())
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 347Medium

    Top K Frequent Elements

    Count with a dictionary, then use “bucket by count”: no full sort needed, so it runs in O(n).

    Show the Python solution
    def top_k_frequent(nums, k):
        count = Counter(nums)
        heap = []                     # (visits, value), fewest on top
        for x, c in count.items():
            heappush(heap, (c, x))
            if len(heap) > k:
                heappop(heap)
        return [x for c, x in heap]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 271Medium

    Encode and Decode Strings

    Prefix each word with its length and a marker. Decoding reads the length first, so any character is safe inside the words.

    Show the Python solution
    def encode(words):
        return "".join(f"{len(w)}#{w}" for w in words)
    
    def decode(tape):
        out, i = [], 0
        while i < len(tape):
            j = tape.index("#", i)      # length ends at the first #
            n = int(tape[i:j])
            out.append(tape[j + 1:j + 1 + n])
            i = j + 1 + n
        return out
    ▶ AnimationSolve on LeetCode ↗ (LeetCode Premium; free on NeetCode ↗)
  • LeetCode 238Medium

    Product of Array Except Self

    Answer[i] = prefix product before i × suffix product after i. Two passes, no division, O(n) time.

    Show the Python solution
    def product_except_self(nums):
        n = len(nums)
        out = [1] * n
        left = 1
        for i in range(n):
            out[i] = left              # product of everything on the left
            left *= nums[i]
        right = 1
        for i in range(n - 1, -1, -1):
            out[i] *= right            # times everything on the right
            right *= nums[i]
        return out
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 36Medium

    Valid Sudoku

    Each cell belongs to exactly one row, one column and one box (box = (row//3, col//3)). Three families of sets catch every repeat in one pass.

    Show the Python solution
    def is_valid_sudoku(board):
        rows, cols, boxes = defaultdict(set), defaultdict(set), defaultdict(set)
        for r in range(9):
            for c in range(9):
                v = board[r][c]
                if v == ".":
                    continue
                b = (r // 3, c // 3)
                if v in rows[r] or v in cols[c] or v in boxes[b]:
                    return False
                rows[r].add(v); cols[c].add(v); boxes[b].add(v)
        return True
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 128Medium

    Longest Consecutive Sequence

    Put everything in a set. Only start counting from numbers whose (x − 1) is missing. Each number is visited a constant number of times: O(n).

    Show the Python solution
    def longest_consecutive(nums):
        s = set(nums)
        best = 0
        for x in s:
            if x - 1 not in s:          # x starts a run
                length = 1
                while x + length in s:
                    length += 1
                best = max(best, length)
        return best
    ▶ AnimationSolve on LeetCode ↗

Two Pointers ·

  • LeetCode 125Easy

    Valid Palindrome

    Two pointers from both ends, skipping non-letters, compare as you go: O(n) time, no extra copy of the string.

    Show the Python solution
    def is_palindrome(s):
        l, r = 0, len(s) - 1
        while l < r:
            if not s[l].isalnum():
                l += 1
            elif not s[r].isalnum():
                r -= 1
            elif s[l].lower() != s[r].lower():
                return False
            else:
                l, r = l + 1, r - 1
        return True
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 167Medium

    Two Sum II

    Sorted input lets two pointers squeeze inward: sum too big → move right pointer left, too small → move left pointer right. O(n).

    Show the Python solution
    def two_sum(nums, target):
        l, r = 0, len(nums) - 1
        while l < r:
            s = nums[l] + nums[r]
            if s == target:
                return [l + 1, r + 1]  # 1-based
            if s < target:
                l += 1
            else:
                r -= 1
        return []
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 15Medium

    3Sum

    Sort, fix one number, then solve Two Sum II on the rest with two pointers. Skip equal neighbours to avoid duplicates. O(n²).

    Show the Python solution
    def three_sum(nums):
        a = sorted(nums)
        res = []
        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]])
                    while l < r and a[l] == a[l+1]:
                        l += 1
                    l, r = l + 1, r - 1
        return res
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 11Medium

    Container With Most Water

    Area = min(h[l], h[r]) × (r − l). Always move the shorter side inward; you never skip a better pair. O(n).

    Show the Python solution
    def max_area(h):
        l, r, best = 0, len(h) - 1, 0
        while l < r:
            best = max(best, (r - l) * min(h[l], h[r]))
            if h[l] < h[r]:
                l += 1
            else:
                r -= 1
        return best
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 42Hard

    Trapping Rain Water

    Water at i = min(maxLeft, maxRight) − height[i]. Two pointers know which side is the limit, so one pass with O(1) memory.

    Show the Python solution
    def trap(h):
        l, r = 0, len(h) - 1
        left_max = right_max = water = 0
        while l < r:
            if h[l] < h[r]:
                left_max = max(left_max, h[l])
                water += left_max - h[l]
                l += 1
            else:
                right_max = max(right_max, h[r])
                water += right_max - h[r]
                r -= 1
        return water
    ▶ AnimationSolve on LeetCode ↗

Sliding Window ·

  • LeetCode 121Easy

    Best Time to Buy and Sell Stock

    Track the minimum price so far and the best (today − minimum). One pass, O(n).

    Show the Python solution
    def max_profit(prices):
        if not prices: return 0      # no days
        cheapest, best = prices[0], 0
        for p in prices[1:]:    # sell or rebuy?
            best = max(best, p - cheapest)
            cheapest = min(cheapest, p)
        return best
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 3Medium

    Longest Substring Without Repeating Characters

    Sliding window + “last seen position” dictionary: when a repeat appears, jump the left edge past the old copy. O(n).

    Show the Python solution
    def longest_unique(s):
        last = {}                 # letter -> last position
        left = best = 0
        for right, ch in enumerate(s):
            if ch in last and last[ch] >= left:
                left = last[ch] + 1
            last[ch] = right
            best = max(best, right - left + 1)
        return best
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 424Medium

    Longest Repeating Character Replacement

    A window is fine while (length − count of its most frequent letter) ≤ k. Grow right, shrink left when it breaks. O(n).

    Show the Python solution
    def character_replacement(s, k):
        count, left, top, best = Counter(), 0, 0, 0
        for right, ch in enumerate(s):
            count[ch] += 1
            top = max(top, count[ch])         # most common colour in window
            while (right - left + 1) - top > k:  # too many planks to repaint
                count[s[left]] -= 1
                left += 1
            best = max(best, right - left + 1)
        return best
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 567Medium

    Permutation in String

    Fixed-size window with letter counts. Slide by adding one letter and removing one; compare counts. O(n).

    Show the Python solution
    def check_inclusion(s1, s2):
        m = len(s1)
        need, win = Counter(s1), Counter(s2[:m])
        for i in range(m, len(s2)):
            if win == need:
                return True
            win[s2[i]] += 1             # letter enters
            win[s2[i - m]] -= 1         # letter leaves
        return win == need
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 76Hard

    Minimum Window Substring

    Expand right until the window is valid, then shrink left while it stays valid, tracking the smallest. A “have vs need” counter makes each check O(1). Each character of s enters and leaves the window at most once, so the whole thing is O(m + n) for m = len(s), n = len(t).

    Show the Python solution
    def min_window(s, t):
        need, have = Counter(t), Counter()
        missing = len(t)
        best, left = "", 0
        for right, ch in enumerate(s):
            if have[ch] < need[ch]:
                missing -= 1
            have[ch] += 1
            while missing == 0:   # net has all
                size = right - left + 1
                if not best or size < len(best):
                    best = s[left:right + 1]
                have[s[left]] -= 1
                if have[s[left]] < need[s[left]]:
                    missing += 1
                left += 1
        return best
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 239Hard

    Sliding Window Maximum

    A deque kept in decreasing order: the front is always the maximum. Each tower is added and removed at most once: O(n).

    Show the Python solution
    def max_window(h, k):
        dq, out = deque(), []      # positions, tallest at front
        for i, x in enumerate(h):
            while dq and h[dq[-1]] <= x:
                dq.pop()
            dq.append(i)
            if dq[0] <= i - k:
                dq.popleft()
            if i >= k - 1:
                out.append(h[dq[0]])
        return out
    ▶ AnimationSolve on LeetCode ↗

Stack ·

  • LeetCode 20Easy

    Valid Parentheses

    Last opened must be first closed, which is exactly what a stack (last in, first out) gives you. O(n).

    Show the Python solution
    def is_valid(s):
        pairs = {")": "(", "]": "[", "}": "{"}
        stack = []
        for ch in s:
            if ch not in pairs:
                stack.append(ch)
            elif not stack or stack.pop() != pairs[ch]:
                return False
        return not stack
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 155Medium

    Min Stack

    Store (value, minimum so far) with every entry. The top entry always knows the current minimum: every operation is O(1).

    Show the Python solution
    class MinStack:
        def __init__(self):
            self.stack = []                # (value, min so far)
        def push(self, x):
            low = min(x, self.stack[-1][1]) if self.stack else x
            self.stack.append((x, low))
        def pop(self):
            self.stack.pop()
        def top(self):
            return self.stack[-1][0]
        def get_min(self):
            return self.stack[-1][1]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 150Medium

    Evaluate Reverse Polish Notation

    Numbers push; operators pop two, compute, push the result. One pass with a stack, O(n).

    Show the Python solution
    OPS = {"+": add, "-": sub, "*": mul, "/": lambda a, b: int(a / b)}
    def eval_rpn(tokens):
        stack = []
        for t in tokens:
            if t in OPS:
                b = stack.pop()
                a = stack.pop()
                stack.append(OPS[t](a, b))
            else:
                stack.append(int(t))
        return stack[0]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 22Medium

    Generate Parentheses

    Backtracking with two counts (open used, close used). Only add “)” when close < open, so every result is valid by construction.

    Show the Python solution
    def generate(n):
        out = []
        def build(s, opened, closed):
            if len(s) == 2 * n:
                out.append(s)
                return
            if opened < n:
                build(s + "(", opened + 1, closed)
            if closed < opened:
                build(s + ")", opened, closed + 1)
        build("", 0, 0)
        return out
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 739Medium

    Daily Temperatures

    A “monotonic stack” keeps waiting days in decreasing temperature. Each day is pushed and popped once: O(n).

    Show the Python solution
    def daily_temperatures(temps):
        wait = [0] * len(temps)
        stack = []                      # days still waiting, coolest on top
        for i, t in enumerate(temps):
            while stack and temps[stack[-1]] < t:
                j = stack.pop()
                wait[j] = i - j          # day j finally got warmer
            stack.append(i)
        return wait
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 853Medium

    Car Fleet

    Sort by position (closest to the finish first) and compare arrival times; a new fleet starts only when a car is slower to arrive than the fleet ahead.

    Show the Python solution
    def car_fleet(target, position, speed):
        cars = sorted(zip(position, speed), reverse=True)  # front first
        fleets = []                    # arrival time of each fleet
        for pos, spd in cars:
            t = (target - pos) / spd
            if not fleets or t > fleets[-1]:
                fleets.append(t)       # too slow to catch up: new fleet
            # else: catches the fleet ahead and joins it
        return len(fleets)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 84Hard

    Largest Rectangle in Histogram

    Monotonic increasing stack: when a bar is popped, the current index is its right limit and the new stack top is its left limit. O(n).

    Show the Python solution
    def largest_rectangle(h):
        stack, best = [], 0          # positions with rising heights
        for i, x in enumerate(h + [0]):
            while stack and h[stack[-1]] >= x:
                height = h[stack.pop()]
                left = stack[-1] + 1 if stack else 0
                best = max(best, height * (i - left))
            stack.append(i)
        return best
    ▶ AnimationSolve on LeetCode ↗

Linked List ·

  • LeetCode 206Easy

    Reverse Linked List

    Remember next, point curr back at prev, then move both forward. O(n) time, O(1) extra space.

    Show the Python solution
    def reverse(head):
        prev, curr = None, head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 21Easy

    Merge Two Sorted Lists

    Always take the smaller front node; a dummy head avoids special cases. O(m + n).

    Show the Python solution
    def merge(a, b):
        dummy = tail = Node(0)
        while a and b:
            if a.val <= b.val:
                tail.next, a = a, a.next
            else:
                tail.next, b = b, b.next
            tail = tail.next
        tail.next = a or b
        return dummy.next
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 143Medium

    Reorder List

    Find the middle, reverse the second half, merge alternately. O(n) time, O(1) space.

    Show the Python solution
    def reorder_list(head):
        slow = fast = head
        while fast.next and fast.next.next:     # 1. find the middle
            slow, fast = slow.next, fast.next.next
        prev, curr = None, slow.next          # 2. reverse the back half
        slow.next = None
        while curr:
            curr.next, prev, curr = prev, curr, curr.next
        a, b = head, prev                     # 3. zip the halves
        while b:
            a.next, a = b, a.next
            b.next, b = a, b.next
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 19Medium

    Remove Nth Node From End of List

    Keep a gap of n between two pointers; when the leader reaches the end, the follower is just before the target. One pass.

    Show the Python solution
    def remove_nth(head, n):
        dummy = Node(0, head)
        fast = slow = dummy
        for _ in range(n + 1):
            fast = fast.next
        while fast:
            fast, slow = fast.next, slow.next
        slow.next = slow.next.next
        return dummy.next
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 138Medium

    Copy List with Random Pointer

    A dictionary from old node to new node lets you wire every pointer in a second pass. O(n).

    Show the Python solution
    def copy_random(head):
        clone = {None: None}
        node = head
        while node:
            clone[node] = Node(node.val)
            node = node.next
        node = head
        while node:
            clone[node].next = clone[node.next]
            clone[node].random = clone[node.random]
            node = node.next
        return clone[head]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 2Medium

    Add Two Numbers

    Column addition walking both lists at once, carrying as you go. O(max(m, n)).

    Show the Python solution
    def add(l1, l2):            # digits stored backwards
        dummy = tail = Node(0)
        carry = 0
        while l1 or l2 or carry:
            s = carry + (l1.val if l1 else 0) + (l2.val if l2 else 0)
            carry, digit = divmod(s, 10)
            tail.next = Node(digit)
            tail = tail.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 141Easy

    Linked List Cycle

    Floyd’s fast/slow pointers: they meet if and only if there is a cycle. O(n) time, O(1) space.

    Show the Python solution
    def has_cycle(head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 287Medium

    Find the Duplicate Number

    Treat values as “next” pointers; the duplicate is the start of a cycle. Floyd’s algorithm finds it in O(n) time, O(1) space.

    Show the Python solution
    def find_duplicate(nums):            # box i holds a note: "go to box nums[i]"
        slow = fast = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        slow = 0
        while slow != fast:
            slow, fast = nums[slow], nums[fast]
        return slow                         # two notes point here: the duplicate
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 146Medium

    LRU Cache

    Hash map for O(1) lookup + doubly linked list for O(1) reordering and eviction.

    Show the Python solution
    class LRUCache:
        def __init__(self, capacity):
            self.cap, self.data = capacity, OrderedDict()   # oldest first
        def get(self, key):
            if key not in self.data:
                return -1
            self.data.move_to_end(key)           # just used: now newest
            return self.data[key]
        def put(self, key, value):
            self.data[key] = value
            self.data.move_to_end(key)
            if len(self.data) > self.cap:
                self.data.popitem(last=False)    # evict the oldest
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 23Hard

    Merge k Sorted Lists

    A min-heap of the k front nodes gives the next smallest in O(log k): total O(N log k).

    Show the Python solution
    def merge_k(lists):
        heap = [(l.val, i, l) for i, l in enumerate(lists) if l]
        heapify(heap)
        dummy = tail = Node(0)
        while heap:
            val, i, node = heappop(heap)
            tail.next = node
            tail = node
            if node.next:
                heappush(heap, (node.next.val, i, node.next))
        return dummy.next
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 25Hard

    Reverse Nodes in k-Group

    Count k ahead, reverse that segment in place, stitch it back, repeat. O(n) time, O(1) space.

    Show the Python solution
    def reverse_k(head, k):
        dummy = group_prev = Node(0, head)
        while True:
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next
            nxt = kth.next
            prev, curr = nxt, group_prev.next
            while curr is not nxt:
                curr.next, prev, curr = prev, curr, curr.next
            first = group_prev.next
            group_prev.next = kth
            group_prev = first
    ▶ AnimationSolve on LeetCode ↗

Trees ·

  • LeetCode 226Easy

    Invert Binary Tree

    Recursion: invert the left subtree, invert the right subtree, swap them. Every node is visited once: O(n).

    Show the Python solution
    def invert_tree(node):
        if not node:
            return None
        invert_tree(node.left)
        invert_tree(node.right)
        node.left, node.right = node.right, node.left   # swing the two arms
        return node
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 104Easy

    Maximum Depth of Binary Tree

    depth(node) = 1 + max(depth(left), depth(right)). O(n).

    Show the Python solution
    def max_depth(node):
        if not node:
            return 0
        left = max_depth(node.left)
        right = max_depth(node.right)
        return 1 + max(left, right)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 543Easy

    Diameter of Binary Tree

    One DFS returning height; at each node update best = max(best, leftHeight + rightHeight). O(n).

    Show the Python solution
    def diameter(root):
        best = 0
        def depth(node):
            nonlocal best
            if not node:
                return 0
            l, r = depth(node.left), depth(node.right)
            best = max(best, l + r)          # path that bends at this node
            return 1 + max(l, r)
        depth(root)
        return best
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 110Easy

    Balanced Binary Tree

    Compute heights bottom-up and return −1 as soon as a node is unbalanced. One pass, O(n).

    Show the Python solution
    def is_balanced(root):
        def height(node):
            if not node:
                return 0
            l = height(node.left)
            r = height(node.right)
            if l < 0 or r < 0 or abs(l - r) > 1:
                return -1                  # unbalanced below
            return 1 + max(l, r)
        return height(root) >= 0
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 100Easy

    Same Tree

    Recursive lockstep walk: same(p, q) = values equal and same(left, left) and same(right, right). O(n).

    Show the Python solution
    def is_same(p, q):
        if not p and not q:
            return True
        if not p or not q or p.val != q.val:
            return False
        return is_same(p.left, q.left) and is_same(p.right, q.right)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 572Easy

    Subtree of Another Tree

    For every node in the big tree, run isSameTree against the small tree. O(m × n) in the worst case.

    Show the Python solution
    def is_subtree(root, sub):
        if not root:
            return False
        if is_same(root, sub):  # stencil fits?
            return True
        return (is_subtree(root.left, sub) or
                is_subtree(root.right, sub))
    
    def is_same(a, b):
        if not a or not b:
            return a is b          # both empty?
        return (a.val == b.val
                and is_same(a.left, b.left)
                and is_same(a.right, b.right))
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 235Medium

    Lowest Common Ancestor of a Binary Search Tree

    Use the BST ordering: walk down while p and q are on the same side. O(height).

    Show the Python solution
    def lca(root, p, q):
        node = root
        while node:
            if p < node.val and q < node.val:
                node = node.left          # both are smaller: go left
            elif p > node.val and q > node.val:
                node = node.right         # both are bigger: go right
            else:
                return node               # they split here
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 102Medium

    Binary Tree Level Order Traversal

    Breadth-first search with a queue, processing one level (queue length) at a time. O(n).

    Show the Python solution
    def level_order(root):
        if not root:
            return []
        q, out = deque([root]), []
        while q:
            level = []
            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            out.append(level)
        return out
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 199Medium

    Binary Tree Right Side View

    BFS by levels and keep the last value of each level. O(n).

    Show the Python solution
    def right_side_view(root):
        view, q = [], deque([root] if root else [])
        while q:
            view.append(q[-1].val)          # last in the row is visible
            for _ in range(len(q)):
                node = q.popleft()
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
        return view
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 1448Medium

    Count Good Nodes in Binary Tree

    DFS carrying the max value on the path; a node is good if its value ≥ that max. O(n).

    Show the Python solution
    def good_nodes(root):
        def walk(node, tallest):
            if not node:
                return 0
            good = 1 if node.val >= tallest else 0
            tallest = max(tallest, node.val)
            return good + walk(node.left, tallest) + walk(node.right, tallest)
        return walk(root, root.val)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 98Medium

    Validate Binary Search Tree

    Pass (low, high) bounds down the tree and tighten them at each step. O(n).

    Show the Python solution
    def is_valid_bst(root):
        def check(node, lo, hi):
            if not node:
                return True
            if not (lo < node.val < hi):
                return False
            return check(node.left, lo, node.val) and check(node.right, node.val, hi)
        return check(root, -inf, inf)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 230Medium

    Kth Smallest Element in a BST

    Inorder traversal of a BST is sorted; stop after k visits. O(height + k).

    Show the Python solution
    def kth_smallest(root, k):
        stack, node = [], root
        while stack or node:
            while node:                    # slide down to the smallest
                stack.append(node)
                node = node.left
            node = stack.pop()
            k -= 1
            if k == 0:
                return node.val
            node = node.right
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 105Medium

    Construct Binary Tree from Preorder and Inorder Traversal

    Preorder gives the root; its position in inorder splits left and right subtrees. With a value→index map: O(n).

    Show the Python solution
    def build(preorder, inorder):
        where = {v: i for i, v in enumerate(inorder)}
        nxt = iter(preorder)               # preorder gives roots in order
        def make(lo, hi):                  # inorder[lo..hi]
            if lo > hi:
                return None
            root = Node(next(nxt))
            mid = where[root.val]           # splits left and right
            root.left = make(lo, mid - 1)
            root.right = make(mid + 1, hi)
            return root
        return make(0, len(inorder) - 1)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 124Hard

    Binary Tree Maximum Path Sum

    DFS returns the best downward gain; update best with left + node + right, clamping negative gains to 0. O(n).

    Show the Python solution
    def max_path_sum(root):
        best = -inf
        def gain(node):
            nonlocal best
            if not node:
                return 0
            l = max(gain(node.left), 0)     # ignore losing branches
            r = max(gain(node.right), 0)
            best = max(best, node.val + l + r)
            return node.val + max(l, r)
        gain(root)
        return best
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 297Hard

    Serialize and Deserialize Binary Tree

    Preorder with null markers makes the encoding unambiguous; decoding reads the tokens back in the same order. O(n).

    Show the Python solution
    def serialize(root):
        out = []
        def walk(n):
            if not n:
                out.append("#"); return    # mark empty spots
            out.append(str(n.val)); walk(n.left); walk(n.right)
        walk(root)
        return ",".join(out)
    
    def deserialize(data):
        tokens = iter(data.split(","))
        def make():
            t = next(tokens)
            if t == "#": return None
            n = Node(int(t)); n.left = make(); n.right = make()
            return n
        return make()
    ▶ AnimationSolve on LeetCode ↗

Tries ·

  • LeetCode 208Medium

    Implement Trie (Prefix Tree)

    Each node holds children by letter plus an end-of-word flag. Every operation costs O(length of the word).

    Show the Python solution
    class Trie:
        def __init__(self):
            self.root = {}
        def insert(self, word):
            node = self.root
            for ch in word:
                node = node.setdefault(ch, {})   # grow a branch if missing
            node["$"] = True                     # mark: a word ends here
        def search(self, word, prefix=False):
            node = self.root
            for ch in word:
                if ch not in node:
                    return False
                node = node[ch]
            return prefix or "$" in node
        def starts_with(self, prefix):
            return self.search(prefix, prefix=True)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 211Medium

    Design Add and Search Words Data Structure

    Trie + depth-first search: branch over all children on “.”. Plain letters stay O(length).

    Show the Python solution
    class WordDictionary:
        def __init__(self):
            self.root = {}
        def add_word(self, word):
            node = self.root
            for ch in word:
                node = node.setdefault(ch, {})
            node["$"] = True
        def search(self, word, node=None, i=0):
            node = self.root if node is None else node
            if i == len(word):
                return "$" in node
            if word[i] == ".":                 # try every branch
                return any(self.search(word, kid, i + 1)
                           for ch, kid in node.items() if ch != "$")
            return word[i] in node and self.search(word, node[word[i]], i + 1)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 212Hard

    Word Search II

    Build a trie of all words and run one backtracking search over the grid, pruned by the trie.

    Show the Python solution
    def find_words(board, words):
        trie = build_trie(words)  # "$" = end
        found = []
        def dfs(r, c, node):
            ch = board[r][c]
            if ch not in node:
                return  # dead end
            node = node[ch]
            if "$" in node:
                found.append(node.pop("$"))
            board[r][c] = "#"          # in use
            for nr, nc in nbrs(board, r, c):
                if board[nr][nc] != "#":
                    dfs(nr, nc, node)
            board[r][c] = ch
        for r, c in all_cells(board):
            dfs(r, c, trie)
        return found
    
    def build_trie(words):
        root = {}
        for w in words:
            node = root
            for ch in w:
                node = node.setdefault(ch, {})
            node["$"] = w
        return root
    
    def all_cells(g):
        return [(r, c) for r in range(len(g))
                for c in range(len(g[0]))]
    
    def nbrs(g, r, c):  # in-grid neighbours
        R, C = len(g), len(g[0])
        for nr, nc in ((r+1, c), (r-1, c),
                       (r, c+1), (r, c-1)):
            if 0 <= nr < R and 0 <= nc < C:
                yield nr, nc
    ▶ AnimationSolve on LeetCode ↗

Heap / Priority Queue ·

  • LeetCode 703Easy

    Kth Largest Element in a Stream

    Keep a min-heap of size k; its top is the k-th largest. Each add costs O(log k).

    Show the Python solution
    class KthLargest:
        def __init__(self, k, nums):
            self.k, self.heap = k, []
            for x in nums:
                self.add(x)
        def add(self, x):
            heappush(self.heap, x)
            if len(self.heap) > self.k:
                heappop(self.heap)        # weakest of the top k leaves
            return self.heap[0]           # the k-th largest so far
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 1046Easy

    Last Stone Weight

    A max-heap hands over the two largest in O(log n) each; repeat until at most one rock remains.

    Show the Python solution
    def last_stone_weight(stones):
        heap = [-s for s in stones]          # max-heap via negatives
        heapify(heap)
        while len(heap) > 1:
            a = -heappop(heap)                # heaviest
            b = -heappop(heap)                # second heaviest
            if a != b:
                heappush(heap, -(a - b))      # what’s left of the bigger rock
        return -heap[0] if heap else 0
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 973Medium

    K Closest Points to Origin

    Compare squared distances; keep a max-heap of size k (or heapify and pop k). O(n log k).

    Show the Python solution
    def k_closest(points, k):
        heap = []                          # max-heap of the k closest (negated)
        for x, y in points:
            d = x * x + y * y
            heappush(heap, (-d, x, y))
            if len(heap) > k:
                heappop(heap)                  # drop the farthest
        return [[x, y] for _, x, y in heap]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 215Medium

    Kth Largest Element in an Array

    Min-heap of size k: the top is the answer. O(n log k).

    Show the Python solution
    def find_kth_largest(nums, k):
        heap = []                  # min-heap of the k largest so far
        for x in nums:
            heappush(heap, x)
            if len(heap) > k:
                heappop(heap)          # the weakest leaves
        return heap[0]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 621Medium

    Task Scheduler

    Greedy: always run the most frequent available task; a queue holds tasks in cooldown. (Formula version: (maxCount − 1) × (n + 1) + number of tasks with maxCount.)

    Show the Python solution
    def least_interval(tasks, n):
        heap = [-c for c in Counter(tasks).values()]
        heapify(heap)
        cooling, time = deque(), 0         # (count left, ready time)
        while heap or cooling:
            time += 1
            if heap:
                c = heappop(heap) + 1           # do the most-needed task
                if c: cooling.append((c, time + n))
            if cooling and cooling[0][1] == time:
                heappush(heap, cooling.popleft()[0])
        return time
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 355Medium

    Design Twitter

    Merge k sorted lists with a heap, stopping after 10 posts. Follow sets are hash sets.

    Show the Python solution
    class Twitter:
        def __init__(self):
            self.time = 0
            self.posts = defaultdict(list)      # user -> [(time, id)]
            self.follows = defaultdict(set)
        def postTweet(self, user, tweet):
            self.time += 1
            self.posts[user].append((self.time, tweet))
        def getNewsFeed(self, user):
            people = self.follows[user] | {user}
            heap = [(-t, id) for p in people for t, id in self.posts[p][-10:]]
            return [id for _, id in nsmallest(10, heap)]   # newest first
        def follow(self, a, b): self.follows[a].add(b)
        def unfollow(self, a, b): self.follows[a].discard(b)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 295Hard

    Find Median from Data Stream

    Two heaps split the data into halves; rebalance after each insert. Add O(log n), median O(1).

    Show the Python solution
    class MedianFinder:
        def __init__(self):
            self.low, self.high = [], []    # max-heap (negated), min-heap
        def add_num(self, x):
            heappush(self.low, -x)
            heappush(self.high, -heappop(self.low))
            if len(self.high) > len(self.low):
                heappush(self.low, -heappop(self.high))
        def find_median(self):
            if len(self.low) > len(self.high):
                return -self.low[0]
            return (-self.low[0] + self.high[0]) / 2
    ▶ AnimationSolve on LeetCode ↗

Backtracking ·

  • LeetCode 78Medium

    Subsets

    Backtracking: at each index branch “include” and “exclude”. 2ⁿ subsets.

    Show the Python solution
    def subsets(nums):
        res, pick = [], []
        def dfs(i):
            if i == len(nums):
                res.append(pick[:])          # a finished pizza
                return
            pick.append(nums[i])             # take topping i
            dfs(i + 1)
            pick.pop()                       # leave topping i
            dfs(i + 1)
        dfs(0)
        return res
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 39Medium

    Combination Sum

    Backtracking with a start index (to avoid reorderings) and reuse allowed: recurse with the same index after choosing a coin.

    Show the Python solution
    def combination_sum(coins, target):
        coins.sort(); res = []
        def dfs(start, left, path):
            if left == 0:
                res.append(path[:]); return
            for i in range(start, len(coins)):
                if coins[i] > left:
                    break                     # too big, and so is everything after
                dfs(i, left - coins[i], path + [coins[i]])   # same coin may repeat
        dfs(0, target, [])
        return res
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 46Medium

    Permutations

    Backtracking with a “used” set: choose, recurse, un-choose. n! orderings.

    Show the Python solution
    def permute(nums):
        res, seat = [], []
        def dfs():
            if len(seat) == len(nums):
                res.append(seat[:]); return
            for x in nums:
                if x not in seat:            # guest still standing
                    seat.append(x)
                    dfs()
                    seat.pop()               # stand up again, try someone else
        dfs()
        return res
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 90Medium

    Subsets II

    Sort, then skip nums[i] when i > start and nums[i] == nums[i−1]. This removes duplicate branches.

    Show the Python solution
    def subsets_with_dup(nums):
        nums.sort(); res = []
        def dfs(start, pick):
            res.append(pick[:])
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue                  # same topping, same branch: skip
                dfs(i + 1, pick + [nums[i]])
        dfs(0, [])
        return res
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 40Medium

    Combination Sum II

    Sort + backtracking moving to i + 1 (no reuse) + skip equal neighbours at the same level.

    Show the Python solution
    def combination_sum2(coins, target):
        coins.sort(); res = []
        def dfs(start, left, path):
            if left == 0:
                res.append(path[:]); return
            for i in range(start, len(coins)):
                if i > start and coins[i] == coins[i - 1]:
                    continue                  # same value at this level: skip
                if coins[i] > left:
                    break
                dfs(i + 1, left - coins[i], path + [coins[i]])   # each coin once
        dfs(0, target, [])
        return res
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 79Medium

    Word Search

    Depth-first search with backtracking: mark, explore 4 neighbours, unmark. Stop as soon as the whole word is matched.

    Show the Python solution
    def exist(board, word):
        R, C = len(board), len(board[0])
        def dfs(r, c, i):
            if i == len(word):
                return True
            if not (0 <= r < R and 0 <= c < C):
                return False
            if board[r][c] != word[i]:
                return False
            board[r][c] = "#"  # mark: in use
            found = any(dfs(r+dr, c+dc, i+1)
                        for dr, dc in DIRS)
            board[r][c] = word[i]      # unmark
            return found
        return any(dfs(r, c, 0)
                   for r in range(R)
                   for c in range(C))
    
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 131Medium

    Palindrome Partitioning

    Backtracking: try every end position for the next piece, recurse only if that piece is a palindrome.

    Show the Python solution
    def partition(s):
        out, parts = [], []
        def cut(start):
            if start == len(s):
                out.append(parts[:])
                return
            for end in range(start + 1, len(s) + 1):
                piece = s[start:end]
                if piece == piece[::-1]:
                    parts.append(piece)
                    cut(end)
                    parts.pop()
        cut(0)
        return out
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 17Medium

    Letter Combinations of a Phone Number

    Backtracking over digits; at each level loop over that digit’s letters. 3ⁿ–4ⁿ results.

    Show the Python solution
    KEYS = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
    def letter_combinations(digits):
        res = []
        def dfs(i, word):
            if i == len(digits):
                res.append(word); return
            for ch in KEYS[digits[i]]:
                dfs(i + 1, word + ch)
        if digits: dfs(0, "")
        return res
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 51Hard

    N-Queens

    Backtrack row by row; three sets (columns, r−c diagonals, r+c diagonals) make each safety check O(1).

    Show the Python solution
    def solve_n_queens(n):
        cols, d1, d2, res, board = set(), set(), set(), [], []
        def place(r):
            if r == n:
                res.append(["." * c + "Q" + "." * (n - c - 1) for c in board]); return
            for c in range(n):
                if c in cols or r - c in d1 or r + c in d2:
                    continue                  # attacked: skip this square
                cols.add(c); d1.add(r - c); d2.add(r + c); board.append(c)
                place(r + 1)
                cols.remove(c); d1.remove(r - c); d2.remove(r + c); board.pop()
        place(0)
        return res
    ▶ AnimationSolve on LeetCode ↗

Graphs ·

  • LeetCode 200Medium

    Number of Islands

    For each unvisited land cell: count + 1, then DFS/BFS to mark its whole island. O(rows × cols).

    Show the Python solution
    def num_islands(grid):
        count = 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == "1":
                    count += 1
                    flood(grid, r, c)
        return count
    
    def flood(grid, r, c):
        q = deque([(r, c)]); grid[r][c] = "0"
        while q:
            r, c = q.popleft()
            for nr, nc in nbrs(grid, r, c):
                if grid[nr][nc] == "1":
                    grid[nr][nc] = "0"
                    q.append((nr, nc))
    
    def nbrs(g, r, c):  # in-grid neighbours
        R, C = len(g), len(g[0])
        for nr, nc in ((r+1, c), (r-1, c),
                       (r, c+1), (r, c-1)):
            if 0 <= nr < R and 0 <= nc < C:
                yield nr, nc
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 133Medium

    Clone Graph

    BFS/DFS with an old→new dictionary so each node is copied once and cycles don’t loop forever. O(V + E).

    Show the Python solution
    def clone_graph(node):
        if not node:
            return None
        copies = {node: Node(node.val)}
        q = deque([node])
        while q:
            cur = q.popleft()
            for nb in cur.neighbors:
                if nb not in copies:
                    copies[nb] = Node(nb.val)
                    q.append(nb)
                copies[cur].neighbors.append(copies[nb])
        return copies[node]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 695Medium

    Max Area of Island

    Flood fill each island, returning its size. O(rows × cols).

    Show the Python solution
    def max_area(grid):
        best = 0
        for r, c in all_cells(grid):
            if grid[r][c] == 1:
                size = flood(grid, r, c)
                best = max(best, size)
        return best
    
    def flood(grid, r, c):  # paint, count
        q, size = deque([(r, c)]), 1
        grid[r][c] = 0
        while q:
            r, c = q.popleft()
            for nr, nc in nbrs(grid, r, c):
                if grid[nr][nc] == 1:
                    grid[nr][nc] = 0
                    size += 1
                    q.append((nr, nc))
        return size
    
    def all_cells(g):
        return [(r, c) for r in range(len(g))
                for c in range(len(g[0]))]
    
    def nbrs(g, r, c):  # in-grid neighbours
        R, C = len(g), len(g[0])
        for nr, nc in ((r+1, c), (r-1, c),
                       (r, c+1), (r, c-1)):
            if 0 <= nr < R and 0 <= nc < C:
                yield nr, nc
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 417Medium

    Pacific Atlantic Water Flow

    Reverse the flow: BFS/DFS uphill from each ocean’s border, then intersect. O(rows × cols).

    Show the Python solution
    def pacific_atlantic(h):
        R, C = len(h), len(h[0])
        def climb(starts):        # walk uphill
            seen, q = set(starts), deque(starts)
            while q:
                r, c = q.popleft()
                for nr, nc in nbrs(h, r, c):
                    if (nr, nc) in seen:
                        continue
                    if h[nr][nc] >= h[r][c]:
                        seen.add((nr, nc))
                        q.append((nr, nc))
            return seen
        top = [(0, c) for c in range(C)]
        left = [(r, 0) for r in range(R)]
        bot = [(R - 1, c) for c in range(C)]
        right = [(r, C - 1) for r in range(R)]
        pac = climb(top + left)
        atl = climb(bot + right)
        return sorted(pac & atl)
    
    def nbrs(g, r, c):  # in-grid neighbours
        R, C = len(g), len(g[0])
        for nr, nc in ((r+1, c), (r-1, c),
                       (r, c+1), (r, c-1)):
            if 0 <= nr < R and 0 <= nc < C:
                yield nr, nc
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 130Medium

    Surrounded Regions

    Flood fill from border O cells to mark the survivors, then flip the rest. O(rows × cols).

    Show the Python solution
    def solve(board):
        R, C = len(board), len(board[0])
        q = deque()  # edge cells
        for r, c in all_cells(board):
            if r in (0, R-1) or c in (0, C-1):
                q.append((r, c))
        while q:  # edge-linked: safe
            r, c = q.popleft()
            if board[r][c] == "O":
                board[r][c] = "S"
                q.extend(nbrs(board, r, c))
        for r, c in all_cells(board):
            if board[r][c] == "O":
                board[r][c] = "X"     # captured
            if board[r][c] == "S":
                board[r][c] = "O"
    
    def all_cells(g):
        return [(r, c) for r in range(len(g))
                for c in range(len(g[0]))]
    
    def nbrs(g, r, c):  # in-grid neighbours
        R, C = len(g), len(g[0])
        for nr, nc in ((r+1, c), (r-1, c),
                       (r, c+1), (r, c-1)):
            if 0 <= nr < R and 0 <= nc < C:
                yield nr, nc
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 994Medium

    Rotting Oranges

    Multi-source BFS: all starting points enter the queue at once, and each level is one minute. O(rows × cols).

    Show the Python solution
    def oranges_rotting(grid):
        q, fresh = deque(), 0
        for r, c in all_cells(grid):
            if grid[r][c] == 2: q.append((r, c))
            if grid[r][c] == 1: fresh += 1
        minutes = 0
        while q and fresh:
            for _ in range(len(q)):
                r, c = q.popleft()
                for nr, nc in nbrs(grid, r, c):
                    if grid[nr][nc] == 1:
                        grid[nr][nc] = 2
                        fresh -= 1
                        q.append((nr, nc))
            minutes += 1
        return minutes if fresh == 0 else -1
    
    def all_cells(g):
        return [(r, c) for r in range(len(g))
                for c in range(len(g[0]))]
    
    def nbrs(g, r, c):  # in-grid neighbours
        R, C = len(g), len(g[0])
        for nr, nc in ((r+1, c), (r-1, c),
                       (r, c+1), (r, c-1)):
            if 0 <= nr < R and 0 <= nc < C:
                yield nr, nc
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 286Medium

    Walls and Gates

    Multi-source BFS from all gates; first arrival = shortest distance. O(rows × cols).

    Show the Python solution
    def walls_and_gates(rooms):
        q = deque()
        for r, c in all_cells(rooms):
            if rooms[r][c] == 0:  # a gate
                q.append((r, c))
        while q:  # gates spread together
            r, c = q.popleft()
            d = rooms[r][c] + 1
            for nr, nc in nbrs(rooms, r, c):
                if rooms[nr][nc] == INF:
                    rooms[nr][nc] = d
                    q.append((nr, nc))
    
    INF = 2**31 - 1  # empty room
    
    def all_cells(g):
        return [(r, c) for r in range(len(g))
                for c in range(len(g[0]))]
    
    def nbrs(g, r, c):  # in-grid neighbours
        R, C = len(g), len(g[0])
        for nr, nc in ((r+1, c), (r-1, c),
                       (r, c+1), (r, c-1)):
            if 0 <= nr < R and 0 <= nc < C:
                yield nr, nc
    ▶ AnimationSolve on LeetCode ↗ (LeetCode Premium; free on NeetCode ↗)
  • LeetCode 207Medium

    Course Schedule

    Kahn’s topological sort: count incoming arrows, repeatedly take courses with count 0. All taken ⇔ no cycle.

    Show the Python solution
    def can_finish(n, prerequisites):
        indeg = [0] * n; nxt = defaultdict(list)
        for course, need in prerequisites:
            nxt[need].append(course); indeg[course] += 1
        q = deque(c for c in range(n) if indeg[c] == 0)
        taken = []
        while q:
            c = q.popleft()
            taken.append(c)
            for d in nxt[c]:
                indeg[d] -= 1
                if indeg[d] == 0:
                    q.append(d)
        return len(taken) == n
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 210Medium

    Course Schedule II

    Topological order from Kahn’s algorithm; length < n means a cycle.

    Show the Python solution
    def find_order(n, prerequisites):
        indeg = [0] * n; nxt = defaultdict(list)
        for course, need in prerequisites:
            nxt[need].append(course); indeg[course] += 1
        q = deque(c for c in range(n) if indeg[c] == 0)
        taken = []
        while q:
            c = q.popleft()
            taken.append(c)
            for d in nxt[c]:
                indeg[d] -= 1
                if indeg[d] == 0:
                    q.append(d)
        return taken if len(taken) == n else []
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 684Medium

    Redundant Connection

    Union-find: for each edge, if find(a) == find(b) it is the extra edge; otherwise union them.

    Show the Python solution
    def find_redundant(edges):
        n = len(edges) + 1
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                return [a, b]   # closes a loop
            parent[rb] = ra
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 323Medium

    Number of Connected Components in an Undirected Graph

    Union-find: components = n − (number of successful unions).

    Show the Python solution
    def count_components(n, edges):
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        groups = n
        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[rb] = ra
                groups -= 1
        return groups
    ▶ AnimationSolve on LeetCode ↗ (LeetCode Premium; free on NeetCode ↗)
  • LeetCode 261Medium

    Graph Valid Tree

    A tree ⇔ exactly n − 1 edges and no union fails (no cycle).

    Show the Python solution
    def valid_tree(n, edges):
        if len(edges) != n - 1:
            return False
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False          # a loop
            parent[rb] = ra           # union
        return True    # n-1 edges, no loop
    ▶ AnimationSolve on LeetCode ↗ (LeetCode Premium; free on NeetCode ↗)
  • LeetCode 127Hard

    Word Ladder

    BFS over words (neighbours = one-letter changes found in the dictionary). The first time you reach the end word is the shortest.

    Show the Python solution
    def ladder_length(begin, end, words):
        words, q, steps = set(words), deque([begin]), 1
        while q:
            for _ in range(len(q)):
                w = q.popleft()
                if w == end:
                    return steps
                for i in range(len(w)):
                    for ch in "abcdefghijklmnopqrstuvwxyz":
                        nxt = w[:i] + ch + w[i + 1:]
                        if nxt in words:
                            words.remove(nxt); q.append(nxt)
            steps += 1
        return 0
    ▶ AnimationSolve on LeetCode ↗

Advanced Graphs ·

  • LeetCode 332Hard

    Reconstruct Itinerary

    Hierholzer’s algorithm for an Eulerian path: DFS with sorted tickets, append a node when stuck, reverse at the end.

    Show the Python solution
    def find_itinerary(tickets):
        out = defaultdict(list)
        for a, b in sorted(tickets, reverse=True):
            out[a].append(b)                 # pop() gives the smallest
        route = []
        def fly(airport):
            while out[airport]:
                fly(out[airport].pop())      # use a ticket
            route.append(airport)            # stuck here: finalise this stop
        fly("JFK")
        return route[::-1]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 1584Medium

    Min Cost to Connect All Points

    Prim’s algorithm for a minimum spanning tree: grow from one point, always taking the cheapest edge to a new point.

    Show the Python solution
    def min_cost_connect(points):
        n, done, cost = len(points), set(), 0
        heap = [(0, 0)]                     # (cable length, house)
        while len(done) < n:
            d, i = heappop(heap)
            if i in done:
                continue
            done.add(i); cost += d
            for j in range(n):
                if j not in done:
                    dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                    heappush(heap, (dist, j))
        return cost
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 743Medium

    Dijkstra

    Dijkstra: a min-heap of (time, junction); pop the closest, relax its roads. Works when no road has negative time.

    Show the Python solution
    def network_delay_time(times, n, k):
        roads = defaultdict(list)
        for u, v, w in times:         # one-way
            roads[u].append((v, w))
        dist = {k: 0}
        pq = [(0, k)]
        while pq:
            d, u = heappop(pq)         # closest
            if d > dist[u]:
                continue
            for v, w in roads[u]:
                if d + w < dist.get(v, inf):
                    dist[v] = d + w
                    heappush(pq, (dist[v], v))
        if len(dist) < n:
            return -1  # someone never hears
        return max(dist.values())
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 778Hard

    Swim in Rising Water

    Dijkstra-style search where a path’s cost is its maximum height, not its sum.

    Show the Python solution
    def swim_in_water(grid):
        n = len(grid)
        heap = [(grid[0][0], 0, 0)]
        seen = {(0, 0)}
        while heap:
            t, r, c = heappop(heap)  # lowest
            if (r, c) == (n - 1, n - 1):
                return t
            for nr, nc in nbrs(grid, r, c):
                if (nr, nc) not in seen:
                    seen.add((nr, nc))
                    tt = max(t, grid[nr][nc])
                    heappush(heap, (tt, nr, nc))
    
    def nbrs(g, r, c):  # in-grid neighbours
        R, C = len(g), len(g[0])
        for nr, nc in ((r+1, c), (r-1, c),
                       (r, c+1), (r, c-1)):
            if 0 <= nr < R and 0 <= nc < C:
                yield nr, nc
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 269Hard

    Alien Dictionary

    Build “a before b” edges from adjacent words, then topologically sort. A cycle (or a longer word before its own prefix) means invalid.

    Show the Python solution
    def alien_order(words):
        after = {ch: set() for w in words for ch in w}
        for a, b in zip(words, words[1:]):
            for x, y in zip(a, b):
                if x != y:
                    after[x].add(y)            # x comes before y
                    break
            else:
                if len(a) > len(b): return ""  # "abc" before "ab" is impossible
        indeg = {ch: 0 for ch in after}
        for x in after:
            for y in after[x]: indeg[y] += 1
        q = deque(ch for ch in after if indeg[ch] == 0)
        order = ""
        while q:
            ch = q.popleft(); order += ch
            for y in after[ch]:
                indeg[y] -= 1
                if indeg[y] == 0: q.append(y)
        return order if len(order) == len(after) else ""
    ▶ AnimationSolve on LeetCode ↗ (LeetCode Premium; free on NeetCode ↗)
  • LeetCode 787Medium

    Cheapest Flights Within K Stops

    Bellman–Ford limited to k + 1 rounds, using last round’s prices (a copy) for each relaxation.

    Show the Python solution
    def find_cheapest_price(n, flights, src, dst, k):
        price = [inf] * n
        price[src] = 0
        for _ in range(k + 1):               # at most k stops = k+1 flights
            nxt = price[:]                   # only build on last round’s prices
            for a, b, cost in flights:
                if price[a] + cost < nxt[b]:
                    nxt[b] = price[a] + cost
            price = nxt
        return -1 if price[dst] == inf else price[dst]
    ▶ AnimationSolve on LeetCode ↗

1-D DP ·

  • LeetCode 70Easy

    Climbing Stairs

    ways[i] = ways[i − 1] + ways[i − 2]: the Fibonacci pattern. Only the last two numbers are needed. O(n).

    Show the Python solution
    def climb(n):
        ways = [1, 1] + [0] * (n - 1)
        for i in range(2, n + 1):
            ways[i] = ways[i - 1] + ways[i - 2]
        return ways[n]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 746Easy

    Min Cost Climbing Stairs

    best[i] = min(best[i − 1] + cost[i − 1], best[i − 2] + cost[i − 2]). O(n).

    Show the Python solution
    def min_cost_climbing_stairs(cost):
        n = len(cost)
        best = [0] * (n + 1)            # cheapest way to stand on step i
        for i in range(2, n + 1):
            best[i] = min(best[i - 1] + cost[i - 1],   # one step from i-1
                          best[i - 2] + cost[i - 2])   # or two from i-2
        return best[n]                   # the top is just past the last step
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 198Medium

    House Robber

    best[i] = max(best[i − 1], best[i − 2] + money[i]). O(n), O(1) memory.

    Show the Python solution
    def rob(houses):
        skip, take = 0, 0           # best total if the last house was skipped / robbed
        for loot in houses:
            skip, take = max(skip, take), skip + loot
        return max(skip, take)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 213Medium

    House Robber II

    answer = max(rob(houses[1:]), rob(houses[:-1])). Two linear passes.

    Show the Python solution
    def rob_circle(houses):
        if len(houses) == 1:
            return houses[0]
        def rob_line(hs):
            skip, take = 0, 0
            for loot in hs:
                skip, take = max(skip, take), skip + loot
            return max(skip, take)
        return max(rob_line(houses[1:]),    # leave the first house alone
                   rob_line(houses[:-1]))   # or leave the last one
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 5Medium

    Longest Palindromic Substring

    Expand around 2n − 1 centres. O(n²) time, O(1) memory.

    Show the Python solution
    def longest_palindrome(s):
        best = ""
        for c in range(len(s)):
            for l, r in ((c, c), (c, c + 1)):   # odd, even
                while l >= 0 and r < len(s) and s[l] == s[r]:
                    l, r = l - 1, r + 1
                if r - l - 1 > len(best):
                    best = s[l + 1:r]
        return best
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 647Medium

    Palindromic Substrings

    Expand around every centre and count each successful step. O(n²).

    Show the Python solution
    def count_substrings(s):
        count = 0
        for c in range(len(s)):
            for l, r in ((c, c), (c, c + 1)):   # odd and even centres
                while l >= 0 and r < len(s) and s[l] == s[r]:
                    count += 1
                    l, r = l - 1, r + 1
        return count
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 91Medium

    Decode Ways

    ways[i] = (ways[i − 1] if s[i−1] ≠ 0) + (ways[i − 2] if 10 ≤ s[i−2:i] ≤ 26). O(n).

    Show the Python solution
    def num_decodings(s):          # 1 = A … 26 = Z
        ways = [1] + [0] * len(s)    # ways[i]: ways to read the first i digits
        for i in range(1, len(s) + 1):
            if s[i - 1] != "0":
                ways[i] += ways[i - 1]         # read one digit
            if i > 1 and 10 <= int(s[i - 2:i]) <= 26:
                ways[i] += ways[i - 2]         # read two digits
        return ways[len(s)]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 322Medium

    Coin Change

    best[x] = 1 + min(best[x − c]) over coins c. O(amount × coins).

    Show the Python solution
    def coin_change(coins, amount):
        fewest = [0] + [inf] * amount
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a:
                    n = fewest[a - c] + 1
                    fewest[a] = min(fewest[a], n)
        best = fewest[amount]
        return -1 if best == inf else best
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 152Medium

    Maximum Product Subarray

    Track both max and min product ending at i; cur_max = max(x, x·prev_max, x·prev_min). O(n).

    Show the Python solution
    def max_product(nums):
        hi = lo = best = nums[0]
        for x in nums[1:]:
            if x < 0:
                hi, lo = lo, hi            # a negative swaps big and small
            hi = max(x, hi * x)
            lo = min(x, lo * x)
            best = max(best, hi)
        return best
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 139Medium

    Word Break

    ok[i] is True if some word w ends at position i and ok[i − len(w)] is True. This loop tries all W words at each of the n positions, comparing up to L letters each time: O(n · W · L). (The other common version tries every split point j < i and looks s[j:i] up in a set: O(n²) substring checks, each costing up to O(L) once pieces longer than the longest word L are skipped, so O(n² · L) at most.)

    Show the Python solution
    def word_break(s, words):
        ok = [True] + [False] * len(s)  # s[:i]?
        for i in range(1, len(s) + 1):
            for w in words:
                j = i - len(w)  # w = s[j:i]?
                if j >= 0 and ok[j] and s[j:i] == w:
                    ok[i] = True
                    break
        return ok[len(s)]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 300Medium

    Longest Increasing Subsequence

    Patience sorting: keep pile tops (always sorted) and binary search where each card goes. O(n log n).

    Show the Python solution
    def length_of_lis(nums):
        piles = []                       # top card of each pile, increasing
        for x in nums:
            i = bisect_left(piles, x)     # leftmost pile whose top is >= x
            if i == len(piles):
                piles.append(x)           # bigger than every top: new pile
            else:
                piles[i] = x              # place it on that pile
        return len(piles)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 416Medium

    Partition Equal Subset Sum

    Subset-sum: a set (or boolean row) of reachable sums, updated per weight. O(n × total/2).

    Show the Python solution
    def can_partition(nums):
        total = sum(nums)
        if total % 2:
            return False
        half = total // 2
        reach = {0}                         # sums one pan can hold so far
        for x in nums:
            reach |= {r + x for r in reach if r + x <= half}
        return half in reach
    ▶ AnimationSolve on LeetCode ↗

2-D DP ·

  • LeetCode 62Medium

    Unique Paths

    paths[r][c] = paths[r − 1][c] + paths[r][c − 1]. Fill in row order. O(m × n).

    Show the Python solution
    def unique_paths(m, n):
        ways = [[1] * n for _ in range(m)]   # first row and column: one way
        for r in range(1, m):
            for c in range(1, n):
                ways[r][c] = ways[r - 1][c] + ways[r][c - 1]   # from above + from the left
        return ways[m - 1][n - 1]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 1143Medium

    Longest Common Subsequence

    dp[i][j] = dp[i−1][j−1] + 1 if A[i] == B[j], else max(dp[i−1][j], dp[i][j−1]). O(m × n).

    Show the Python solution
    def lcs(a, b):
        t = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
        for i in range(1, len(a) + 1):
            for j in range(1, len(b) + 1):
                if a[i - 1] == b[j - 1]:
                    t[i][j] = t[i - 1][j - 1] + 1     # letters pair up
                else:
                    t[i][j] = max(t[i - 1][j], t[i][j - 1])
        return t[len(a)][len(b)]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 309Medium

    Best Time to Buy and Sell Stock with Cooldown

    State machine DP: hold = max(hold, rest − price); sold = hold + price; rest = max(rest, sold). O(n).

    Show the Python solution
    def max_profit(prices):
        hold, sold, rest = -inf, 0, 0
        for p in prices:
            hold, sold, rest = (max(hold, rest - p),   # keep, or buy (only after resting)
                                hold + p,                # sell today
                                max(rest, sold))         # do nothing (cooldown ends)
        return max(sold, rest)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 518Medium

    Coin Change II

    ways[x] += ways[x − c], looping coins on the outside and amounts on the inside. O(amount × coins).

    Show the Python solution
    def change(amount, coins):
        ways = [1] + [0] * amount
        for c in coins:                  # one coin type at a time: no reorderings
            for a in range(c, amount + 1):
                ways[a] += ways[a - c]
        return ways[amount]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 494Medium

    Target Sum

    DP over sums: a dictionary position → count, updated for each number with ±. O(n × range).

    Show the Python solution
    def find_target_sum_ways(nums, target):
        ways = {0: 1}                     # total -> number of sign choices
        for x in nums:
            nxt = defaultdict(int)
            for total, w in ways.items():
                nxt[total + x] += w
                nxt[total - x] += w
            ways = nxt
        return ways.get(target, 0)
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 97Medium

    Interleaving String

    dp[i][j] = (dp[i−1][j] and A[i−1] == C[i+j−1]) or (dp[i][j−1] and B[j−1] == C[i+j−1]). O(m × n).

    Show the Python solution
    def is_interleave(a, b, c):
        if len(a) + len(b) != len(c): return False
        ok = [[False] * (len(b) + 1) for _ in range(len(a) + 1)]
        ok[0][0] = True
        for i in range(len(a) + 1):
            for j in range(len(b) + 1):
                k = i + j - 1                 # next letter of c to explain
                if i and a[i - 1] == c[k] and ok[i - 1][j]: ok[i][j] = True
                if j and b[j - 1] == c[k] and ok[i][j - 1]: ok[i][j] = True
        return ok[len(a)][len(b)]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 329Hard

    Longest Increasing Path in a Matrix

    DFS with memoisation; the strict increase rule means there are no cycles. O(rows × cols).

    Show the Python solution
    def longest_increasing_path(h):
        memo = {}
        def climb(r, c):  # best hike from here
            if (r, c) not in memo:
                up = [0]
                for nr, nc in nbrs(h, r, c):
                    if h[nr][nc] > h[r][c]:
                        up.append(climb(nr, nc))
                memo[(r, c)] = 1 + max(up)
            return memo[(r, c)]
        return max(climb(r, c)
                   for r, c in all_cells(h))
    
    def all_cells(g):
        return [(r, c) for r in range(len(g))
                for c in range(len(g[0]))]
    
    def nbrs(g, r, c):  # in-grid neighbours
        R, C = len(g), len(g[0])
        for nr, nc in ((r+1, c), (r-1, c),
                       (r, c+1), (r, c-1)):
            if 0 <= nr < R and 0 <= nc < C:
                yield nr, nc
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 115Hard

    Distinct Subsequences

    dp[i][j] = dp[i−1][j] + (dp[i−1][j−1] if s[i−1] == t[j−1]). O(m × n).

    Show the Python solution
    def num_distinct(s, t):
        ways = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
        for i in range(len(s) + 1):
            ways[i][0] = 1                   # empty t: cross out everything
        for i in range(1, len(s) + 1):
            for j in range(1, len(t) + 1):
                ways[i][j] = ways[i - 1][j]    # skip s[i-1]
                if s[i - 1] == t[j - 1]:
                    ways[i][j] += ways[i - 1][j - 1]   # or use it
        return ways[len(s)][len(t)]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 72Medium

    Edit Distance

    Classic edit distance DP. O(m × n).

    Show the Python solution
    def min_distance(a, b):
        d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
        for i in range(len(a) + 1): d[i][0] = i     # delete everything
        for j in range(len(b) + 1): d[0][j] = j     # type everything
        for i in range(1, len(a) + 1):
            for j in range(1, len(b) + 1):
                if a[i - 1] == b[j - 1]:
                    d[i][j] = d[i - 1][j - 1]          # letters already agree
                else:
                    d[i][j] = 1 + min(d[i - 1][j],     # delete
                                      d[i][j - 1],     # insert
                                      d[i - 1][j - 1]) # replace
        return d[len(a)][len(b)]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 312Hard

    Burst Balloons

    Interval DP: dp[l][r] = max over k of dp[l][k] + dp[k][r] + v[l]·v[k]·v[r]. O(n³).

    Show the Python solution
    def max_coins(nums):
        b = [1] + nums + [1]                 # imaginary 1-balloons at the ends
        n = len(b)
        best = [[0] * n for _ in range(n)]   # best[l][r]: pop everything strictly between
        for gap in range(2, n):
            for l in range(n - gap):
                r = l + gap
                for k in range(l + 1, r):     # k is the LAST balloon popped in (l, r)
                    best[l][r] = max(best[l][r],
                                     best[l][k] + b[l] * b[k] * b[r] + best[k][r])
        return best[0][n - 1]
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 10Hard

    Regular Expression Matching

    dp over (text prefix, pattern prefix); handle “*” as zero uses (j − 2) or one more use (i − 1). O(m × n).

    Show the Python solution
    def is_match(s, p):
        m, n = len(s), len(p)
        ok = [[False] * (n + 1) for _ in range(m + 1)]
        ok[0][0] = True
        for i in range(m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == "*":                       # x* : zero copies, or one more
                    ok[i][j] = ok[i][j - 2] or (i > 0 and p[j - 2] in (s[i - 1], ".") and ok[i - 1][j])
                elif i > 0 and p[j - 1] in (s[i - 1], "."):
                    ok[i][j] = ok[i - 1][j - 1]
        return ok[m][n]
    ▶ AnimationSolve on LeetCode ↗

Greedy ·

  • LeetCode 53Medium

    Maximum Subarray (Kadane)

    Kadane: cur = max(x, cur + x); best = max(best, cur). O(n).

    Show the Python solution
    def max_subarray(days):
        cur = best = days[0]
        for x in days[1:]:
            cur = max(x, cur + x)      # keep the streak or start fresh
            best = max(best, cur)
        return best
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 55Medium

    Jump Game

    Greedy: reach = max(reach, i + nums[i]); fail if i > reach. O(n).

    Show the Python solution
    def can_jump(pads):
        reach = 0
        for i, jump in enumerate(pads):
            if i > reach:
                return False               # this pad can never be reached
            reach = max(reach, i + jump)
        return True
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 45Medium

    Jump Game II

    BFS by ranges: when i reaches the end of the current wave, jumps += 1 and the wave end becomes the farthest reach. O(n).

    Show the Python solution
    def jump(pads):
        hops, end, far = 0, 0, 0
        for i in range(len(pads) - 1):
            far = max(far, i + pads[i])     # best reach from this wave
            if i == end:                    # finished the current wave
                hops += 1
                end = far
        return hops
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 134Medium

    Gas Station

    One pass: reset the start to i + 1 whenever the running tank drops below 0. O(n).

    Show the Python solution
    def can_complete_circuit(gas, cost):
        if sum(gas) < sum(cost):
            return -1                       # not enough fuel in total
        tank, start = 0, 0
        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            if tank < 0:                     # ran dry: no start up to i works
                start, tank = i + 1, 0
        return start
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 846Medium

    Hand of Straights

    Count cards; always start a run at the smallest remaining value and consume the following values. O(n log n).

    Show the Python solution
    def is_n_straight_hand(hand, size):
        count = Counter(hand)
        for start in sorted(count):
            need = count[start]              # runs that must start at this card
            if need:
                for v in range(start, start + size):
                    if count[v] < need:
                        return False
                    count[v] -= need
        return True
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 1899Medium

    Merge Triplets to Form Target Triplet

    Ignore triplets exceeding the target anywhere; the rest must cover each target value. O(n).

    Show the Python solution
    def merge_triplets(triplets, target):
        got = set()
        for t in triplets:
            if any(t[i] > target[i] for i in range(3)):
                continue                    # would overshoot: never use it
            for i in range(3):
                if t[i] == target[i]:
                    got.add(i)              # this pot supplies slot i exactly
        return len(got) == 3
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 763Medium

    Partition Labels

    end = max(end, last[c]); cut when i == end. O(n).

    Show the Python solution
    def partition_labels(s):
        last = {ch: i for i, ch in enumerate(s)}
        sizes, start, end = [], 0, 0
        for i, ch in enumerate(s):
            end = max(end, last[ch])         # this piece must reach ch’s last copy
            if i == end:
                sizes.append(end - start + 1)  # safe to cut here
                start = i + 1
        return sizes
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 678Medium

    Valid Parenthesis String

    Greedy with (lo, hi) open-count bounds. O(n), O(1) memory.

    Show the Python solution
    def check_valid_string(s):
        lo = hi = 0                        # range of possible open brackets
        for ch in s:
            if ch == "(":   lo, hi = lo + 1, hi + 1
            elif ch == ")": lo, hi = lo - 1, hi - 1
            else:           lo, hi = lo - 1, hi + 1   # * could be ), nothing, or (
            if hi < 0:
                return False                # too many ) whatever the stars are
            lo = max(lo, 0)
        return lo == 0
    ▶ AnimationSolve on LeetCode ↗

Intervals ·

  • LeetCode 57Medium

    Insert Interval

    Three phases: before, overlapping (merge), after. O(n).

    Show the Python solution
    def insert(intervals, new):
        out, i, n = [], 0, len(intervals)
        while i < n and intervals[i][1] < new[0]:
            out.append(intervals[i]); i += 1          # ends before: keep
        while i < n and intervals[i][0] <= new[1]:
            new = [min(new[0], intervals[i][0]),       # overlaps: absorb it
                   max(new[1], intervals[i][1])]
            i += 1
        out.append(new)
        out.extend(intervals[i:])                      # starts after: keep
        return out
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 56Medium

    Merge Intervals

    Sort by start, then extend or start a new block. O(n log n).

    Show the Python solution
    def merge(intervals):
        intervals.sort()
        out = [intervals[0]]
        for start, end in intervals[1:]:
            if start <= out[-1][1]:
                out[-1][1] = max(out[-1][1], end)   # overlaps: stretch the block
            else:
                out.append([start, end])            # gap: a new block
        return out
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 435Medium

    Non-overlapping Intervals

    Greedy by earliest end; count clashes. O(n log n).

    Show the Python solution
    def erase_overlap_intervals(intervals):
        intervals.sort(key=lambda x: x[1])   # earliest finish first
        removed, free_at = 0, -inf
        for start, end in intervals:
            if start >= free_at:
                free_at = end                 # keep it
            else:
                removed += 1                  # clashes with a kept booking
        return removed
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 252Easy

    Meeting Rooms

    Sort by start and compare each start with the previous end. O(n log n).

    Show the Python solution
    def can_attend_meetings(intervals):
        intervals.sort()
        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i - 1][1]:
                return False               # starts before the last one ends
        return True
    ▶ AnimationSolve on LeetCode ↗ (LeetCode Premium; free on NeetCode ↗)
  • LeetCode 253Medium

    Meeting Rooms II

    Sort by start + min-heap of end times. O(n log n).

    Show the Python solution
    def min_meeting_rooms(intervals):
        intervals.sort()
        ends = []                           # min-heap of when each room frees up
        for start, end in intervals:
            if ends and ends[0] <= start:
                heappop(ends)                 # reuse the room that frees first
            heappush(ends, end)
        return len(ends)
    ▶ AnimationSolve on LeetCode ↗ (LeetCode Premium; free on NeetCode ↗)
  • LeetCode 1851Hard

    Minimum Interval to Include Each Query

    Sort intervals and queries; min-heap by size, discarding expired intervals. O(n log n + q log q).

    Show the Python solution
    def min_interval(intervals, queries):
        intervals.sort()
        heap, ans, i = [], {}, 0            # heap of (length, end)
        for q in sorted(queries):
            while i < len(intervals) and intervals[i][0] <= q:
                a, b = intervals[i]
                heappush(heap, (b - a + 1, b)); i += 1   # started by now
            while heap and heap[0][1] < q:
                heappop(heap)                 # already over
            ans[q] = heap[0][0] if heap else -1
        return [ans[q] for q in queries]
    ▶ AnimationSolve on LeetCode ↗

Math & Geometry ·

  • LeetCode 48Medium

    Rotate Image

    Transpose, then reverse each row. O(n²), O(1) extra space.

    Show the Python solution
    def rotate(m):
        n = len(m)
        for i in range(n):
            for j in range(i + 1, n):
                m[i][j], m[j][i] = m[j][i], m[i][j]   # flip over the diagonal
        for row in m:
            row.reverse()                              # then mirror left-right
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 54Medium

    Spiral Matrix

    Four boundaries that shrink after each side. O(rows × cols).

    Show the Python solution
    def spiral_order(m):
        out = []
        top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1
        while top <= bottom and left <= right:
            for c in range(left, right + 1): out.append(m[top][c])
            top += 1
            for r in range(top, bottom + 1): out.append(m[r][right])
            right -= 1
            if top <= bottom:
                for c in range(right, left - 1, -1): out.append(m[bottom][c])
                bottom -= 1
            if left <= right:
                for r in range(bottom, top - 1, -1): out.append(m[r][left])
                left += 1
        return out
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 73Medium

    Set Matrix Zeroes

    Record zero rows/columns first (or use the first row and column as markers), then apply. O(rows × cols).

    Show the Python solution
    def set_zeroes(m):
        rows, cols = set(), set()
        for r in range(len(m)):
            for c in range(len(m[0])):
                if m[r][c] == 0:
                    rows.add(r); cols.add(c)   # remember first, change later
        for r in range(len(m)):
            for c in range(len(m[0])):
                if r in rows or c in cols:
                    m[r][c] = 0
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 202Easy

    Happy Number

    Detect a cycle with a set (or fast/slow pointers). Numbers shrink quickly, so it’s fast.

    Show the Python solution
    def is_happy(n):
        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = sum(int(d) ** 2 for d in str(n))
        return n == 1
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 66Easy

    Plus One

    Walk from the right, turning 9s into 0s until a digit can be incremented. O(n).

    Show the Python solution
    def plus_one(digits):
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits
            digits[i] = 0               # 9 rolls over to 0, carry on
        return [1] + digits
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 50Medium

    Pow(x, n)

    Fast exponentiation by squaring: O(log n) multiplications.

    Show the Python solution
    def my_pow(x, n):
        if n < 0:
            x, n = 1 / x, -n
        result = 1
        while n:
            if n & 1:
                result *= x        # this power of two is in n
            x *= x                 # square: x, x², x⁴, x⁸ …
            n >>= 1
        return result
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 43Medium

    Multiply Strings

    An array of n + m slots; add every digit product into slot i + j + 1 and carry. O(n × m).

    Show the Python solution
    def multiply(a, b):
        res = [0] * (len(a) + len(b))
        for i in range(len(a) - 1, -1, -1):
            for j in range(len(b) - 1, -1, -1):
                p = int(a[i]) * int(b[j]) + res[i + j + 1]
                res[i + j + 1] = p % 10          # keep the ones digit
                res[i + j] += p // 10            # carry to the left
        s = "".join(map(str, res)).lstrip("0")
        return s or "0"
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 2013Medium

    Detect Squares

    Count points in a dictionary; for each diagonal candidate, multiply the counts of the other two corners.

    Show the Python solution
    class DetectSquares:
        def __init__(self):
            self.count = Counter()            # (x, y) -> pegs there
        def add(self, p):
            self.count[tuple(p)] += 1
        def count_squares(self, q):
            qx, qy = q
            total = 0
            for (x, y), c in list(self.count.items()):
                if abs(x - qx) != abs(y - qy) or x == qx:
                    continue                   # not a diagonal corner
                total += c * self.count[(x, qy)] * self.count[(qx, y)]
            return total
    ▶ AnimationSolve on LeetCode ↗

Bit Manipulation ·

  • LeetCode 136Easy

    Single Number

    a ^ a = 0 and a ^ 0 = a, so XOR of everything is the single number. O(n), O(1).

    Show the Python solution
    def single_number(nums):
        acc = 0
        for x in nums:
            acc ^= x                  # a pair flips a switch twice: back off
        return acc
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 191Easy

    Number of 1 Bits

    Repeat n &= n − 1, counting iterations: one step per 1 bit.

    Show the Python solution
    def hamming_weight(n):
        count = 0
        while n:
            n &= n - 1        # switches off the lowest light
            count += 1
        return count
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 338Easy

    Counting Bits

    bits[i] = bits[i >> 1] + (i & 1). O(n).

    Show the Python solution
    def count_bits(n):
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)   # i = (i // 2) shifted, plus last bit
        return ans
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 190Easy

    Reverse Bits

    For each bit: result = (result << 1) | (n & 1); n >>= 1.

    Show the Python solution
    def reverse_bits(n, width=32):     # this scene uses width = 8
        out = 0
        for _ in range(width):
            out = (out << 1) | (n & 1)   # take n’s last switch
            n >>= 1
        return out
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 268Easy

    Missing Number

    n(n + 1)/2 − sum(nums) (or XOR indices and values). O(n), O(1).

    Show the Python solution
    def missing_number(nums):
        n = len(nums)
        total = n * (n + 1) // 2      # roll call should add up to this
        for x in nums:
            total -= x
        return total
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 371Medium

    Sum of Two Integers

    sum = a ^ b, carry = (a & b) << 1; repeat until carry is 0. Python integers have no fixed width, so a negative number acts like endless 1-bits and the carry never dies out: mask every step with M = 0xFFFFFFFF to stay in 32 bits, and at the end turn a pattern with the top bit on back into a negative with ~(a ^ M).

    Show the Python solution
    def get_sum(a, b):
        M = 0xFFFFFFFF            # 32 one-bits
        a, b = a & M, b & M       # 32-bit view
        while b:
            carry = ((a & b) << 1) & M
            a = (a ^ b) & M  # add, no carry
            b = carry
        if a > 0x7FFFFFFF:        # top bit on:
            a = ~(a ^ M)  # it is negative
        return a
    ▶ AnimationSolve on LeetCode ↗
  • LeetCode 7Medium

    Reverse Integer

    Pop and push digits with % and //, checking against 2³¹ − 1 before each push.

    Show the Python solution
    def reverse(x):
        sign = -1 if x < 0 else 1
        x, out = abs(x), 0
        while x:
            out = out * 10 + x % 10       # move the last digit over
            x //= 10
        out *= sign
        return out if -2**31 <= out < 2**31 else 0
    ▶ AnimationSolve on LeetCode ↗