Coding DSA Interview at Big Tech — 288 Python Problems & Solutions

Phạm Ngọc Lâm — ex-Senior Software Engineer @ TikTok / Grab · co-founder EngineerPro

Lê Quang Hoà — ex-Tech Lead @ TikTok · co-founder EngineerPro

2026

Project goal: to compile the most representative DSA coding interview questions at Big Tech companies, with Python 3 solutions, complexity analysis, common interview pitfalls, and related practice problems so that readers can train systematically by pattern, not by memorising individual problems.

Scope: 288 problems (267 fully solved + 21 cross-reference recaps across chapters) · 44 patterns · Python 3 solutions matching the LeetCode style. Free web preview: first 14 chapters; full book on Gumroad.

📚 This book is based on the curriculum of the DSA Coding Interview course currently taught at EngineerPro.

However, a book cannot replace the deeper training in algorithmic thinking and the way you absorb algorithms that you get by attending the course directly at EngineerPro.

If you are interested in the course, please message our fanpage for a consultation:

📖 DSA course details 🎓 All interview training courses (DSA, System Design, CS, Behavioural) 💬 Drop Inbox message

🎯 Need 1-on-1 mentorship until you land the offer?

MentorPro is a personalised 1-on-1 mentorship program run by engineers currently or previously at Big Tech companies (NVIDIA, TikTok, Google, Meta, AWS). As a strategic partner of EngineerPro, MentorPro walks each mentee through CV screening → algorithm practice → mock interviews → until you receive a job offer.

✅ 30+ mentees have received offers at Grab, NAB, IBM, ANT Group, VinBigData, Cognizant, SAP, Deputy… since 7/2025. MentorPro mentees also get 100% free access to selected EngineerPro courses recommended by their mentor.

🌐 Visit MentorPro 💬 Message MentorPro fanpage

This project is sponsored by EngineerPro.

EngineerPro is a community and training platform dedicated to helping Vietnamese software engineers break into Big Tech and international companies — from coding interviews and system design to career growth. This book is one of our contributions to the Vietnamese learning ecosystem for engineers.

How to find us:

📖 Free web preview: the first 14 chapters (Array → Interval). Use this preview to try the patterns and practice style.

Want the full 44 chapters + appendix (288 problems with complete Python 3 solutions)? Get the full book on Gumroad:

🛒 Buy the full book on Gumroad

About the authors

Phạm Ngọc Lâm

Phạm Ngọc Lâm

ex-Senior Software Engineer @ TikTok · Grab

Co-founder EngineerPro

in LinkedIn 🌐 Portfolio

Lê Quang Hoà

Lê Quang Hoà

ex-Tech Lead @ TikTok

Co-founder EngineerPro

in LinkedIn

Both authors have been through hundreds of technical interviews, on both sides of the table — as candidates and as interviewers — at TikTok, Grab, and other leading tech companies. This book distils real lessons from both sides of that experience.

🙏 Acknowledgments

This book is inspired by the DSA topics that many outstanding mentors at EngineerPro have taught over the years across our courses and mentor sessions. The authors would like to sincerely thank the teaching team who has accompanied the community:

  • Lam Đỗ — ex-Software Engineer @ Meta
  • Lê Chương — Senior Software Engineer @ Google
  • Trần Khánh Hiệp — Software Engineer @ Spotify
  • Tùng Trần — Senior SWE @ Pendle · ex-Senior SWE @ Shopee
  • Quang Hoàng — Senior Software Engineer @ Google
  • Kyle Nguyễn — Senior Engineer @ Citadel
  • Tùng Lâm — Senior Software Engineer @ Shopee
  • Hiếu — Senior Software Engineer @ Acronis · ex-SWE @ Shopee
  • … and many other mentors across the EngineerPro community.

If this book helps you in any way, much of the credit belongs to the teachers and mentors who have tirelessly shared their knowledge with the next generation of Vietnamese engineers. 💙

Introduction

Video: a sample coding interview session

Before diving into the main content, please watch a sample coding interview session produced by EngineerPro. The video lets you visualise the real flow of an interview round: how the interviewer asks questions, how the candidate clarifies, analyses, codes, and discusses follow-ups.

Sample coding interview — EngineerPro Watch on YouTube

▶ Watch the full playlist — other sample interviews on the EngineerPro YouTube channel.

Viewing tip: the first time you watch, focus on how the candidate communicates, not on understanding every algorithm. Come back for a second viewing after finishing Chapters 1–5 and you will recognise many familiar patterns.

0.1 Foreword

Welcome to Coding DSA Interview At Big Tech — with Full Solutions.

This book is written with one simple belief: a Big Tech coding interview is not a trivia contest — it is a learnable skill that can be trained systematically.

Most existing interview materials fall into one of two extremes: - Too academic (textbook DSA), with little real-world interview context. - Too “tips and tricks” (300 LeetCode lists), without a systematic thinking framework.

This book aims to sit between the two: learn PATTERNS, not problems. Each chapter focuses on one pattern with 5–18 representative problems, including whiteboard presentation guidance and common pitfalls from real interviews. Once you internalise the pattern, new problems become variations.

Who this book is for: - CS students preparing for internships / new-grad roles at Big Tech. - Working engineers looking to switch into FAANG-tier companies. - Self-learners on LeetCode who feel stuck without a systematic approach.

We wish you success in every interview round!

How to use this book

There are three reading paths depending on your time and experience:

Sequential reading (recommended for beginners): chapters 1 → 44 in order. For each chapter you must code the problems yourself before peeking at the solutions. After finishing Level 1 (Chapters 1–20) you will have a solid foundation for entry-level Big Tech interviews.

Pattern-based reading (if you already have a foundation): skim the table of contents and dive into chapters where you feel weak. Each chapter stands alone and includes clear cross-references to related material.

Cramming before an onsite: see the Learning Roadmap below.

Learning roadmap

📖 Web free preview: only the first 14 chapters (Array → Interval) are published here. Chapters 15–44 and the appendix are in the full book on Gumroad. The roadmaps below still describe the full book so you can plan your study.

1-week roadmap (last-minute onsite prep): - Day 1–2: Frontmatter (0.1–0.5) + Appendix D (50 must-do problems). - Day 3: Review Chapters 1, 2, 5, 6 (Array, String, Binary Search, Hash) — all Easy/Medium tier. - Day 4: Chapters 7, 9, 10, 11 (Linked List, Graph, BFS, DFS). - Day 5: Chapters 17, 18, 27 (D&C, Monotonic, Sliding Window). - Day 6: Chapters 28, 29 (Backtracking, DP) — the two longest, most important chapters. - Day 7: Mock interviews + read Appendix E (Behavioral).

2-week roadmap (already know DSA, refresher): - Week 1: Level 1 (Chapters 1–20) — 3 chapters/day. - Week 2: Level 2 (Chapters 21–32) — 2 chapters/day + mock interviews at the weekend.

6-week roadmap (beginners): - Weeks 1–2: Frontmatter + Level 1 (Ch 1–10) — 1 chapter/day, code every problem yourself. - Weeks 3–4: Level 1 (Ch 11–20) — 1 chapter/day. - Week 5: Level 2 (Ch 21–32) — 2 chapters/day, read patterns carefully. - Week 6: Level 3 (Ch 33–44) — 2 chapters/day, no need to memorise — just know they exist.

Skip if short on time (priority chapters): skip Ch 20 (Prime), Ch 31 (Game Theory), Ch 33–36 (MST / Hash / KMP / Z) — niche patterns, rare in entry/mid-level interviews.

Self-assessment: - Solve Easy in < 30 min each → Level 1 is enough. - Medium in 30–60 min → read up to Level 2. - Hard takes > 60 min or you get stuck often → read all three levels.

⚠️ Do not read the code before planning yourself. The book intentionally places the solution after the “Approach” section — you must struggle with the problem before peeking at the answer; that is how the brain absorbs patterns most effectively.

0.2 The coding interview process (UMPIRE)

UMPIRE = a 6-step framework that keeps you from “freezing” when you receive a new problem:

U — Understand (5 min)

M — Match (2 min)

P — Plan (5 min)

I — Implement (15 min)

R — Review (3 min)

E — Evaluate (2 min)

Mindset tip: the interviewer wants to see your thought process, not a perfect solution on the first try. Think out loud.

0.3 Big-O in 30 minutes

Big-O lecture — Le Chuong — EngineerPro Big-O — EngineerPro

🎥 Companion video lecture on Big-O — presented by Le Chuong, Senior Software Engineer @ Google, instructor from the EngineerPro team. (Vietnamese audio.)

Quick definition

f(n) = O(g(n)) ↔︎ there exists c > 0, n₀ such that f(n) <= c·g(n) for every n >= n₀.

In interviews: drop constants, drop lower-order terms. 3n² + 100n + 5 = O(n²).

“Cheatsheet” table

Notation Name Example
O(1) Constant Hash lookup, push/pop on a stack
O(log n) Logarithmic Binary search
O(n) Linear Single-array scan
O(n log n) Linearithmic Sort, segment-tree build
O(n²) Quadratic Brute-force double loop
O(2^n) Exponential Subset brute force
O(n!) Factorial Permutation brute force

Calculation rules

  1. Sequential (a(); b();): O(a + b), take the max.
  2. Nested loops: O(n × n) = O(n²).
  3. Recursion:
  4. Master theorem for T(n) = aT(n/b) + f(n):

Amortised analysis

Some operations are occasionally slow but on average fast: - Python list.append(): O(1) amortised (despite occasional dynamic resizing). - Hash table with open addressing: O(1) amortised.

Common pitfalls

Practical bounds in interviews

n Acceptable
n ≤ 10 O(n!) brute force
n ≤ 20 O(2^n) bitmask
n ≤ 5000 O(n²) is fine
n ≤ 10^5 O(n log n) or O(n)
n ≤ 10^7 strict O(n)
n ≤ 10^9 O(log n) (search on the answer)

0.4 Python 3 cheat-sheet for interviews

Data structures

# List
lst = [1, 2, 3]
lst.append(x); lst.pop()      # O(1) both
lst.insert(0, x); lst.pop(0)  # O(n) — avoid!
sorted_lst = sorted(lst)      # O(n log n), returns a new list
lst.sort()                    # in-place
lst[::-1]                     # reverse, O(n)
lst[a:b]                      # slicing, O(b-a) copy

# Dict
d = {}; d[k] = v               # O(1) amortised
from collections import defaultdict, Counter
dd = defaultdict(list)
cnt = Counter("anagram")       # {'a':3, 'n':1, 'g':1, 'r':1, 'm':1}
cnt.most_common(2)             # [('a',3), ('n',1)]

# Set
s = {1, 2, 3}
s.add(x); s.discard(x)         # O(1)
s & t; s | t; s - t            # intersection / union / difference

# Deque (double-ended queue) — used for BFS, sliding window
from collections import deque
dq = deque()
dq.append(x); dq.appendleft(x)
dq.pop(); dq.popleft()         # all O(1)

# Heap (min-heap)
import heapq
h = []
heapq.heappush(h, x)
heapq.heappop(h)              # O(log n)
heapq.heapify(lst)            # O(n)
heapq.nsmallest(k, lst)       # O(n log k)

Important idioms

# Enumerate
for i, x in enumerate(lst):
    pass

# Zip
for a, b in zip(lst1, lst2):
    pass

# Comprehension
[x*2 for x in lst if x > 0]
{x: i for i, x in enumerate(lst)}

# Bisect
from bisect import bisect_left, bisect_right
idx = bisect_left(sorted_lst, x)

# Functools
from functools import cache, reduce
@cache
def f(n):
    ...
reduce(lambda a, b: a + b, lst, 0)

# Itertools
from itertools import combinations, permutations, product
list(combinations([1,2,3], 2))    # [(1,2),(1,3),(2,3)]

Pitfalls (CRITICAL — read carefully!)

Arithmetic & division: - dict[k] raises KeyError if k is missing → use dict.get(k, default) or defaultdict. - int / int = float; use // for integer division. - -7 // 2 = -4 (floor), not -3 (truncate toward 0). Truncate via int(-7/2). - -7 % 2 = 1 in Python (always ≥ 0), different from C/C++/Java. Be careful when taking modulo of negative numbers in prefix sums.

Heap & comparison: - Python heapq is only a min-heap. For max-heap, push -x. - Heap compares tuples element-by-element: (priority, idx, payload) — use idx as a tiebreaker when priorities are equal (the payload may not be hashable or comparable, e.g. ListNode). - heappush-ing a tuple whose payload is not comparable (such as ListNode) raises TypeError when priorities collide.

Recursion & cache: - Python’s default recursion limit is around 1000. Use sys.setrecursionlimit(10**6) for large graphs/trees. - Python has no tail-call optimisation → deep recursion can blow the stack. Switch to iterative when n > 10^5. - @functools.cache only works for hashable arguments. list / dict / set cannot be cached; wrap with tuple(...) / frozenset(...). - @cache on a self.method shares a global cache across instances. Use @cached_property if you want per-instance caching.

Mutable defaults & references: - Default mutable argument: def f(x=[]) is a serious bug (every call shares the same list). Use def f(x=None): x = x or []. - result.append(path) appends a reference, not a copy. Use result.append(path.copy()) or result.append(path[:]).

Sort & stability: - Python’s sorted() is Timsort, stable, O(n log n). Take advantage of stability to sort multi-key by sorting multiple times in reverse order. - Custom sort: Python 3 has no cmp= argument. Use key=... or functools.cmp_to_key(...).

Integers & overflow: - Python int is unbounded → no need to worry about overflow like in Java/C++. But explicitly truncate (32-bit) when the problem requires it (LC 7, LC 8, LC 50).

0.5 How to present code on a whiteboard / CoderPad

Golden rules

  1. Think out loud. Silence makes it hard for the interviewer to follow your thought process — they need to hear your reasoning to help when you get stuck, and to evaluate how you approach problems rather than only the final answer.
  2. Start from concrete examples. Draw the input on paper and run the algorithm by hand, step by step.
  3. Code top-down. Write the main def solve(...) first, call helper functions, then implement the helpers afterwards.
  4. Use clear names:
  5. Do not chase brevity. Clear code matters more than a “clever” one-liner.

When stuck

After finishing

Demeanor during the interview

Sample phrases per stage

Stage Sample phrase
Clarify “Let me confirm the problem: input is …, output is …, any additional constraints?”
Brute force “To start, here is the direct approach: enumerate every pair — O(n²)…”
Optimise “I think we can use a hash map to reduce each lookup to O(1)…”
Stuck “I am torn between a hash map and a sorted array. Do you have any hint?”
Done “The solution runs in O(n) time and O(n) space. Let me try a few edge cases…”

Chapter 1 — Array

Array is the most fundamental data structure and also the pattern that shows up most often in Big Tech coding interviews. Most techniques in later chapters (two pointers, sliding window, prefix sum, monotonic stack, …) originate from array manipulation. The goal of this chapter is to master in-place and two-pass operations and to start cultivating the habit of “thinking in terms of indices, not values”.

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

Template code

from typing import List

def two_pass_pattern(nums: List[int]) -> List[int]:
    """Two-pass template: pass 1 collects information, pass 2 uses it."""
    n = len(nums)
    aux = [0] * n
    # pass 1: compute prefix / suffix / count
    for i in range(n):
        aux[i] = ...   # problem-specific
    # pass 2: use aux to produce the result
    out = [0] * n
    for i in range(n):
        out[i] = ...   # problem-specific
    return out


def two_pointers_in_place(nums: List[int]) -> int:
    """Two-pointer in-place: slow = write position, fast = read position."""
    slow = 0
    for fast in range(len(nums)):
        if condition(nums[fast]):
            nums[slow] = nums[fast]
            slow += 1
    return slow  # length of the "valid" compacted prefix

End-of-chapter practice

1.1 Two Sum (LC 1)

Problem

You are given an integer array nums and an integer target. Return the indices of the two elements in nums whose sum equals target.

You may assume each input has exactly one solution, and you cannot use the same element twice.

Example

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] == 9.

Constraints

Clarifying questions

Approach

Brute force — O(n²). Enumerate every pair (i, j) with i < j and check nums[i] + nums[j] == target. Easy to write but TLEs for large n.

Optimal — one-pass hash map — O(n). When we are at index i, we need to know whether some j < i satisfies nums[j] == target - nums[i]. Use a dict storing {value: index} of elements we have already seen.

Presentation tip: Always start with brute force, state its complexity explicitly, then say: “I think we can replace the linear O(n) lookup with an O(1) hash-map lookup, which brings the total cost down from O(n²) to O(n)…” — interviewers love this flow of reasoning.

Code (Python 3)

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen: dict[int, int] = {}
        for i, x in enumerate(nums):
            complement = target - x
            if complement in seen:
                return [seen[complement], i]
            seen[x] = i
        return []  # per the problem statement this line never executes

Complexity

Comments

1.2 Best Time to Buy and Sell Stock (LC 121)

Problem

Given an array prices where prices[i] is the stock price on day i, you are allowed to buy once then sell once afterwards (you cannot sell before you buy). Return the maximum profit, or 0 if no transaction is profitable.

Example

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: buy on day 2 (price 1), sell on day 5 (price 6); profit = 6 - 1 = 5.

Input:  prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: prices only decrease; no profitable transaction exists.

Constraints

Clarifying questions

Approach

Brute force — O(n²). Try every (i, j) with i < j and take max(prices[j] - prices[i]). TLE at n = 10^5.

Optimal — one pass, O(n). If we decide “we will sell today on day i”, the best profit is prices[i] - min(prices[0..i-1]). So we just maintain min_so_far as we sweep and update best at every step.

Illustration for prices = [7, 1, 5, 3, 6, 4]:

day        :   0    1    2    3    4    5
prices     :   7    1    5    3    6    4
                    │              │
                    │ buy here     │ sell here
                    ▼              ▼
min_so_far :   7    1    1    1    1    1
profit_now :   0    0    4    2    5    3   (= prices[i] - min_so_far)
best       :   0    0    4    4    5    5   ← answer = 5
                              ▲
                              unchanged since 2 < 4

Mindset: this is a DP in one variable. The state min_so_far is the O(1)-space compression of dp[i] = min(prices[0..i]) — a technique you will see repeatedly in the DP chapters.

Code (Python 3)

from typing import List
import math

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_so_far = math.inf
        best = 0
        for p in prices:
            min_so_far = min(min_so_far, p)
            best = max(best, p - min_so_far)
        return best

Complexity

Comments

1.3 Product of Array Except Self (LC 238)

Problem

Given an array nums of n integers, return an array answer of the same length such that answer[i] is the product of all elements of nums except nums[i].

Special constraints: - Division is not allowed. - The algorithm must run in O(n) time.

Example

Input:  nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation:
  answer[0] = 2*3*4 = 24
  answer[1] = 1*3*4 = 12
  answer[2] = 1*2*4 = 8
  answer[3] = 1*2*3 = 6

Input:  nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]

Constraints

Clarifying questions

Approach

Brute force — O(n²). For each i, recompute the product of the rest of the array. The problem already bans this.

Division — O(n) but not allowed. Compute total = product(nums) then answer[i] = total / nums[i]. Forbidden because nums[i] = 0 breaks it; and many languages lack exact integer division.

Optimal — Prefix × Suffix products — O(n) time, O(1) extra space (output excluded).

Observation: answer[i] = (∏ nums[0..i-1]) * (∏ nums[i+1..n-1]). Define: - left[i] = product of nums[0..i-1] (left product, left[0] = 1). - right[i] = product of nums[i+1..n-1] (right product, right[n-1] = 1). Then answer[i] = left[i] * right[i].

To reach O(1) extra space, reuse answer: - Pass 1 (left → right): fill answer[i] = left[i]. - Pass 2 (right → left): multiply answer[i] *= right, updating the rolling variable right as we go.

Illustration for nums = [1, 2, 3, 4]:

              i=0     i=1     i=2     i=3
nums      :  [  1  ,   2  ,   3  ,   4  ]

                 ┌─────────────┐
                 │  prefix →   │   (product of elements LEFT of i)
                 ▼             ▼
left[i]   :  [  1  ,   1  ,   2  ,   6  ]
              (empty)(1)   (1·2) (1·2·3)

                         ┌─────────────┐
                         │   ← suffix  │   (product of elements RIGHT of i)
                         ▼             ▼
right[i]  :  [ 24  ,  12  ,   4  ,   1  ]
            (2·3·4)(3·4)  (4)   (empty)

                         ↓  pointwise multiplication  ↓

answer[i] :  [ 24  ,  12  ,   8  ,   6  ]
              1·24   1·12   2·4    6·1

In real code we do not keep both left and right arrays — we use answer for the prefix pass, then a single rolling right variable swept right-to-left to multiply into answer in place.

Code (Python 3)

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n

        # Pass 1: answer[i] = product of elements left of i.
        left = 1
        for i in range(n):
            answer[i] = left
            left *= nums[i]

        # Pass 2: multiply by the right-side product, using a rolling variable.
        right = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= right
            right *= nums[i]

        return answer

Complexity

Comments

1.4 Move Zeroes (LC 283)

Problem

Given an array nums, move all zeros to the end of the array while preserving the relative order of the non-zero elements. Do it in place; you may not create an auxiliary array.

Example

Input:  nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Input:  nums = [0]
Output: [0]

Constraints

Clarifying questions

Approach

Brute force — O(n) time, O(n) extra space. Build an auxiliary array of non-zero values and pad with zeros to length n. The problem forbids auxiliary arrays — rejected.

Optimal — Two pointers — O(n) time, O(1) extra space. Use two pointers: - slow = the next index to write a non-zero value. - fast = the index currently being read.

Pass 1: for each fast, if nums[fast] != 0 → nums[slow] = nums[fast], then increment slow. Pass 2: from slow to the end of the array, write 0.

Illustration for nums = [0, 1, 0, 3, 12]:

                    Pass 1: pack non-zero values to the front
                    ──────────────────────────────────────────

Initial  :  [ 0 , 1 , 0 , 3 , 12]      slow=0  fast=0
              S
              F

fast=0:  nums[0]=0, skip
         [ 0 , 1 , 0 , 3 , 12]         slow=0  fast=1
           S
               F

fast=1:  nums[1]=1 != 0 → write nums[0]=1, slow++
         [ 1 , 1 , 0 , 3 , 12]         slow=1  fast=2
               S
                   F

fast=2:  nums[2]=0, skip                slow=1  fast=3
fast=3:  nums[3]=3 != 0 → write nums[1]=3, slow++
         [ 1 , 3 , 0 , 3 , 12]         slow=2  fast=4
                   S
                       F

fast=4:  nums[4]=12 != 0 → write nums[2]=12, slow++
         [ 1 , 3 ,12 , 3 , 12]         slow=3  fast=done

                    Pass 2: from slow to end, write 0
                    ──────────────────────────────────────────

         [ 1 , 3 ,12 , 0 , 0 ]    ← answer
                       ▲   ▲
                   write 0  write 0

This approach minimises the number of writes to exactly n (each cell is written at most once). A swap-as-you-go variant exists with shorter code but twice as many writes.

Code (Python 3)

from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        slow = 0
        # Pass 1: pack non-zero values to the front.
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
        # Pass 2: fill the tail with zeros.
        for i in range(slow, len(nums)):
            nums[i] = 0

Complexity

Comments

slow = 0
for fast in range(len(nums)):
    if nums[fast] != 0:
        nums[slow], nums[fast] = nums[fast], nums[slow]
        slow += 1

1.5 Container With Most Water (LC 11)

Problem

Given an array height where height[i] is the height of the i-th pole, choose two poles i < j such that the water held between them is maximal.

Water volume = min(height[i], height[j]) * (j - i).

Example

Input:  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: choose poles 1 (height 8) and 8 (height 7) → 7 * (8-1) = 49.

Input:  height = [1, 1]
Output: 1

Constraints

Clarifying questions

Approach

Brute force — O(n²). Try every (i, j) and take the max. TLE for n = 10^5.

Optimal — Two pointers, O(n). Set l = 0, r = n - 1. The current area is min(height[l], height[r]) * (r - l).

Core question: which pointer do we move? — Move the pointer at the shorter side.

Why? The area is bounded by the shorter pole. Moving the taller pointer inward shrinks the width while the shorter pole is still the bottleneck → the area can only stay the same or decrease. Moving the shorter pointer at least gives us a chance (no guarantee) to find a taller pole, which can lift the bottleneck.

“Elimination” proof: Fixing the shorter pole (say the left one) and moving the right pointer inward, every pair (l, r' < r) has area ≤ height[l] * (r - l). None of those pairs can beat the current area unless they were already going to lose to the current best — we can “eliminate” all of them at once and only need to move l.

Illustration for height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

         ▓                                ▓
   8     ▓       ▓                        |          ← height 8
   7     ▓       ▓                        ▓
   6     ▓   ▓   ▓               ▓        ▓
   5     ▓   ▓   ▓       ▓       ▓        ▓
   4     ▓   ▓   ▓       ▓   ▓   ▓        ▓
   3     ▓   ▓   ▓       ▓   ▓   ▓    ▓   ▓
   2     ▓   ▓   ▓   ▓   ▓   ▓   ▓    ▓   ▓
   1 ▓   ▓   ▓   ▓   ▓   ▓   ▓   ▓    ▓   ▓
       └─┴───┴───┴───┴───┴───┴───┴────┴───┴─
index: 0   1   2   3   4   5   6    7   8
       L                                  R

Trace (★ = best so far):

  step │  L   R │ min(h[L], h[R]) │ width │  area │ move
  ─────┼────────┼─────────────────┼───────┼───────┼──────────────
   1   │  0   8 │       1         │   8   │    8  │ h[L]<h[R] → L++
   2   │  1   8 │       7         │   7   │  49 ★ │ h[L]>=h[R] → R--
   3   │  1   7 │       3         │   6   │   18  │ → R--
   4   │  1   6 │       8         │   5   │   40  │ → R--
   5   │  1   5 │       4         │   4   │   16  │ → R--
   6   │  1   4 │       5         │   3   │   15  │ → R--
   7   │  1   3 │       2         │   2   │    4  │ → R--
   8   │  1   2 │       6         │   1   │    6  │ → R--
   ─── │  1   1 │       stop      │       │       │

Answer: 49 (pair of pole index 1 and 8, heights 8 and 7).

Code (Python 3)

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        best = 0
        while l < r:
            h = min(height[l], height[r])
            best = max(best, h * (r - l))
            # Always move the pointer on the shorter side.
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return best

Complexity

Comments

1.6 Rotate Array (LC 189)

Problem

Given an array nums and a non-negative integer k, rotate the array to the right by k steps.

Example

Input:  nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]
Explanation: 1-step right → [7,1,2,3,4,5,6]; 2-step → [6,7,1,2,3,4,5]; 3-step → [5,6,7,1,2,3,4].

Input:  nums = [-1, -100, 3, 99], k = 2
Output: [3, 99, -1, -100]

Constraints

Clarifying questions

Approach

Brute force — rotate by one step, repeated k times — O(n·k). TLE.

Auxiliary array — O(n) time, O(n) space. new[(i + k) % n] = nums[i], then copy new back to nums. Simple but violates the O(1)-space follow-up.

Optimal — Three reverses, O(n) time, O(1) extra space. Look at n = 7, k = 3: - Reverse the whole array: [7, 6, 5, 4, 3, 2, 1]. - Reverse [0..k-1]: [5, 6, 7, 4, 3, 2, 1]. - Reverse [k..n-1]: [5, 6, 7, 1, 2, 3, 4]. ✓

Intuition: the full reverse brings the elements that “should end up at the beginning” to the front, but each block is locally backwards. The two inner reverses fix the order inside each block.

Illustration for n = 7, k = 3:

Input         :  [ 1   2   3   4 │ 5   6   7 ]
                                  ▲
                  the last k=3 elements must "jump" to the front

──────────────────────────────────────────────────

Step 1: reverse the whole array [0..6]
                  ◀═══════════════════════════▶
                 [ 7   6   5   4   3   2   1 ]
                   ↑               ↑
                  (5,6,7 reversed) (1,2,3,4 reversed)

Step 2: reverse [0..k-1] = [0..2]   (fix the first 3 elements)
                  ◀═══════▶
                 [ 5   6   7 │ 4   3   2   1 ]
                                ↑
                  first 3 fixed; last 4 still backwards

Step 3: reverse [k..n-1] = [3..6]   (fix the last 4 elements)
                              ◀═══════════════▶
                 [ 5   6   7 │ 1   2   3   4 ]   ← answer ✓

Code (Python 3)

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n  # always normalise first

        def reverse(left: int, right: int) -> None:
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        reverse(0, n - 1)        # reverse everything
        reverse(0, k - 1)        # reverse the first k elements
        reverse(k, n - 1)        # reverse the rest

Complexity

Comments

Chapter summary & decisions

Array decision checklist (before you start coding)

Question If YES If NO
May we mutate the input? In-place (Move Zeroes, Rotate) Allocate a result array
Must we preserve the original order? Same-direction two-pointer Free to swap anywhere
Return index or value? Be careful when sorting: keep (value, index) —
Are there zeros / negatives? Product-Except-Self cannot use division Plain prefix × suffix is fine
Need O(1) memory? 3-reverse trick, in-place markers Hashes / aux arrays are fine

Gateway to other patterns

Rotate Array recap — three approaches compared

Approach Time Space When to choose
Extra array O(n) O(n) Easiest to write, fewest bugs; when RAM is plentiful
3-reverse O(n) O(1) Default for interviews — elegant and short
Cyclic replacement (GCD) O(n) O(1) When the interviewer asks for a “no-reverse” follow-up

Chapter 2 — String

A string is really an array of characters — every technique from Chapter 1 (two pointers, in-place, prefix) applies. Strings, however, have two specific quirks: (i) you must handle the character set (ASCII or full Unicode?) and (ii) in Python, strings are immutable — you cannot mutate them in place; every “character swap” must go through a list followed by ''.join.

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

Template code

from collections import Counter
from typing import List

def two_pointers_in_string(s: str) -> bool:
    """Two-pointer template: check a symmetric / pairwise condition."""
    l, r = 0, len(s) - 1
    while l < r:
        if not check(s[l], s[r]):
            return False
        l += 1
        r -= 1
    return True


def count_chars(s: str) -> dict[str, int]:
    """Character frequency table — used by almost every string problem."""
    return Counter(s)

End-of-chapter practice

2.1 Valid Anagram (LC 242)

Problem

Given two strings s and t, return True if t is an anagram of s (same characters with the same counts, possibly in different order), otherwise False.

Example

Input:  s = "anagram", t = "nagaram"
Output: True

Input:  s = "rat", t = "car"
Output: False

Constraints

Clarifying questions

Approach

Brute force — sort, O(n log n). sorted(s) == sorted(t). One-liner, but O(n log n) time and O(n) space (because sorted returns a list).

Optimal — single-pass Counter, O(n). Count the characters of s, then sweep t decrementing. If any count goes negative — not an anagram. Final state must be all zeros.

Even faster — fixed 26-element table, O(1) extra space (alphabet dependent). With only 26 letters we can use int[26] (or a length-26 list) instead of a dict. Memory is genuinely O(1) (independent of n).

Code (Python 3)

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return Counter(s) == Counter(t)


class SolutionFast:
    """Fixed 26-letter table — true O(1) memory."""
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1
        for ch in t:
            count[ord(ch) - ord('a')] -= 1
            if count[ord(ch) - ord('a')] < 0:
                return False
        return True

Complexity

Comments

2.2 Valid Palindrome (LC 125)

Problem

Given a string s, consider it a palindrome if, after converting all letters to lowercase and removing every non-alphanumeric character, it reads the same forwards and backwards. Return True / False.

Example

Input:  s = "A man, a plan, a canal: Panama"
Output: True
Explanation: filtered → "amanaplanacanalpanama" — reads identically both ways.

Input:  s = "race a car"
Output: False
Explanation: filtered → "raceacar" — not a palindrome.

Input:  s = " "
Output: True
Explanation: an empty filtered string is considered a palindrome.

Constraints

Clarifying questions

Approach

Brute force — filter then compare reversed — O(n) time, O(n) space. filtered = ''.join(ch.lower() for ch in s if ch.isalnum()), then filtered == filtered[::-1]. Simple but uses O(n) extra memory.

Optimal — Two pointers in place — O(n) time, O(1) space. Use two pointers l (left) and r (right). On each side, skip non-alphanumeric characters, then compare s[l].lower() == s[r].lower(). Mismatch → return False.

Code (Python 3)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True

Complexity

Comments

2.3 Longest Common Prefix (LC 14)

Problem

Given an array of strings strs, return the longest common prefix. If none exists, return "".

Example

Input:  strs = ["flower", "flow", "flight"]
Output: "fl"

Input:  strs = ["dog", "racecar", "car"]
Output: ""
Explanation: no character is shared at position 0.

Constraints

Clarifying questions

Approach

Approach 1 — Vertical scan, O(S) where S is the total length. Iterate column-by-column i = 0, 1, 2, .... At each i, check whether strs[0][i] equals strs[j][i] for every j. If a string runs out or a mismatch occurs → return strs[0][:i].

Approach 2 — Horizontal scan. Take prefix = strs[0], then for each subsequent string, shrink prefix until it is a prefix of that string.

Approach 3 — Sort + compare endpoints, O(n log n · L). Sort lexicographically. The longest common prefix equals the common prefix of strs[0] and strs[-1]. Cute but not time-optimal.

We recommend vertical scan because it is easiest to present on a whiteboard and supports early-exit on the first mismatch.

Code (Python 3)

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        for i, ch in enumerate(strs[0]):
            for s in strs[1:]:
                if i >= len(s) or s[i] != ch:
                    return strs[0][:i]
        return strs[0]  # all of strs[0] is a common prefix

Complexity

Comments

2.4 String to Integer / atoi (LC 8)

Problem

Implement atoi (ASCII to Integer), converting a string into a signed 32-bit integer. Rules:

  1. Skip leading whitespace.
  2. Read an optional + or - sign.
  3. Read consecutive digit characters until a non-digit is reached.
  4. Apply the sign to the result.
  5. Clamp to the range of int 32-bit: [-2^31, 2^31 - 1].
  6. Return 0 if no digits were read (e.g. the string is entirely letters).

Example

Input:  s = "42"
Output: 42

Input:  s = "   -42"
Output: -42                (skip leading spaces, read '-', then "42")

Input:  s = "4193 with words"
Output: 4193               (stop at the whitespace after "4193")

Input:  s = "words and 987"
Output: 0                  (we hit 'w' immediately — no digits read)

Input:  s = "-91283472332"
Output: -2147483648        (= INT_MIN, clamped because the number is too small)

Input:  s = "+-12"
Output: 0                  (already consumed '+', then '-' is non-digit → fail)

Constraints

Clarifying questions

Approach

Approach 1 — Sequential procedure with an index walker. Four clear steps: skip space → read sign → read digits → clamp. Each step maintains its own state variables.

Approach 2 — Finite State Machine (FSM). A state machine yields concise code and is easy to extend when the problem adds requirements (decimals, scientific notation, …). Highly worth learning since it is the canonical pattern for any parser problem (Chapter 32).

FSM diagram:

       blank        sign        digit       other
   ┌───────────────────────────────────────────────┐
S  │  start  →  start    signed   in_number   end │
T  │  signed →  end      end      in_number   end │
A  │ in_num  →  end      end      in_number   end │
T  │  end    →  end      end      end         end │
E  └───────────────────────────────────────────────┘

States:
  start     : still skipping leading spaces
  signed    : sign already read, awaiting digits
  in_number : currently consuming digits
  end       : finished; remaining characters are ignored

Code (Python 3)

INT_MAX = 2**31 - 1   # 2147483647
INT_MIN = -2**31      # -2147483648

class Solution:
    """Approach 1 — sequential procedure."""

    def myAtoi(self, s: str) -> int:
        i, n = 0, len(s)

        # 1. Skip leading whitespace.
        while i < n and s[i] == ' ':
            i += 1

        # 2. Optional sign.
        sign = 1
        if i < n and s[i] in '+-':
            sign = -1 if s[i] == '-' else 1
            i += 1

        # 3. Read digits.
        result = 0
        while i < n and s[i].isdigit():
            result = result * 10 + (ord(s[i]) - ord('0'))
            # Optimisation: clamp early to avoid running too long.
            if result > 2**31:
                break
            i += 1

        # 4. Apply sign and clamp.
        result *= sign
        return max(INT_MIN, min(INT_MAX, result))


class SolutionFSM:
    """Approach 2 — Finite State Machine. Easy to extend later."""

    table = {
        'start':     {'blank': 'start',  'sign': 'signed',   'digit': 'in_num', 'other': 'end'},
        'signed':    {'blank': 'end',    'sign': 'end',      'digit': 'in_num', 'other': 'end'},
        'in_num':    {'blank': 'end',    'sign': 'end',      'digit': 'in_num', 'other': 'end'},
        'end':       {'blank': 'end',    'sign': 'end',      'digit': 'end',    'other': 'end'},
    }

    @staticmethod
    def _kind(ch: str) -> str:
        if ch == ' ':           return 'blank'
        if ch in '+-':          return 'sign'
        if ch.isdigit():        return 'digit'
        return 'other'

    def myAtoi(self, s: str) -> int:
        state = 'start'
        sign = 1
        result = 0
        for ch in s:
            state = self.table[state][self._kind(ch)]
            if state == 'in_num':
                result = result * 10 + int(ch)
                result = min(result, INT_MAX + 1)  # early-clamp
            elif state == 'signed':
                sign = -1 if ch == '-' else 1
            elif state == 'end':
                break
        return max(INT_MIN, min(INT_MAX, sign * result))

Complexity

Comments

2.5 Group Anagrams (LC 49)

Problem

Given an array of strings strs, group strings that are anagrams of one another. Return the list of groups (the order of groups and the order within each group does not matter).

Example

Input:  strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Constraints

Clarifying questions

Approach

Core idea: two strings are anagrams ↔︎ they share the same “signature”. Use a dict {signature: [strings]} to bucket them.

Approach 1 — signature = sorted(s), O(n · k log k). key = ''.join(sorted(s)). Anagrams share the same sorted form.

Approach 2 — signature = tuple of 26 counts, O(n · k). key = tuple(Counter(s)[ch] for ch in 'abcdefghijklmnopqrstuvwxyz'). Avoids the O(k log k) sort, at the cost of a length-26 tuple overhead.

Illustration for ["eat", "tea", "tan", "ate", "nat", "bat"]:

str    sorted_key   bucket
─────  ───────────  ─────────────────────
"eat"   "aet"  ──┐
"tea"   "aet"  ──┤───►  bucket "aet" = ["eat", "tea", "ate"]
"ate"   "aet"  ──┘
"tan"   "ant"  ──┐
"nat"   "ant"  ──┤───►  bucket "ant" = ["tan", "nat"]
"bat"   "abt"  ──────►  bucket "abt" = ["bat"]

Code (Python 3)

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups: dict[str, list[str]] = defaultdict(list)
        for s in strs:
            key = ''.join(sorted(s))
            groups[key].append(s)
        return list(groups.values())


class SolutionCount:
    """Signature = tuple of 26 counts — no sort needed."""

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups: dict[tuple, list[str]] = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for ch in s:
                count[ord(ch) - ord('a')] += 1
            groups[tuple(count)].append(s)
        return list(groups.values())

Complexity

Approach Time Space
sorted-key O(n · k log k) O(n·k)
count-key O(n · k) O(n·k)

where n = number of strings, k = string length.

Comments

2.6 Reverse Words in a String (LC 151)

Problem

Given a string s containing multiple words separated by at least one space, reverse the order of words and return the result such that:

Example

Input:  s = "the sky is blue"
Output: "blue is sky the"

Input:  s = "  hello world  "
Output: "hello world"   (compress leading/trailing + inner)

Input:  s = "a good   example"
Output: "example good a"   (collapse multiple inner spaces into one)

Constraints

Clarifying questions

Approach

Approach 1 — Pythonic split-reverse-join, O(n). return ' '.join(reversed(s.split())). s.split() with no argument automatically collapses runs of whitespace and drops leading / trailing spaces — exactly what we need.

Approach 2 — Three Reverses (in place on a character array). Apply the same idea as Rotate Array (problem 1.6): 1. Reverse the entire string. 2. Reverse each “word” inside the reversed string. 3. Clean up spaces (keep only one space between words; remove leading / trailing).

Illustration for s = "the sky is blue":

Input               :  "the sky is blue"

Step 1: reverse the whole string
                       "eulb si yks eht"

Step 2: reverse each word inside the reversed string
                       "blue is sky the"   ← answer ✓

Comparison with Rotate Array: Rotate Array reverses at the granularity of individual elements; Reverse Words reverses at the granularity of words (substrings between spaces). Same idea, different abstraction level.

Code (Python 3)

class Solution:
    """Approach 1 — Pythonic, shortest."""

    def reverseWords(self, s: str) -> str:
        return ' '.join(reversed(s.split()))


class SolutionInPlace:
    """Approach 2 — three reverses, in place on a character list."""

    def reverseWords(self, s: str) -> str:
        chars = list(s.strip())  # Python strings are immutable → convert to list

        # 1. Reverse the entire array.
        self._reverse(chars, 0, len(chars) - 1)

        # 2. Reverse each word.
        start = 0
        for i in range(len(chars) + 1):
            if i == len(chars) or chars[i] == ' ':
                self._reverse(chars, start, i - 1)
                start = i + 1

        # 3. Collapse multiple spaces between words.
        return self._collapse_spaces(chars)

    @staticmethod
    def _reverse(arr: list, l: int, r: int) -> None:
        while l < r:
            arr[l], arr[r] = arr[r], arr[l]
            l += 1
            r -= 1

    @staticmethod
    def _collapse_spaces(chars: list) -> str:
        out, prev_space = [], False
        for ch in chars:
            if ch == ' ':
                if not prev_space and out:
                    out.append(' ')
                prev_space = True
            else:
                out.append(ch)
                prev_space = False
        if out and out[-1] == ' ':
            out.pop()
        return ''.join(out)

Complexity

Comments

Chapter summary & decisions

Character assumptions — clarify them before you write code

  1. Alphabet: lowercase a–z (26)? ASCII 128? Unicode? — The [26] counting array only works when the alphabet is exactly 26 letters.
  2. Case sensitivity? — is "Aa" a palindrome? LC 125 lowercases first; LC 5 does not.
  3. Non-alphanumeric characters? — Filter with isalnum(), or does the problem guarantee a clean input?
  4. Leading / trailing whitespace? — Call strip() before parsing numbers.

String pattern map

Pattern When to use Chapter
Counting (Counter, [26]) Anagrams, frequency 02, 06
Two pointers (in / out) Palindrome, reverse 02, 26
Sliding window Substring under a dynamic constraint 27
Parsing with stack / FSM atoi, calculator, Decode 08, 32
Pattern matching strStr, anagrams in text 35, 36, 34
String hashing Rabin-Karp, distinct substrings 34

Group Anagrams — how to choose the key?

Bridge to Chapter 32 (String Parser)

LC 8 (atoi) is a small FSM with 4 states: start, sign, digits, overflow. When problems get more complex (Valid Number, Calculator) → see Chapter 32.

Chapter 3 — Recursion

Recursion is the natural language for problems with a self-similar structure — solving a large problem by combining the solutions of a few smaller subproblems. This chapter teaches you to feel the three components of a recursive solution: (i) the base case (stopping condition), (ii) the recursive case (calling smaller subproblems), (iii) the combination of subproblem results. Once these three click, you will see DP, Backtracking, Trees, and Graph DFS as dialects of the same language.

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

Three questions to answer before coding any recursion: 1. What variables make up the state of the function? (Enough to fully define a subproblem.) 2. What is the base case? (When do we return immediately?) 3. What does the recursive step look like — how do we split the problem and combine the results?

Template code

from functools import cache

# 1) "Pure" recursion (can be slow because subproblems repeat).
def recurse(state):
    if base_condition(state):
        return base_value
    result = combine(recurse(subproblem_1(state)),
                     recurse(subproblem_2(state)))
    return result


# 2) Top-down DP: cache for O(#states) total work.
@cache
def f(*state):
    if base_condition(*state):
        return base_value
    return combine(f(*sub1(*state)), f(*sub2(*state)))


# 3) Backtracking: enumerate + undo.
def backtrack(path, choices):
    if is_solution(path):
        results.append(path.copy())
        return
    for c in choices:
        if not valid(c, path):
            continue
        path.append(c)
        backtrack(path, next_choices(choices, c))
        path.pop()              # undo — the signature of backtracking

End-of-chapter practice

3.1 Fibonacci Number (LC 509)

Problem

Compute the n-th Fibonacci number, defined by F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n >= 2.

Example

Input:  n = 2  → 1
Input:  n = 3  → 2
Input:  n = 10 → 55

Constraints

Clarifying questions

Approach

Approach 1 — Pure recursion, O(2^n). Each F(n) triggers two recursive calls. The call tree has ~2^n nodes → very slow.

Approach 2 — Memoisation (top-down DP), O(n) time, O(n) space. Cache results → each F(k) is computed exactly once.

Approach 3 — Iterative (bottom-up), O(n) time, O(1) space. Keep two rolling variables prev, curr.

Approach 4 — Matrix exponentiation, O(log n). When n reaches 10^18.

Illustration — call tree for F(5):

                F(5)
              /      \
          F(4)        F(3)
         /    \      /    \
       F(3)  F(2) F(2)   F(1)
       /  \   / \  / \
     F(2) F(1)...   ...   ← F(3), F(2), F(1) are RECOMPUTED many times

→ With memoisation, only n+1 unique calls are made (n=5 → 6 calls).
→ Without memoisation, total calls ~ Fibonacci(n+1) ~ φ^n (exponential).

Code (Python 3)

from functools import cache

class Solution:
    """Approach 3 — iterative O(1) space, the production answer."""
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        prev, curr = 0, 1
        for _ in range(2, n + 1):
            prev, curr = curr, prev + curr
        return curr


class SolutionMemo:
    """Approach 2 — top-down DP."""
    @cache
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        return self.fib(n - 1) + self.fib(n - 2)


class SolutionMatrix:
    """Approach 4 — matrix exponentiation, O(log n)."""
    MOD = 10**9 + 7

    def fib(self, n: int) -> int:
        if n < 2:
            return n
        # [[F(n+1), F(n)], [F(n), F(n-1)]] = [[1,1],[1,0]] ^ n
        result, base = [[1, 0], [0, 1]], [[1, 1], [1, 0]]
        while n > 0:
            if n & 1:
                result = self._mul(result, base)
            base = self._mul(base, base)
            n >>= 1
        return result[0][1]  # F(n)

    def _mul(self, a, b):
        return [[(a[0][0]*b[0][0] + a[0][1]*b[1][0]) % self.MOD,
                 (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % self.MOD],
                [(a[1][0]*b[0][0] + a[1][1]*b[1][0]) % self.MOD,
                 (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % self.MOD]]

Complexity

Comments

3.2 Power(x, n) (LC 50)

Problem

Implement a function that computes x^n where x is a real number and n is an integer (possibly negative).

Example

Input:  x = 2.00000, n = 10     → 1024.00000
Input:  x = 2.10000, n = 3      → 9.26100
Input:  x = 2.00000, n = -2     → 0.25

Constraints

Clarifying questions

Approach

Approach 1 — Multiply by hand, O(n). Loop n times. TLEs at n = 2^31.

Approach 2 — Fast Power (recursive / iterative), O(log n).

Recursive observation: - If n == 0: return 1. - If n is even: x^n = (x^(n/2))^2. - If n is odd: x^n = x · x^(n-1).

Handling negative n: recurse with -n then invert.

Illustration — call tree for x^10:

                  x^10
                   │ even → (x^5)^2
                   ▼
                  x^5
                   │ odd  → x · x^4
                   ▼
                  x^4
                   │ even → (x^2)^2
                   ▼
                  x^2
                   │ even → (x^1)^2
                   ▼
                  x^1
                   │ odd  → x · x^0
                   ▼
                  x^0 = 1

Total multiplications: ~ 2 log₂(10) ≈ 8  (vs. 10 for brute force)

Code (Python 3)

class Solution:
    """Recursive fast power."""

    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1.0
        if n < 0:
            return 1.0 / self.myPow(x, -n)
        half = self.myPow(x, n // 2)
        return half * half if n % 2 == 0 else half * half * x


class SolutionIter:
    """Iterative — avoids recursion depth. Reads bits from low to high."""

    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x, n = 1.0 / x, -n
        result = 1.0
        base = x
        while n > 0:
            if n & 1:
                result *= base
            base *= base
            n >>= 1
        return result

Complexity

Comments

3.3 Reverse Linked List (recursive) (LC 206)

Problem

Given the head of a singly linked list, reverse the list and return the new head. (There are two classic approaches: iterative and recursive. This chapter focuses on the recursive version; the iterative version returns in Chapter 7.)

Example

Input:  head = 1 → 2 → 3 → 4 → 5 → None  (singly linked list)
Output: 5 → 4 → 3 → 2 → 1 → None

Input:  head = None     (empty list)
Output: None

Constraints

Clarifying questions

Approach

Recursive idea: - Base case: if head is None or head.next is None → return head. - Recursive step: call reverseList(head.next) to reverse the tail; we receive the new last node (which is the original tail → the new head of the reversed list). - Combination: at this point head.next still points to the original node right after head (recursion only operated on the tail). Set head.next.next = head and head.next = None to stitch head to the end of the reversed list.

Illustration with 1 → 2 → 3 → None:

Call reverseList(1):
  reverseList(2):
    reverseList(3):
      base case → return 3              #  3 → None
    # here head=2, head.next=3
    # tail is reversed: 3 → None
    # stitch 2 after 3:
    head.next.next = head                #  3 → 2
    head.next = None                     #  2 → None
    # chain so far: 3 → 2 → None, new head = 3
    return 3
  # here head=1, head.next=2
  # tail is reversed: 3 → 2 → None
  # stitch 1 after 2:
  head.next.next = head                  #  2 → 1
  head.next = None                       #  1 → None
  # chain: 3 → 2 → 1 → None
  return 3

Code (Python 3)

class ListNode:
    def __init__(self, val: int = 0, next: 'ListNode | None' = None):
        self.val = val
        self.next = next


class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        if head is None or head.next is None:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

Complexity

Comments

prev = None
while head:
    nxt = head.next
    head.next = prev
    prev = head
    head = nxt
return prev

3.4 Generate Parentheses (LC 22)

Problem

Given an integer n, generate all well-formed parenthesis strings of length 2n.

Example

Input:  n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Input:  n = 1
Output: ["()"]

Constraints

Clarifying questions

Approach

Idea: generate the characters ( and ) one at a time. Each step has 2 choices, constrained by validity: - Number of ( placed must not exceed n. - Number of ) placed must not exceed the number of ( placed (otherwise an unmatched close-paren appears).

Recurse with two counters: open_count, close_count. When len(path) == 2n → push to results.

Illustration — decision tree for n = 2:

                       ""
                     /    \
                ( /        \ )  ✗ (close > open)
                   "("
                  /   \
              ( /      \ )
              "(("    "()"
               │        │
            ) ▼     ( / \ )  ✗
              "(()"   "()("
               │       │
            ) ▼     ) ▼
              "(())" ★  "()()" ★

Answer: ["(())", "()()"]
(✗ = branch pruned because invalid)

Code (Python 3)

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result: list[str] = []

        def backtrack(path: list[str], open_cnt: int, close_cnt: int) -> None:
            if len(path) == 2 * n:
                result.append(''.join(path))
                return
            if open_cnt < n:
                path.append('(')
                backtrack(path, open_cnt + 1, close_cnt)
                path.pop()
            if close_cnt < open_cnt:
                path.append(')')
                backtrack(path, open_cnt, close_cnt + 1)
                path.pop()

        backtrack([], 0, 0)
        return result

Complexity

Comments

3.5 Permutations (LC 46)

Problem

Given an array nums of distinct integers, return all possible permutations of them.

Example

Input:  nums = [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Constraints

Clarifying questions

Approach

Idea: at each step, pick an unused number and push it into path. When path reaches n elements → record one complete permutation.

Two ways to track “used”: - A used: bool[n] array. - A set of used indices.

Illustration — decision tree for [1, 2, 3]:

                          [ ]
              ┌────────────┼────────────┐
            [1]           [2]          [3]
           /   \         /   \         /  \
        [1,2] [1,3]   [2,1] [2,3]   [3,1] [3,2]
          │     │       │     │       │     │
       [1,2,3][1,3,2] [2,1,3][2,3,1][3,1,2][3,2,1]

Total: 3 · 2 · 1 = 6 permutations.

Code (Python 3)

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result: list[list[int]] = []
        n = len(nums)
        used = [False] * n
        path: list[int] = []

        def backtrack() -> None:
            if len(path) == n:
                result.append(path.copy())
                return
            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtrack()
                path.pop()
                used[i] = False

        backtrack()
        return result


class SolutionSwap:
    """Approach 2 — swap in place, no used array required."""

    def permute(self, nums: List[int]) -> List[List[int]]:
        result: list[list[int]] = []

        def backtrack(start: int) -> None:
            if start == len(nums):
                result.append(nums.copy())
                return
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]  # undo

        backtrack(0)
        return result

Complexity

Comments

3.6 Subsets (LC 78)

Problem

Given an array nums of distinct integers, return all possible subsets of nums (including the empty set and the full set), totalling 2^n subsets.

Example

Input:  nums = [1, 2, 3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

Input:  nums = [0]
Output: [[], [0]]

Constraints

Clarifying questions

Approach

There are three classic approaches, all worth knowing.

Approach 1 — Backtracking “pick / skip”. At each index i, branch into two: include nums[i] in path or skip it.

Approach 2 — Backtracking “start-index”. Every node in the recursion tree calls result.append(path.copy()) (every prefix is a valid subset), then loops for i in range(start, n).

Approach 3 — Bitmask iteration. Each number from 0 to 2^n - 1 represents one subset: bit i set ↔︎ nums[i] is in the subset. (See Chapter 21.)

Illustration — “pick / skip” tree for [1, 2, 3]:

                            [ ]
                skip 1 /          \ pick 1
                  [ ]             [1]
            skip 2 / \ pick 2  skip 2 / \ pick 2
                [ ] [2]            [1] [1,2]
          skip3/\ ... ...          ...  ...
           [ ] [3]

Each LEAF = one subset. The tree has 2^3 = 8 leaves.

Code (Python 3)

from typing import List

class Solution:
    """Approach 2 — every prefix is a subset."""

    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: list[list[int]] = []
        path: list[int] = []

        def backtrack(start: int) -> None:
            result.append(path.copy())          # every state is a subset
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result


class SolutionBitmask:
    """Approach 3 — iterate through 2^n bitmasks."""

    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = []
        for mask in range(1 << n):
            subset = [nums[i] for i in range(n) if mask & (1 << i)]
            result.append(subset)
        return result


class SolutionPick:
    """Approach 1 — pick / skip backtracking."""

    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: list[list[int]] = []
        path: list[int] = []

        def backtrack(i: int) -> None:
            if i == len(nums):
                result.append(path.copy())
                return
            # branch: skip nums[i]
            backtrack(i + 1)
            # branch: pick nums[i]
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

        backtrack(0)
        return result

Complexity

Comments

Chapter summary & decisions

Recursion vs DFS vs Backtracking vs Top-down DP

Property Recursion DFS Backtracking Top-down DP
Goal Self-call to solve a subproblem Traverse a graph/tree Enumerate every solution Optimal value / count
Need undo? Optional Rare Required (choose/unchoose) No
Need memo? Sometimes Rarely Rarely (state depends on path) Required
Examples Factorial, Fibonacci Number of Islands Permutations, N-Queens LCS, Coin Change

Backtracking mantra

def backtrack(path, choices):
    if is_goal(path):
        record(path); return
    for c in choices:
        if not feasible(path, c): continue
        path.append(c)          # choose
        backtrack(path, ...)    # explore
        path.pop()              # unchoose

Python recursion caveats

Chapter 4 — Sorting

Sort is itself a solved problem. This chapter does not teach you to implement quicksort — Python already ships an excellent sorted() (Timsort, worst-case O(n log n), stable). What you really need to learn is when sorting is the enabler that solves the problem, and the secret lies in custom comparators and the techniques that scan a sorted array with two pointers / sweep line.

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

Three golden questions: 1. Sort by which key? start, end, length, frequency, ratio? 2. How do we sweep after sorting? one-pass / two pointers / sweep line / heap? 3. Do we need stability? Python’s sorted is stable by default — a valuable asset.

Template code

from functools import cmp_to_key
from typing import List

# 1) Sort by a simple key
nums.sort(key=lambda x: x[0])

# 2) Sort by multiple keys (tie-breaker)
nums.sort(key=lambda x: (x[0], -x[1]))    # x[0] ascending, x[1] descending

# 3) Sort with a custom comparator
def cmp(a, b) -> int:
    if a + b > b + a:   return -1   # a comes first
    if a + b < b + a:   return  1   # b comes first
    return 0
arr.sort(key=cmp_to_key(cmp))

# 4) Sweep line over an event array
events = [(start, +1), (end, -1)]
events.sort()

End-of-chapter practice

4.1 Sort Colors / Dutch National Flag (LC 75)

Problem

Given an array nums containing only the values 0, 1, and 2 (representing 3 colours), rearrange it so equal colours are adjacent in the order 0 → 1 → 2. You must do it in place, without using the language’s sort function.

Example

Input:  nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]

Input:  nums = [2, 0, 1]
Output: [0, 1, 2]

Constraints

Clarifying questions

Approach

Approach 1 — Two-pass counting sort, O(n). Count the number of 0s, 1s, 2s, then overwrite. Simple but two passes.

Approach 2 — Dutch National Flag (Edsger Dijkstra), one pass, O(n).

Maintain 3 pointers: - lo = the right boundary of the 0s region (everything in [0..lo-1] is 0). - hi = the left boundary of the 2s region (everything in [hi+1..n-1] is 2). - mid = the scanning pointer between the two regions.

Invariant: [0..lo-1] = 0, [lo..mid-1] = 1, [mid..hi] unprocessed, [hi+1..n-1] = 2.

At each step: - nums[mid] == 0 → swap with nums[lo], lo++, mid++. - nums[mid] == 1 → already in the correct region, mid++. - nums[mid] == 2 → swap with nums[hi], hi-- (do not increment mid because the value that just came from hi has not been processed).

Illustration for nums = [2, 0, 2, 1, 1, 0]:

                  lo  mid          hi
Init       :  [ 2,  0,  2,  1,  1,  0 ]
                ↑   ↑                ↑
              lo=0 mid=0           hi=5

mid=0: nums[0]=2 → swap(0,5), hi--
              [ 0,  0,  2,  1,  1,  2 ]
                ↑   ↑           ↑
              lo=0 mid=0      hi=4

mid=0: nums[0]=0 → swap(lo,mid)=swap(0,0), lo++, mid++
              [ 0,  0,  2,  1,  1,  2 ]
                    ↑   ↑       ↑
                  lo=1 mid=1  hi=4

mid=1: nums[1]=0 → swap(1,1), lo++, mid++
              [ 0,  0,  2,  1,  1,  2 ]
                        ↑   ↑   ↑
                       lo=2 mid=2 hi=4

mid=2: nums[2]=2 → swap(2,4), hi--
              [ 0,  0,  1,  1,  2,  2 ]
                        ↑   ↑   ↑
                       lo=2 mid=2 hi=3

mid=2: nums[2]=1 → mid++
              [ 0,  0,  1,  1,  2,  2 ]
                        ↑       ↑
                       lo=2 mid=3 hi=3

mid=3: nums[3]=1 → mid++
              [ 0,  0,  1,  1,  2,  2 ]
                        ↑           ↑
                       lo=2  mid=4 hi=3   ← mid > hi → stop

Result : [0, 0, 1, 1, 2, 2]  ✓

Code (Python 3)

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        lo, mid, hi = 0, 0, len(nums) - 1
        while mid <= hi:
            if nums[mid] == 0:
                nums[lo], nums[mid] = nums[mid], nums[lo]
                lo += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:  # nums[mid] == 2
                nums[mid], nums[hi] = nums[hi], nums[mid]
                hi -= 1
                # DO NOT increment mid — we have not seen what just came from hi

Complexity

Comments

4.2 Merge Intervals (LC 56)

Problem

Given an array of intervals intervals[i] = [start_i, end_i], merge all overlapping intervals into non-overlapping ones and return the result.

Example

Input:  intervals = [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]
Explanation: [1,3] and [2,6] overlap → merged into [1,6].

Input:  intervals = [[1,4], [4,5]]
Output: [[1,5]]
Explanation: [1,4] and [4,5] touch at point 4 → counted as overlapping.

Constraints

Clarifying questions

Approach

Brute force. Repeatedly find an overlapping pair and merge. O(n²) or worse.

Optimal — Sort + one pass — O(n log n).

Sort by start ascending. Sweep through, keeping last = the most recently appended interval. For each new cur: - If cur.start <= last.end → overlap; extend last.end = max(last.end, cur.end). - Otherwise → push cur as a new interval.

Illustration for [[1,3], [2,6], [8,10], [15,18]]:

Number line:
   1   3   5   7   9  11  13  15  17  19
   |   |   |   |   |   |   |   |   |   |
   ├───┤                                       [1,3]
       ├──────────┤                            [2,6]
                       ├───┤                   [8,10]
                                       ├───┤   [15,18]

After sorting by start: [[1,3], [2,6], [8,10], [15,18]]

Sweep:
  Push [1,3]                              result = [[1,3]]
  cur=[2,6], 2 <= 3 → extend [1, max(3,6)] = [1,6]
                                           result = [[1,6]]
  cur=[8,10], 8 > 6 → push                result = [[1,6], [8,10]]
  cur=[15,18], 15 > 10 → push             result = [[1,6], [8,10], [15,18]]

Result: [[1,6], [8,10], [15,18]]

Code (Python 3)

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        result: list[list[int]] = []
        for cur in intervals:
            if result and cur[0] <= result[-1][1]:
                result[-1][1] = max(result[-1][1], cur[1])
            else:
                result.append(cur[:])   # copy so we don't alias the input
        return result

Complexity

Comments

4.3 Largest Number (LC 179)

Problem

Given an array of non-negative integers nums, arrange them (in some order) to form a single concatenated string that represents the largest possible number. Return the result as a string (because the number can be huge).

Example

Input:  nums = [10, 2]
Output: "210"

Input:  nums = [3, 30, 34, 5, 9]
Output: "9534330"

Input:  nums = [0, 0]
Output: "0"   (not "00")

Constraints

Clarifying questions

Approach

Brute force — try every permutation, O(n! · n). TLE for any non-trivial n.

Optimal — Sort with a custom comparator — O(n log n · L) where L is the max string length.

Insight: to decide whether a should precede b, compare the two possible concatenations: str(a) + str(b) vs str(b) + str(a) — the one that is lexicographically larger wins.

Why is it valid? “Concatenation-bigger” is a transitive relation — provable rigorously via the lexicographic ordering of concatenations, which guarantees a consistent sort order exists.

Example: a = 3, b = 30 → "330" > "303" → 3 comes before 30.

Code (Python 3)

from functools import cmp_to_key
from typing import List

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        strs = [str(x) for x in nums]

        def cmp(a: str, b: str) -> int:
            if a + b > b + a:   return -1   # a first
            if a + b < b + a:   return  1   # b first
            return 0

        strs.sort(key=cmp_to_key(cmp))
        result = ''.join(strs)
        # edge case: [0, 0, 0] → avoid returning "000"
        return '0' if result[0] == '0' else result

Complexity

Comments

4.4 Meeting Rooms II (LC 253)

Problem

Given an array of intervals intervals[i] = [start_i, end_i] representing meetings, find the minimum number of rooms required to host them all.

(That is, at any point in time, what is the maximum number of simultaneous meetings?)

Example

Input:  intervals = [[0,30], [5,10], [15,20]]
Output: 2
Explanation: at t=5, [0,30] and [5,10] overlap → 2 rooms needed.

Input:  intervals = [[7,10], [2,4]]
Output: 1
Explanation: 2 meetings don't overlap, 1 room suffices.

Constraints

Clarifying questions

Approach

There are three solid approaches, all worth knowing:

Approach 1 — Heap (priority queue) — O(n log n).

Sort by start. Scan each meeting and maintain a min-heap of end_times for currently open meetings. When a new meeting arrives at start: - If the heap top has end <= start → the old meeting is over → pop it (reuse the room). - Push the new end onto the heap.

The heap size at any moment = number of rooms currently in use → the max of that size over time is the answer.

Approach 2 — Sweep line / chronological — O(n log n).

Build two arrays: starts (sorted) and ends (sorted). Use two pointers: if starts[i] < ends[j] → a new meeting begins before the oldest ends → need a room (rooms++, i++); otherwise → an old meeting ends, advance j.

Approach 3 — Event-driven, O(n log n).

Each meeting emits two events: (start, +1) and (end, -1). Sort all events (prefer -1 before +1 at the same time → close before open). Sweep, tracking cur and peak.

Illustration for [[0,30], [5,10], [15,20]] — heap-based:

Sort by start: [[0,30], [5,10], [15,20]]

Step 1: meeting [0,30]    heap = [30]     → rooms = 1
Step 2: meeting [5,10]    top=30 > 5 → keep; push 10  heap = [10, 30]  → rooms = 2 ★
Step 3: meeting [15,20]   top=10 <= 15 → pop 10; push 20  heap = [20, 30] → rooms = 2

Number line:
   0   5  10  15  20  25  30
   |   |   |   |   |   |   |
   ├───────────────────────┤    [0, 30] uses room A
       ├───┤                    [5, 10] uses room B
                ├───┤            [15, 20] reuses room B

Code (Python 3)

import heapq
from typing import List

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[0])
        heap: list[int] = []   # min-heap of end times
        for start, end in intervals:
            if heap and heap[0] <= start:
                heapq.heappop(heap)
            heapq.heappush(heap, end)
        return len(heap)


class SolutionEvents:
    """Event-driven — clean for follow-ups."""

    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        events = []
        for s, e in intervals:
            events.append((s, +1))
            events.append((e, -1))
        # On a tie: -1 before +1 (close room before opening a new one)
        events.sort(key=lambda x: (x[0], x[1]))

        cur = peak = 0
        for _, delta in events:
            cur += delta
            peak = max(peak, cur)
        return peak

Complexity

Comments

4.5 Custom Sort String (LC 791)

Problem

Given two strings order (containing distinct characters) and s, rearrange s so that the order of characters appearing in order is respected. Characters of s not present in order may be placed anywhere in the result.

Example

Input:  order = "cba", s = "abcd"
Output: "cbad"
Explanation: in order, c < b < a. The character 'd' does not appear in order
            and can be placed anywhere.

Input:  order = "bcafg", s = "abcd"
Output: "bcad"

Constraints

Clarifying questions

Approach

Approach 1 — Sort by an index table comparator, O(|s| log |s|).

Build a dict priority = {ch: i for i, ch in enumerate(order)}. Characters not in order get a very large priority (e.g. 26). Sort s by this priority.

Approach 2 — Counter + emit in order, O(|s|).

Compute Counter(s), then iterate over each character in order and “emit” it the right number of times. Finally append the remaining characters (those not in order).

Approach 2 needs no sort, is faster, and feels very natural — interviewers typically expect this version.

Code (Python 3)

from collections import Counter

class Solution:
    """Approach 2 — Counter + emit in order."""

    def customSortString(self, order: str, s: str) -> str:
        cnt = Counter(s)
        parts: list[str] = []
        # 1. Characters that belong to `order`, in the exact order.
        for ch in order:
            if ch in cnt:
                parts.append(ch * cnt.pop(ch))
        # 2. Remaining characters (not in `order`) — order doesn't matter.
        for ch, c in cnt.items():
            parts.append(ch * c)
        return ''.join(parts)


class SolutionSort:
    """Approach 1 — comparator by index table."""

    def customSortString(self, order: str, s: str) -> str:
        priority = {ch: i for i, ch in enumerate(order)}
        return ''.join(sorted(s, key=lambda ch: priority.get(ch, 26)))

Complexity

Approach Time Space
Counter O(|s| + |order|) O(1)
Sort key O(|s| log |s|) O(|s|)

Comments

4.6 Wiggle Sort (LC 280)

Problem

Given nums, rearrange it so that:

nums[0] <= nums[1] >= nums[2] <= nums[3] >= nums[4] <= ...

Odd indices are always >= their left and right neighbours.

Example

Input:  nums = [3, 5, 2, 1, 6, 4]
Output: [3, 5, 1, 6, 2, 4]   (one of many valid answers)

Input:  nums = [6, 6, 5, 6, 3, 8]
Output: [6, 6, 5, 6, 3, 8]   (already satisfies)

Constraints

Clarifying questions

Approach

Approach 1 — Sort then swap pairs, O(n log n). Sort ascending, then swap each pair (i, i+1) for odd i. Correct but suboptimal.

Approach 2 — Greedy one pass, O(n).

Observation: at each index i, - If i is odd (1, 3, 5, …): nums[i] >= nums[i-1]. - If i is even (2, 4, 6, …): nums[i] <= nums[i-1].

Sweep from i = 1. On violation, swap nums[i] and nums[i-1]. Why does the swap not break the previous relation? We only modify the element at index i-1 (making it smaller or larger), and the relation between nums[i-2] and nums[i-1] from the previous step already enforces a “safe boundary”.

Illustration for nums = [3, 5, 2, 1, 6, 4]:

Index :   0   1   2   3   4   5
Input :  [3,  5,  2,  1,  6,  4]
            odd even odd even odd
            ≥   ≤    ≥   ≤    ≥

i=1 (odd) :  want nums[1] >= nums[0]   5 >= 3 ✓
i=2 (even):  want nums[2] <= nums[1]   2 <= 5 ✓
i=3 (odd) :  want nums[3] >= nums[2]   1 >= 2 ✗ → swap
           [3, 5, 1, 2, 6, 4]
i=4 (even):  want nums[4] <= nums[3]   6 <= 2 ✗ → swap
           [3, 5, 1, 6, 2, 4]
i=5 (odd) :  want nums[5] >= nums[4]   4 >= 2 ✓

Result : [3, 5, 1, 6, 2, 4]  ✓

Code (Python 3)

from typing import List

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        for i in range(1, len(nums)):
            should_be_greater = (i % 2 == 1)
            if (should_be_greater and nums[i] < nums[i - 1]) or \
               (not should_be_greater and nums[i] > nums[i - 1]):
                nums[i], nums[i - 1] = nums[i - 1], nums[i]

Complexity

Comments

Chapter summary & decisions

What sorting buys / costs you

Buys: - Brings order to monotonic, unlocking two-pointer, binary search, sweep. - Groups “similar” elements together (anagram, intervals).

Costs: - Loses the original index → if the output requires indices, store (value, idx) first. - Mutates the input — clarify with the interviewer before sorting. - O(n log n), not free.

Largest Number (LC 179) — comparator pitfalls

Meeting Rooms II — heap vs sweep

Heap Sweep line
Mental model Which room frees up earliest → reuse Count overlap at each timestamp
Code heapq + sort by start Sort events (time, ±1)
Output Max rooms Max rooms
Extending Easy to also return the schedule (which room when) Hard to return the schedule

Wiggle Sort: LC 280 vs LC 324

Binary Search looks simple — “halve a sorted array” — yet in interviews it is the number-one bug magnet. Knuth famously wrote: “although the idea is simple, getting it right is harder than it looks”. This chapter teaches you one single template that applies to every variant: find equal, find boundary, search on rotated, search on the answer, … — we return to it in Chapter 25 (Advanced Binary Search).

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

Standard thought template: 1. What is the search space? (index, value, the answer itself). 2. What does check(mid) return as True/False? Is it monotonic? 3. Which boundary is the answer? First True or last False?

Template code

def lower_bound(nums: list[int], target: int) -> int:
    """Return the first index where nums[i] >= target. Returns len(nums) if absent."""
    lo, hi = 0, len(nums)        # [lo, hi)  — half-open
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def upper_bound(nums: list[int], target: int) -> int:
    """Return the first index where nums[i] > target."""
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def binary_search_answer(check, lo: int, hi: int) -> int:
    """Find the smallest value in [lo, hi] for which check(x)=True (check is F→T monotonic)."""
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Final tip: I always use the half-open [lo, hi) interval and the loop condition lo < hi. This convention matches Python’s bisect and has fewer off-by-one bugs than lo <= hi.

End-of-chapter practice

5.1 Binary Search (LC 704)

Problem

Given a sorted (ascending) array nums and a number target, return the index of target in nums, or -1 if absent. Must run in O(log n).

Example

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

Constraints

Clarifying questions

Approach

Brute force — O(n). Linear scan — fails the O(log n) requirement.

Optimal — half-open Binary Search, O(log n).

Maintain [lo, hi). Each iteration: - mid = (lo + hi) // 2. - If nums[mid] == target → return mid. - If nums[mid] < target → answer (if any) is in [mid+1, hi) → lo = mid + 1. - If nums[mid] > target → answer is in [lo, mid) → hi = mid.

Illustration for nums = [-1, 0, 3, 5, 9, 12], target = 9:

index :     0    1    2    3    4    5
nums  :  [ -1,   0,   3,   5,   9,  12 ]

Iter 1: lo=0, hi=6  → mid=3, nums[3]=5 < 9 → lo = mid+1 = 4
Iter 2: lo=4, hi=6  → mid=5, nums[5]=12 > 9 → hi = mid = 5
Iter 3: lo=4, hi=5  → mid=4, nums[4]=9 == 9 → return 4  ✓

Code (Python 3)

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)    # [lo, hi)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return -1

Complexity

Comments

5.2 Search Insert Position (LC 35)

Problem

Given a sorted (no duplicates) array nums and target, return: - The index of target if present. - The position where target would be inserted to keep nums sorted.

Must run in O(log n).

Example

Input:  nums = [1, 3, 5, 6], target = 5   → 2
Input:  nums = [1, 3, 5, 6], target = 2   → 1
Input:  nums = [1, 3, 5, 6], target = 7   → 4   (append at end)
Input:  nums = [1, 3, 5, 6], target = 0   → 0   (prepend)

Constraints

Clarifying questions

Approach

This is exactly lower_bound. The first index i such that nums[i] >= target — semantically: “this is where target would sit on insertion”.

Code (Python 3)

from typing import List

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo

Complexity

Comments

5.3 First Bad Version (LC 278)

Problem

You have n versions labelled 1 to n. There is a “bad” version, and every version after it is also bad. You can call an API isBadVersion(int) returning True/False. Find the first bad version with the fewest API calls.

Example

n = 5, bad version = 4
call isBadVersion(3) → False
call isBadVersion(5) → True
call isBadVersion(4) → True
→ return 4

Constraints

Clarifying questions

Approach

This is search on a monotonic predicate. Perfect for the binary_search_answer template:

Illustration for n = 7, bad = 4:

version :  1     2     3     4     5     6     7
check  :   F     F     F     T     T     T     T
                              ↑
                       want this position

Iter 1: lo=1, hi=7  → mid=4, check(4)=T → hi=4
Iter 2: lo=1, hi=4  → mid=2, check(2)=F → lo=3
Iter 3: lo=3, hi=4  → mid=3, check(3)=F → lo=4
lo == hi → return lo = 4  ✓

Code (Python 3)

def isBadVersion(v: int) -> bool: ...     # provided API

class Solution:
    def firstBadVersion(self, n: int) -> int:
        lo, hi = 1, n      # closed interval [lo, hi]
        while lo < hi:
            mid = lo + (hi - lo) // 2      # overflow-safe in other languages
            if isBadVersion(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

Complexity

Comments

5.4 Find First and Last Position of Element (LC 34)

Problem

Given a sorted (ascending, with possible duplicates) array nums and target, return [first, last] — the first and last positions of target in nums. Return [-1, -1] if absent. Must run in O(log n).

Example

Input:  nums = [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]

Input:  nums = [5, 7, 7, 8, 8, 10], target = 6
Output: [-1, -1]

Input:  nums = [], target = 0
Output: [-1, -1]

Constraints

Clarifying questions

Approach

Use two binary searches: - first = lower_bound(target) — first index >= target. - last = upper_bound(target) - 1 — last index <= target.

Then sanity-check first is valid and nums[first] == target.

Illustration for nums = [5, 7, 7, 8, 8, 10], target = 8:

index :     0    1    2    3    4    5
nums  :  [  5,   7,   7,   8,   8,  10 ]
                          ↑    ↑
                       first  last

lower_bound(8) = 3   (first index >= 8)
upper_bound(8) = 5   (first index > 8)
last           = 4   (= upper - 1)

Return [3, 4]

Code (Python 3)

from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower_bound(t: int) -> int:
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < t:
                    lo = mid + 1
                else:
                    hi = mid
            return lo

        first = lower_bound(target)
        if first == len(nums) or nums[first] != target:
            return [-1, -1]
        last = lower_bound(target + 1) - 1
        return [first, last]

Complexity

Comments

5.5 Search in Rotated Sorted Array (LC 33)

Problem

Given nums, originally sorted ascending with distinct values, then rotated at an unknown pivot (rotated right k times, k unknown). Given target, return its index, or -1. Must run in O(log n).

Example

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1

Input:  nums = [1], target = 0
Output: -1

Constraints

Clarifying questions

Approach

Key observation: splitting a rotated array at mid, at least one half ([lo, mid] or [mid, hi]) is truly sorted (not rotated).

Each step: 1. Compute mid. 2. If nums[mid] == target → return mid. 3. Identify the sorted half: - If nums[lo] <= nums[mid] → left half is sorted. - Otherwise → right half is sorted. 4. Check whether target lies in the sorted half (compare with <, >): - Yes → search the sorted half. - No → search the other half.

Illustration for nums = [4, 5, 6, 7, 0, 1, 2], target = 0:

index :   0    1    2    3    4    5    6
nums  :  [4,   5,   6,   7,   0,   1,   2]
          lo                            hi

Iter 1: lo=0, hi=6, mid=3, nums[mid]=7
  nums[lo]=4 <= nums[mid]=7 → left [0..3] = [4,5,6,7] sorted.
  Is target=0 in [4..7]? No (0 < 4) → go right.
  → lo = mid + 1 = 4

Iter 2: lo=4, hi=6, mid=5, nums[mid]=1
  nums[lo]=0 <= nums[mid]=1 → left [4..5] = [0,1] sorted.
  Is target=0 in [0..1]? Yes → go left.
  → hi = mid - 1 = 4

Iter 3: lo=4, hi=4, mid=4, nums[mid]=0 == target → return 4  ✓

Code (Python 3)

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1        # closed interval
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid

            # Is the left half [lo..mid] sorted?
            if nums[lo] <= nums[mid]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1     # target in left half
                else:
                    lo = mid + 1
            # Otherwise the right half [mid..hi] is sorted
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1     # target in right half
                else:
                    hi = mid - 1

        return -1

Complexity

Comments

5.6 Sqrt(x) (LC 69)

Problem

Given a non-negative integer x, return the floor of its square root — the largest integer r such that r * r <= x.

Built-in sqrt is not allowed.

Example

Input:  x = 4   → 2
Input:  x = 8   → 2   (because 2² = 4 ≤ 8 < 9 = 3²)
Input:  x = 0   → 0
Input:  x = 1   → 1

Constraints

Clarifying questions

Approach

Approach 1 — Binary search on the answer — O(log x).

Find the largest integer r such that r² <= x. Equivalent to “last True” in the monotonic sequence [T, T, ..., T, F, F, ...] (T = r² <= x).

Search range: [0, x] (or [0, x//2 + 1] to save).

Approach 2 — Newton’s Method — O(log x) with a smaller constant.

Iterate r = (r + x/r) / 2 until r² <= x < (r+1)². Convergence is quadratic — this is how sqrt is implemented in many standard libraries.

Illustration — Binary Search for x = 8:

   r :    0    1    2    3    4    5    6    7    8
  r² :    0    1    4    9   16   25   36   49   64
                    ↑
                last r with r² <= 8

Iter 1: lo=0, hi=8   mid=4, 16 > 8 → hi = 3
Iter 2: lo=0, hi=3   mid=1,  1 <= 8 → answer=1, lo=2
Iter 3: lo=2, hi=3   mid=2,  4 <= 8 → answer=2, lo=3
Iter 4: lo=3, hi=3   mid=3,  9 > 8 → hi=2  → lo > hi, stop

Return 2  ✓

Code (Python 3)

class Solution:
    """Approach 1 — binary search."""

    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        lo, hi = 1, x // 2 + 1
        answer = 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if mid * mid <= x:
                answer = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return answer


class SolutionNewton:
    """Approach 2 — Newton's method, smaller constant."""

    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        r = x
        while r * r > x:
            r = (r + x // r) // 2
        return r

Complexity

Comments

Chapter summary & decisions

Template invariants (pick one and stick with it)

Closed interval [lo, hi]:

lo, hi = 0, n - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if check(mid): return mid
    elif too_small(mid): lo = mid + 1
    else: hi = mid - 1
return -1

Half-open [lo, hi) — first-true (lower_bound):

lo, hi = 0, n          # hi is NOT inclusive
while lo < hi:
    mid = (lo + hi) // 2
    if pred(mid): hi = mid
    else: lo = mid + 1
return lo                # first index where pred holds

Pre-submission checklist

  1. lo, hi are initialised correctly (especially for search on answer: lo = min, hi = max or max + 1).
  2. The loop condition matches the interval kind (<= vs <).
  3. The updates mid+1 / mid-1 / mid are correct — no infinite loop.
  4. What does the “not found” case return? -1, n, lo?
  5. (lo + hi) // 2 overflow is safe in Python; in Java/C++ use lo + (hi - lo) // 2.

Sqrt overflow note (other languages)

Python ints never overflow. Java/C++: mid * mid may overflow int32. Use (long) mid * mid or compare mid <= x / mid to avoid the multiplication.

Chapter 6 — Hash Table

Hash Table is the “magic weapon” of coding interviews: it turns many O(n²) problems into O(n). Philosophy: trade memory for time — accept O(n) extra memory in exchange for O(1) lookups. This chapter teaches you to recognise when you should and when you shouldn’t use hashing, along with 6 classic problems that frequently appear in Big Tech interviews.

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

When not to use hash: - You need sorted order → use SortedSet / TreeMap (Python: sortedcontainers). - You need O(1) worst-case (not amortised) → hash is vulnerable to adversarial collisions. - Keys are complex (list, dict) → must convert to tuple / frozenset.

Template code

from collections import Counter, defaultdict
from typing import List

# 1) Counter: frequency table
cnt = Counter(nums)               # {value: count}
top3 = cnt.most_common(3)         # 3 most-common elements

# 2) defaultdict(list): group by key
groups: dict[str, list[int]] = defaultdict(list)
for i, v in enumerate(arr):
    groups[v].append(i)

# 3) Prefix sum + dict: find subarrays
prefix_index = {0: -1}            # prefix_sum -> earliest index
cur = 0
for i, x in enumerate(arr):
    cur += x
    if cur - target in prefix_index:
        # found a subarray with sum = target
        ...
    if cur not in prefix_index:
        prefix_index[cur] = i

End-of-chapter practice

6.1 Contains Duplicate (LC 217)

Problem

Given an array nums, return True if any value appears at least twice, otherwise False.

Example

Input:  nums = [1, 2, 3, 1]   → True
Input:  nums = [1, 2, 3, 4]   → False
Input:  nums = []             → False

Constraints

Clarifying questions

Approach

Brute force — O(n²). Compare every pair.

Sort — O(n log n), O(1) extra space. Sort then check adjacent elements.

Hash set — O(n) time, O(n) space — the most common answer.

Pythonic one-liner: return len(set(nums)) != len(nums).

Code (Python 3)

from typing import List

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen: set[int] = set()
        for x in nums:
            if x in seen:
                return True
            seen.add(x)
        return False

Complexity

Comments

6.2 Longest Consecutive Sequence (LC 128)

Problem

Given an unsorted array nums, return the length of the longest sequence of consecutive integers (they need not be adjacent in the array). Must run in O(n).

Example

Input:  nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: the consecutive run [1, 2, 3, 4] has length 4.

Input:  nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Explanation: the run [0, 1, 2, 3, 4, 5, 6, 7, 8].

Input:  nums = []
Output: 0

Constraints

Clarifying questions

Approach

Brute force — O(n³). For each element, count x, x+1, x+2, ... in the array.

Sort — O(n log n). Sort, count consecutive runs. Simple but fails the O(n) target.

Optimal — Hash Set + “only start from a chain’s beginning” — O(n).

Key insight: a number x is a chain starter ↔︎ x - 1 is not in the array. Only for such x do we count the chain x, x+1, x+2, ... via hash lookup. Each element is “walked forward” at most once across all starters → total O(n).

Illustration for nums = [100, 4, 200, 1, 3, 2]:

Set: {100, 4, 200, 1, 3, 2}

Iterate over each x in the set:
  x=100: 99 not in set → starter
         Count: 100 ✓, 101 ✗  → length 1
  x=4:   3 IS in set → SKIP (will be counted starting from 1)
  x=200: 199 not in set → starter
         Count: 200 ✓, 201 ✗  → length 1
  x=1:   0 not in set → starter
         Count: 1 ✓, 2 ✓, 3 ✓, 4 ✓, 5 ✗  → length 4  ★
  x=3:   2 IS in set → SKIP
  x=2:   1 IS in set → SKIP

Total: max length = 4.

Key: each element of the chain 1-2-3-4 is "walked forward" exactly once
      (when x=1). Total work ~ O(n).

Code (Python 3)

from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        best = 0
        for x in num_set:
            # Only start from a chain head (x-1 not in set).
            if x - 1 not in num_set:
                cur = x
                length = 1
                while cur + 1 in num_set:
                    cur += 1
                    length += 1
                best = max(best, length)
        return best

Complexity

Comments

6.3 Top K Frequent Elements (LC 347)

Problem

Given an array nums and integer k, return the k most frequent elements (output order does not matter).

Example

Input:  nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]

Input:  nums = [1], k = 1
Output: [1]

Constraints

Clarifying questions

Approach

Approach 1 — Counter + sort — O(n log n). Simple but doesn’t meet the hint.

Approach 2 — Min-heap of size k — O(n log k). Maintain a heap of size k; pop the least-frequent when it overflows.

Approach 3 — Bucket sort by frequency — O(n) — the slickest.

Maximum frequency is n → create n + 1 buckets where bucket i holds elements whose frequency is i. Sweep buckets from high to low, gather k elements.

Illustration for nums = [1,1,1,2,2,3], k=2:

Step 1: Counter → {1:3, 2:2, 3:1}

Step 2: Bucket sort by frequency (n=6, 7 buckets 0..6):
  bucket[0] = []
  bucket[1] = [3]      # element 3 appears 1 time
  bucket[2] = [2]      # element 2 appears 2 times
  bucket[3] = [1]      # element 1 appears 3 times
  bucket[4..6] = []

Step 3: Walk buckets from index 6 down:
  i=6: empty
  i=5: empty
  i=4: empty
  i=3: [1] → result = [1]
  i=2: [2] → result = [1, 2]   reached k=2, stop

Output: [1, 2]

Code (Python 3)

import heapq
from collections import Counter
from typing import List

class Solution:
    """Approach 3 — bucket sort, O(n)."""

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        n = len(nums)
        buckets: list[list[int]] = [[] for _ in range(n + 1)]
        for x, freq in cnt.items():
            buckets[freq].append(x)
        result: list[int] = []
        for freq in range(n, 0, -1):
            for x in buckets[freq]:
                result.append(x)
                if len(result) == k:
                    return result
        return result


class SolutionHeap:
    """Approach 2 — min-heap of size k, O(n log k)."""

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        # heapq.nlargest uses a heap-based partial sort
        return heapq.nlargest(k, cnt.keys(), key=cnt.get)

Complexity

Approach Time Space
Counter + sort O(n log n) O(n)
Min-heap O(n log k) O(n)
Bucket sort O(n) O(n)

Comments

6.4 Subarray Sum Equals K (LC 560)

Problem

Given an integer array nums and integer k, return the number of contiguous subarrays whose sum equals k.

Example

Input:  nums = [1, 1, 1], k = 2
Output: 2
Explanation: two subarrays [1,1] (positions 0..1 and 1..2).

Input:  nums = [1, 2, 3], k = 3
Output: 2
Explanation: [1,2] and [3].

Constraints

Clarifying questions

Approach

Brute force — O(n²). For each i, accumulate a prefix sum and check == k. Acceptable but not optimal.

Optimal — Prefix sum + Hash map — O(n).

Let P[i] = sum of nums[0..i-1] (P[0] = 0). The sum of nums[j..i-1] is P[i] - P[j]. A subarray of sum k ↔︎ P[i] - P[j] = k ↔︎ P[j] = P[i] - k.

→ Walk and count j < i with P[j] == cur - k. Maintain a dict {prefix_sum: count}.

Illustration for nums = [3, 4, 7, 2, -3, 1, 4, 2], k = 7:

i    :   0    1    2    3    4    5    6    7
nums :   3    4    7    2   -3    1    4    2
P[i+1]:  3    7   14   16   13   14   18   20

Hand-trace:
P[]   = [0, 3, 7, 14, 16, 13, 14, 18, 20]
counts = {0:1}                        cur=0
i=0  cur=3   (3-7=-4 not in counts)  add 3 → {0:1, 3:1}
i=1  cur=7   (7-7= 0 in counts: +1)  add 7 → {0:1, 3:1, 7:1}   answer=1
i=2  cur=14  (14-7=7 in counts: +1)  add 14 → ...              answer=2
i=3  cur=16  (16-7=9 not in counts)                            answer=2
i=4  cur=13  (13-7=6 not in counts)                            answer=2
i=5  cur=14  (14-7=7 in counts: +1)  cur seen → counts[14]+=1
                                                              answer=3
i=6  cur=18  (18-7=11 not in counts)                          answer=3
i=7  cur=20  (20-7=13 in counts: +1)                          answer=4

Answer: 4 subarrays with sum = 7.

Code (Python 3)

from collections import defaultdict
from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        counts: dict[int, int] = defaultdict(int)
        counts[0] = 1            # prefix sum 0 has occurred once (empty prefix)
        cur = 0
        result = 0
        for x in nums:
            cur += x
            result += counts[cur - k]    # how many j satisfy P[j] = cur - k
            counts[cur] += 1
        return result

Complexity

Comments

6.5 Isomorphic Strings (LC 205)

Problem

Two strings s and t are isomorphic if there exists a bijection between their characters such that replacing each character in s according to the mapping yields t.

Example

Input:  s = "egg", t = "add"   → True
Explanation: e→a, g→d (bijection).

Input:  s = "foo", t = "bar"   → False
Explanation: o would map to both a and r (not a function).

Input:  s = "paper", t = "title"   → True

Input:  s = "badc", t = "baba"   → False
Explanation: d→a and c→a, two different chars map to one → not a bijection.

Constraints

Clarifying questions

Approach

Approach 1 — Two dicts (mapping in both directions).

Walk the two strings together: - If s[i] is already in s2t → check s2t[s[i]] == t[i]. - Otherwise → confirm t[i] is not already in t2s (avoids multiple s mapping to the same t). - Store the pair (s[i], t[i]) in both dicts.

Approach 2 — Replace by “first-occurrence index”.

A string can be “normalised” by replacing each character with the index of its first occurrence. Two strings are isomorphic ↔︎ their normalised sequences match.

Example: "egg" → [0, 1, 1], "add" → [0, 1, 1] → equal → True.

Approach 1 is more intuitive; Approach 2 is algorithmically slicker. Both O(n).

Code (Python 3)

class Solution:
    """Approach 1 — two dicts, verify bijection."""

    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        s2t: dict[str, str] = {}
        t2s: dict[str, str] = {}
        for a, b in zip(s, t):
            if a in s2t:
                if s2t[a] != b:
                    return False
            else:
                if b in t2s:        # b already mapped from a different char
                    return False
                s2t[a] = b
                t2s[b] = a
        return True


class SolutionNormalize:
    """Approach 2 — normalise by first-occurrence index."""

    def isIsomorphic(self, s: str, t: str) -> bool:
        return self._normalize(s) == self._normalize(t)

    @staticmethod
    def _normalize(s: str) -> list[int]:
        idx: dict[str, int] = {}
        out: list[int] = []
        for ch in s:
            if ch not in idx:
                idx[ch] = len(idx)
            out.append(idx[ch])
        return out

Complexity

Comments

6.6 LRU Cache (LC 146)

Problem

Design a Least Recently Used (LRU) Cache with both operations in O(1):

Example

Input (LC-style operation arrays):
  ops  = ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
  args = [[2],        [1,1], [2,2], [1],   [3,3], [2],   [4,4], [1],   [3],   [4]]

Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Step-by-step trace (capacity = 2; right = MRU, left = LRU):

  LRUCache(2)         → null;   cache = {}                    (LRU ← → MRU)
  put(1, 1)           → null;   cache = {1=1}
  put(2, 2)           → null;   cache = {1=1, 2=2}
  get(1)              → 1;      cache = {2=2, 1=1}   (1 just used → MRU)
  put(3, 3)           → null;   cache = {1=1, 3=3}   (evict 2: LRU)
  get(2)              → -1;     (key 2 gone)
  put(4, 4)           → null;   cache = {3=3, 4=4}   (evict 1)
  get(1)              → -1
  get(3)              → 3;      cache = {4=4, 3=3}
  get(4)              → 4;      cache = {3=3, 4=4}

Constraints

Clarifying questions

Approach

Core requirement: O(1) for both get and put ↔︎ we need both: - Hash map: key → reference to a node (gives O(1) lookup). - Doubly Linked List (DLL): access order (MRU at one end, LRU at the other). Lets us delete an arbitrary node in O(1) given its reference.

Each get(k): - If k is in the map → take the node, move it to the front of the DLL (= MRU), return value. - Otherwise return -1.

Each put(k, v): - If k is already present → update value, move to front. - Otherwise → insert a new node at the front. On capacity overflow → remove the tail node (LRU) and erase from the map.

Pythonic shortcut — use OrderedDict (already supports both operations):

OrderedDict is implemented underneath as a hash map combined with a doubly linked list. It exposes two methods that are gold for LRU: move_to_end(key) and popitem(last=False) (pop from the front).

Illustration — DLL state through the operations:

capacity = 2
                    Head (MRU)              Tail (LRU)
                          │                       │
                          ▼                       ▼
put(1,1):   DLL:    1                              cache = {1: node1}
put(2,2):   DLL:    2 ─── 1                       cache = {1: ., 2: .}
get(1)=1:   DLL:    1 ─── 2     (1 → MRU)
put(3,3):   DLL:    3 ─── 1     (evict 2 as LRU)
get(2)=-1
put(4,4):   DLL:    4 ─── 3     (evict 1)
get(1)=-1
get(3)=3:   DLL:    3 ─── 4
get(4)=4:   DLL:    4 ─── 3

Code (Python 3)

from collections import OrderedDict

class LRUCache:
    """Pythonic — OrderedDict already provides hash + DLL."""

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)        # push to MRU end
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # pop LRU at the front


# ─────────────────────────────────────────────────────────────
# Hand-rolled version (interview-friendly): dict + doubly linked list.
# Use this when the interviewer says "Implement LRU without built-ins."

class _Node:
    __slots__ = ("key", "val", "prev", "next")

    def __init__(self, key: int = 0, val: int = 0):
        self.key, self.val = key, val
        self.prev: "_Node | None" = None
        self.next: "_Node | None" = None


class LRUCacheManual:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: dict[int, _Node] = {}
        # Two sentinels (head/tail) keep code short — no None checks at edges.
        self.head, self.tail = _Node(), _Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: _Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: _Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._add_to_front(node)
            return
        if len(self.cache) == self.cap:
            lru = self.tail.prev          # LRU = just before tail sentinel
            self._remove(lru)
            del self.cache[lru.key]
        new_node = _Node(key, value)
        self.cache[key] = new_node
        self._add_to_front(new_node)

Complexity

Comments

Chapter summary & decisions

When hash is NOT enough

Requirement Hash enough? Replacement
O(1) lookup, no order needed ✅ —
Need ordered traversal ❌ OrderedDict / sorted list
Range query [l, r] ❌ Fenwick / Segment Tree (Chapter 22)
Top-k frequent Partial Heap (Chapter 15)
Nearest neighbour ❌ Sorted set / BST
Subarray sum with negatives ✅ Prefix sum + hash —
Subarray sum non-negative only Use sliding window (27) —

LRU two ways

Longest Consecutive — why O(n)?

Chapter 7 — Linked List

Linked List is “simple in theory, painful in code”. Each node points to the next — that’s it — but writing bug-free linked-list code requires memorising 5 small tricks: dummy head, two pointers, in-place reverse, split-by-pivot, and cross-pointer relinking. By the end of this chapter, LL will stop being intimidating.

This chapter has 12 problems — twice as many as basic chapters — because the LL pattern has many important variants, ranging from Easy (Reverse, Merge, Cycle) to Hard (Reverse k-Group, Sort, Reorder).

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

5 tricks to memorise:

  1. Dummy head: create a fake dummy.next = head, use prev = dummy. Avoids a barrage of if head is None checks.
  2. Two pointers (slow / fast): find the middle (1× / 2× speed), detect cycles (Floyd), find offset-from-end.
  3. Reverse in place: 3 pointers prev / curr / nxt.
  4. Split → process → merge: pattern used by merge sort, palindrome check, reorder.
  5. Pointer relinking: when assigning a.next = b, always detach a from its old spot first (update both incoming and outgoing pointers).

Input format (applies to ALL problems in this chapter)

Every problem in Chapter 7 (and 3.3, 15.5) uses LeetCode’s standard ListNode:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Template code

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None):
        self.val = val
        self.next = next


def use_dummy(head: ListNode | None) -> ListNode | None:
    """Dummy-head pattern — problems that insert/delete near the head."""
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        # ... operate on prev.next ...
        prev = prev.next
    return dummy.next      # head may have changed


def find_middle(head: ListNode | None) -> ListNode | None:
    """Slow/fast pointers — find middle (LC 876)."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


def reverse(head: ListNode | None) -> ListNode | None:
    """Reverse iterative — 3 pointers."""
    prev, curr = None, head
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    return prev

End-of-chapter practice

7.1 Reverse Linked List (LC 206) — iterative

Problem

Given head of a singly linked list, reverse it and return the new head. (The recursive version lives in Chapter 3.3 — this section focuses on the iterative version with O(1) space.)

Example

Input:  head = 1 → 2 → 3 → 4 → 5 → None  (singly linked list)
Output: 5 → 4 → 3 → 2 → 1 → None

Constraints

Clarifying questions

Approach

Three pointers: - prev = the node right before curr in the result. - curr = the node we are processing. - nxt = backup of curr.next before we overwrite.

Each iteration: flip curr.next to point at prev, then advance both prev and curr.

Illustration with 1 → 2 → 3 → None:

Start  :   prev = None
           curr → 1 → 2 → 3 → None

Iter 1:    nxt = 2
           curr.next = prev   →   None ← 1   2 → 3 → None
           prev = curr = 1, curr = 2

Iter 2:    nxt = 3
           curr.next = prev   →   None ← 1 ← 2   3 → None
           prev = 2, curr = 3

Iter 3:    nxt = None
           curr.next = prev   →   None ← 1 ← 2 ← 3
           prev = 3, curr = None  → stop

Return prev = 3, list: 3 → 2 → 1 → None

Code (Python 3)

class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        prev, curr = None, head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

Pythonic in-loop one-liner: curr.next, prev, curr = prev, curr, curr.next. Tuple unpacking evaluates the RHS first, so no temporary nxt is needed.

Complexity

Comments

7.2 Merge Two Sorted Lists (LC 21)

Problem

Given two heads of two ascending sorted linked lists, return the head of the merged list (also ascending).

Example

Input:  l1 = 1 → 2 → 4,  l2 = 1 → 3 → 4
Output: 1 → 1 → 2 → 3 → 4 → 4

Constraints

Clarifying questions

Approach

Iterative — use a dummy head. Create dummy with tail = dummy. Each step attach tail.next to the smaller node of the two lists, advance tail. Finally splice the remaining tail.

Recursive (very concise but O(n) stack):

if not l1: return l2
if not l2: return l1
if l1.val <= l2.val:
    l1.next = self.mergeTwoLists(l1.next, l2)
    return l1
else:
    l2.next = self.mergeTwoLists(l1, l2.next)
    return l2

Code (Python 3)

class Solution:
    def mergeTwoLists(self, l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
        dummy = ListNode()
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next, l1 = l1, l1.next
            else:
                tail.next, l2 = l2, l2.next
            tail = tail.next
        tail.next = l1 if l1 else l2     # splice the remaining tail
        return dummy.next

Complexity

Comments

7.3 Linked List Cycle (LC 141)

Problem

Given the head of a linked list, return True if there is a cycle, otherwise False. Requirement: O(1) extra space.

Example

Input:  head = [3, 2, 0, -4], cycle begins at index 1
        3 → 2 → 0 → -4
            ↑________|
Output: True

Constraints

Clarifying questions

Approach

Brute force — Hash set, O(n) space. Store every seen node.

Optimal — Floyd’s Tortoise and Hare, O(1) space.

Two pointers slow (1×) and fast (2×). If a cycle exists, fast “catches up” to slow inside the loop (their distance shrinks by 1 each step). If not, fast runs off the end.

Illustration — slow/fast on a cycle:

Linked list:  3 → 2 → 0 → -4 → ⟲ (back to 2)

Step 0:  slow=3, fast=3
Step 1:  slow=2, fast=0
Step 2:  slow=0, fast=2     (fast looped back)
Step 3:  slow=-4, fast=-4   ★ they meet → return True

On a cycle of length L, slow steps 1, fast steps 2 → distance shrinks
by 1 per step → meet within L steps.

Code (Python 3)

class Solution:
    def hasCycle(self, head: ListNode | None) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

Complexity

Comments

7.4 Middle of the Linked List (LC 876)

Problem

Given the head, return the middle node. If there are two middles (even length), return the second.

Example

Input:  head = 1 → 2 → 3 → 4 → 5     (singly linked list)
Output: node with value 3 (middle; belongs to the right half on even length)
Input:  head = 1 → 2 → 3 → 4 → 5 → 6   (singly linked list, even length)
Output: node with value 4 (the second of the two middles)

Constraints

Clarifying questions

Approach

Brute force — 2 passes, O(n). Count length, then walk to the middle.

Optimal — Slow/fast one pass, O(n). When fast hits the end, slow is at the middle.

Code (Python 3)

class Solution:
    def middleNode(self, head: ListNode | None) -> ListNode | None:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

Complexity

Comments

7.5 Remove Nth Node From End of List (LC 19)

Problem

Given the head and integer n, remove the n-th node counting from the end (1-indexed) and return the possibly-changed head.

Example

Input:  1 → 2 → 3 → 4 → 5, n = 2     → 1 → 2 → 3 → 5  (remove node 4)
Input:  1, n = 1                     → None
Input:  1 → 2, n = 1                 → 1

Constraints

Clarifying questions

Approach

Brute force — 2 passes. Count length L, then remove the (L - n)-th from the start.

Optimal — single pass, two pointers separated by n. - Create a dummy to handle removal of the head. - fast advances n steps first. - Then slow and fast advance together until fast.next is None. At that point slow.next is exactly the node to remove.

Illustration with 1 → 2 → 3 → 4 → 5, n = 2:

Start:    dummy → 1 → 2 → 3 → 4 → 5 → None
          slow
          fast

After fast advances n=2 steps:
          dummy → 1 → 2 → 3 → 4 → 5 → None
          slow        fast

Advance together until fast.next == None:
          dummy → 1 → 2 → 3 → 4 → 5 → None
                          slow      fast

slow.next = 4 → the node to remove. slow.next = slow.next.next.
          dummy → 1 → 2 → 3 → 5 → None  ✓

Code (Python 3)

class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy = ListNode(0, head)
        slow = fast = dummy
        for _ in range(n):
            fast = fast.next
        while fast.next:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next

Complexity

Comments

7.6 Palindrome Linked List (LC 234)

Problem

Given the head of a singly linked list, return True if the values form a palindrome. Required: O(n) time, O(1) space.

Example

Input:  head = 1 → 2 → 2 → 1     → Output: True   (palindrome)
Input:  head = 1 → 2             → Output: False  (1 ≠ 2)

Constraints

Clarifying questions

Approach

Brute force — copy values to an array + two pointers, O(n) space. Simple but violates the O(1) space goal.

Optimal — Split + Reverse half + Compare, O(1) space. 1. Find the middle (slow/fast). 2. Reverse the second half (in place). 3. Compare node-by-node between the first half and the reversed second half. 4. (Optional) Restore the second half (usually unnecessary in interviews).

Illustration with 1 → 2 → 3 → 2 → 1:

Step 1: find middle (slow lands at node 3)
              1 → 2 → 3 → 2 → 1
                      ↑ slow

Step 2: reverse the second half (starting from slow.next = 2):
              1 → 2 → 3   1 → 2
              (first half) (reversed second half)

Step 3: compare node-by-node:
              1 vs 1 ✓
              2 vs 2 ✓
        → True

Code (Python 3)

class Solution:
    def isPalindrome(self, head: ListNode | None) -> bool:
        # 1. Find middle.
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. Reverse second half (starting at slow).
        prev, curr = None, slow
        while curr:
            curr.next, prev, curr = prev, curr, curr.next

        # 3. Compare.
        left, right = head, prev
        while right:    # reversed second half may be one node shorter
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

Complexity

Comments

7.7 Add Two Numbers (LC 2)

Problem

Given two linked lists representing two non-negative integers with digits stored in reverse (ones digit at the head), return the linked list = sum of the two numbers (also reversed).

Example

Input:  l1 = 2 → 4 → 3   (represents 342)
        l2 = 5 → 6 → 4   (represents 465)
Output: 7 → 0 → 8         (represents 807 = 342 + 465)

Input:  l1 = 9 → 9 → 9 → 9 → 9 → 9 → 9
        l2 = 9 → 9 → 9 → 9
Output: 8 → 9 → 9 → 9 → 0 → 0 → 0 → 1

Constraints

Clarifying questions

Approach

Simulate addition by hand: walk both lists together, keep a carry. Each step: - total = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry - digit = total % 10, carry = total // 10. - Push digit to the result; advance l1, l2.

Stop only when both are exhausted and carry == 0.

Code (Python 3)

class Solution:
    def addTwoNumbers(self, l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
        dummy = ListNode()
        tail = dummy
        carry = 0
        while l1 or l2 or carry:
            total = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
            carry, digit = divmod(total, 10)
            tail.next = ListNode(digit)
            tail = tail.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        return dummy.next

Complexity

Comments

7.8 Copy List with Random Pointer (LC 138)

Problem

Given a linked list where each node has both next and random — pointing to any node in the list (or None) — produce a deep copy (every new node is a distinct instance, with random pointers pointing into the copies).

Example

Input (LC-style):
  head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
  (each entry [val, random_index]; random_index is the 0-based index of
   the node that `random` points to, or null if `random = None`)

  Corresponding linked list:
        node 0      node 1      node 2      node 3      node 4
        val=7   →   val=13  →   val=11  →   val=10  →   val=1  →  None
        random:                                                    (next pointers)
          [0] → None
          [1] → node 0  (val 7)
          [2] → node 4  (val 1)
          [3] → node 2  (val 11)
          [4] → node 0  (val 7)

Output: deep copy of the above — same vals and same random structure,
        but EVERY node is a NEW instance (no sharing with the input).

Output as an LC array:
  [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]

Constraints

Clarifying questions

Approach

Approach 1 — Hash map “old → new”, O(n) time, O(n) space.

Pass 1: create the new nodes, store old_to_new[old] = new. Pass 2: for each old, set new.next = old_to_new[old.next] and new.random = old_to_new[old.random].

Approach 2 — Interweave, O(n) time, O(1) extra space.

A classic trick: 1. Pass 1: insert each copied node right after its original: A → A' → B → B' → C → C'. 2. Pass 2: for each original node A, set A'.random = A.random.next (since A.random.next is the copy of A.random). 3. Pass 3: split the two lists apart.

Illustration — Approach 2 with 3 nodes A, B, C:

Pass 1 (insert copy):
  A → A' → B → B' → C → C'

Pass 2 (set random):
  Suppose A.random = C
  → A'.random = A.random.next = C.next = C'   (copy of C)  ✓

Pass 3 (split):
  Original:  A → B → C
  Copy:      A' → B' → C'

Code (Python 3)

class Node:
    def __init__(self, val: int = 0, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random


class Solution:
    """Approach 1 — hash map. Easiest to debug."""

    def copyRandomList(self, head: "Node | None") -> "Node | None":
        if not head:
            return None
        old_to_new: dict[Node, Node] = {}
        # Pass 1: create copy nodes.
        cur = head
        while cur:
            old_to_new[cur] = Node(cur.val)
            cur = cur.next
        # Pass 2: link next/random.
        cur = head
        while cur:
            old_to_new[cur].next = old_to_new.get(cur.next)
            old_to_new[cur].random = old_to_new.get(cur.random)
            cur = cur.next
        return old_to_new[head]


class SolutionInterleave:
    """Approach 2 — interweave, O(1) extra space."""

    def copyRandomList(self, head: "Node | None") -> "Node | None":
        if not head:
            return None
        # 1. Insert a copy right after each original node.
        cur = head
        while cur:
            cur.next = Node(cur.val, cur.next)
            cur = cur.next.next
        # 2. Set random pointers for the copies.
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        # 3. Split into two lists.
        new_head = head.next
        cur, copy = head, new_head
        while cur:
            cur.next = copy.next
            cur = cur.next
            copy.next = cur.next if cur else None
            copy = copy.next
        return new_head

Complexity

Comments

7.9 Reverse Nodes in k-Group (LC 25)

Problem

Given the head and integer k, reverse each consecutive group of k nodes in the list. If the remaining nodes are fewer than k, leave them as is. Required: O(1) extra space.

Example

Input:  1 → 2 → 3 → 4 → 5, k = 2
Output: 2 → 1 → 4 → 3 → 5    (last group has only 1 node → leave it)

Input:  1 → 2 → 3 → 4 → 5, k = 3
Output: 3 → 2 → 1 → 4 → 5

Constraints

Clarifying questions

Approach

Procedure: 1. Walk k steps to locate the group tail. If fewer than k → break. 2. Reverse the group in [head_of_group, tail_of_group]. 3. Splice the head of the reversed group onto prev_group_tail, and the tail of the reversed group on to next_group_head. 4. Update prev_group_tail for the next group.

Illustration with 1 → 2 → 3 → 4 → 5, k = 2:

Start:      dummy → 1 → 2 → 3 → 4 → 5 → None
            prev

Group 1: [1, 2]. Reverse → [2, 1].
            dummy → 2 → 1 → 3 → 4 → 5 → None
                        ↑
                       prev (= 1, the tail of the just-reversed group)

Group 2: [3, 4]. Reverse → [4, 3].
            dummy → 2 → 1 → 4 → 3 → 5 → None
                                ↑
                               prev (= 3)

Group 3: [5]. Only 1 node → fewer than k=2 → leave.
            dummy → 2 → 1 → 4 → 3 → 5 → None   ✓

Code (Python 3)

class Solution:
    def reverseKGroup(self, head: ListNode | None, k: int) -> ListNode | None:
        dummy = ListNode(0, head)
        prev_group_tail = dummy

        while True:
            # 1. Find the group tail — walk k steps.
            kth = prev_group_tail
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next      # fewer than k left → leave as is

            group_next = kth.next
            # 2. Reverse from prev_group_tail.next to kth.
            prev, curr = group_next, prev_group_tail.next
            while curr is not group_next:
                curr.next, prev, curr = prev, curr, curr.next
            # 3. Splice the reversed group in.
            old_head = prev_group_tail.next
            prev_group_tail.next = kth
            prev_group_tail = old_head     # this is now the reversed group's tail

Complexity

Comments

7.10 Sort List (LC 148)

Problem

Sort a linked list ascending in O(n log n) time and O(1) extra space (per the follow-up — counts call stack/aux only, not nodes).

Example

Input:  head = 4 → 2 → 1 → 3   (singly linked list)
Output: 1 → 2 → 3 → 4

Constraints

Clarifying questions

Approach

O(n log n) ⇒ quicksort, mergesort, heapsort. Quicksort is awkward on LL, heapsort needs O(n) extra. Merge sort is the most natural:

  1. Split the list into two halves (slow/fast for the middle, cut slow.next).
  2. Recurse on both halves.
  3. Merge the two sorted lists (problem 7.2).

Top-down (recursive) is clean but consumes O(log n) stack. Bottom-up (iterative) achieves true O(1) space — but more complex. In an interview, top-down is good enough.

Illustration with 4 → 2 → 1 → 3:

                   sort([4, 2, 1, 3])
                  /                  \
        sort([4, 2])             sort([1, 3])
         /        \                /        \
    [4]            [2]         [1]            [3]
       \          /                \          /
       merge → [2, 4]              merge → [1, 3]
                       \              /
                       merge → [1, 2, 3, 4]   ✓

Code (Python 3)

class Solution:
    def sortList(self, head: ListNode | None) -> ListNode | None:
        if not head or not head.next:
            return head

        # 1. Split: find middle, cut in half.
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None

        # 2. Recurse.
        left = self.sortList(head)
        right = self.sortList(mid)

        # 3. Merge.
        return self._merge(left, right)

    @staticmethod
    def _merge(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
        dummy = ListNode()
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next, l1 = l1, l1.next
            else:
                tail.next, l2 = l2, l2.next
            tail = tail.next
        tail.next = l1 or l2
        return dummy.next

Complexity

Comments

7.11 LRU Cache (LC 146) — recap

This problem is fully solved in Chapter 6 — Hash Table (section 6.6). Here we summarise the Doubly Linked List pattern, which is the LL highlight.

Problem

Design an LRU Cache with get(key) and put(key, value) both O(1). On capacity overflow → evict the least-recently-used key.

Constraints

Clarifying questions

Approach: Doubly Linked List + Hash Map

LRU requires O(1) for both: - Lookup by key → hash map. - Move an arbitrary node to the front → doubly linked list (only DLL supports O(1) unlink given a reference).

Illustration of DLL state on LRU eviction

capacity = 2
Head sentinel — MRU end                LRU end — Tail sentinel
       │                                                  │
       ▼                                                  ▼
     ┌───┐    ┌──────┐    ┌──────┐    ┌──────┐    ┌───┐
     │ H │ ↔ │ K=4  │ ↔ │ K=3  │ ↔ │ K=1  │ ↔ │ T │
     └───┘    └──────┘    └──────┘    └──────┘    └───┘
                                          ▲
                          on capacity overflow, evict this node
                          (Tail.prev = LRU)

Hash map:  {1: node1, 3: node3, 4: node4}

Code (Python 3) — DLL pattern

class Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None


# Two sentinels (head, tail) save many None checks.
head, tail = Node(), Node()
head.next, tail.prev = tail, head

def _remove(node):              # O(1) — only requires a reference
    node.prev.next = node.next
    node.next.prev = node.prev

def _add_to_front(node):
    node.prev = head
    node.next = head.next
    head.next.prev = node
    head.next = node

Complexity

Comments

7.12 Reorder List (LC 143)

Problem

Given a linked list L: L0 → L1 → ... → Ln-1, rearrange it to:

L0 → Ln-1 → L1 → Ln-2 → L2 → Ln-3 → ...

In place; no new nodes may be created.

Example

Input:  head = 1 → 2 → 3 → 4
Output: 1 → 4 → 2 → 3 (mutate in place)

Input:  head = 1 → 2 → 3 → 4 → 5
Output: 1 → 5 → 2 → 4 → 3   (mutate in place)

Constraints

Clarifying questions

Approach

Three standard steps — the “split → reverse → merge” pattern:

  1. Find the middle (slow/fast).
  2. Reverse the second half (in place).
  3. Merge interleaved the first half and the reversed second half.

Illustration with 1 → 2 → 3 → 4 → 5:

Step 1: find middle (slow at 3)
            1 → 2 → 3 → 4 → 5

Step 2: split and reverse the second half:
            1 → 2 → 3      5 → 4
            (first half)   (reversed second half)

Step 3: merge interleaved:
            Take 1 from left  → 1
            Take 5 from right → 1, 5
            Take 2 from left  → 1, 5, 2
            Take 4 from right → 1, 5, 2, 4
            Take 3 from left  → 1, 5, 2, 4, 3

Output: 1 → 5 → 2 → 4 → 3  ✓

Code (Python 3)

class Solution:
    def reorderList(self, head: ListNode | None) -> None:
        if not head or not head.next:
            return

        # 1. Find middle.
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # 2. Reverse second half (starting from slow.next).
        second = slow.next
        slow.next = None      # cut in half
        prev, curr = None, second
        while curr:
            curr.next, prev, curr = prev, curr, curr.next
        second = prev          # head of the reversed second half

        # 3. Merge interleaved.
        first = head
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2

Complexity

Comments

Chapter summary & decisions

Pointer-safety checklist

  1. Before overwriting a.next = b, did you save the old a.next?
  2. Is there a dummy/sentinel at the head? (Needed if head may change.)
  3. while cur and cur.next: be careful with the compound condition for the last two nodes.
  4. After reverse or split, did you set the old tail’s .next = None? (Avoid cycles.)
  5. Edge cases: empty list (head = None), single node, k > len.

Dummy/sentinel pattern (the core)

dummy = ListNode(0, head)
prev = dummy
# ... operate on prev.next ...
return dummy.next

Used by: Remove Nth From End, Merge Two Sorted, Partition, Odd Even, Reverse K-Group.

LRU (LC 146) bridge

Chapter 8 — Queue + Stack

Stack (LIFO) and Queue (FIFO) are mirror images of each other. Stack solves every problem with a nested structure (parentheses, recursion, nested expressions); Queue handles level-order traversal (BFS, sliding window). This chapter focuses on stack — pure queue problems return in Chapter 10 (BFS). The chapter ends with a teaser on monotonic stack — a powerful pattern explored in depth in Chapter 18.

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

Stack fits perfectly when: - The structure is nested / balanced (parentheses, HTML tags, nested expressions). - You need to “undo” — the previous step must finish only after the current step (iterative DFS). - Problems like “next greater element”, “largest rectangle”, “daily temperatures” → monotonic stack (Chapter 18).

Queue fits perfectly when: - You need level-order / BFS traversal (Chapter 10). - “Sliding window max” → monotonic deque (Chapter 18). - Producer-consumer, task scheduler.

Template code

from collections import deque
from typing import List

# 1) Stack with a list (built-in in Python, O(1) amortised).
stack: List[int] = []
stack.append(x)        # push
top = stack[-1]        # peek
val = stack.pop()      # pop

# 2) Queue with collections.deque — O(1) push/pop at both ends.
queue: deque[int] = deque()
queue.append(x)        # enqueue (push at the back)
val = queue.popleft()  # dequeue (pop from the front)

# 3) Stack of (index, value) — monotonic pattern.
stack: list[tuple[int, int]] = []        # (index, value)
for i, v in enumerate(arr):
    while stack and stack[-1][1] < v:
        idx, _ = stack.pop()
        # ... process idx ...
    stack.append((i, v))

End-of-chapter practice

8.1 Valid Parentheses (LC 20)

Problem

Given a string s containing only ()[]{}, return True if it is valid: - Every opening bracket has a matching closing one. - Closing brackets respect LIFO order.

Example

Input:  s = "()"            → Output: True
Input:  s = "()[]{}"        → Output: True
Input:  s = "(]"            → Output: False
Input:  s = "([)]"          → Output: False    (wrong nesting)
Input:  s = "{[]}"          → Output: True

Constraints

Clarifying questions

Approach

The classic stack pattern. Scan each character: - Opening bracket → push. - Closing bracket → check the stack top for the matching opener. If it does not match, or the stack is empty → return False. Otherwise pop.

At the end the stack must be empty (all brackets matched).

Illustration for s = "{[()]}":

ch   action          stack after action
─────────────────────────────────────
{    push            ['{']
[    push            ['{', '[']
(    push            ['{', '[', '(']
)    pop, match (    ['{', '[']
]    pop, match [    ['{']
}    pop, match {    []

Stack empty → True ✓

Code (Python 3)

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {')': '(', ']': '[', '}': '{'}
        stack: list[str] = []
        for ch in s:
            if ch in pairs:                # closing bracket
                if not stack or stack.pop() != pairs[ch]:
                    return False
            else:                          # opening bracket
                stack.append(ch)
        return not stack

Complexity

Comments

8.2 Min Stack (LC 155)

Problem

Design a stack supporting all four operations in O(1): - push(x) - pop() - top() — peek - getMin() — return the current minimum in the stack

Example

Input (LC-style operation arrays):
  ops  = ["MinStack","push","push","push","getMin","pop","top","getMin"]
  args = [[],        [-2],   [0],  [-3],  [],     [],   [],   []]

Output: [null, null, null, null, -3, null, 0, -2]

Step-by-step:
  MinStack()  → init
  push(-2);  push(0);  push(-3)
  getMin()   → -3
  pop()      → drop -3
  top()      → 0
  getMin()   → -2

Constraints

Clarifying questions

Approach

Problem: getMin() in O(1) ⇒ the min has to be stored somewhere. But when we pop the min, we must know the new min — that’s the crux.

Approach 1 — Auxiliary stack holding min_so_far.

The auxiliary stack mins mirrors the main stack; its top is the min of all elements at and below in the main stack. On push, push min(x, mins[-1]). On pop, pop both stacks.

Approach 2 — Single stack of (value, current_min) tuples.

Same idea as Approach 1, just consolidated into tuples. Same overhead.

Illustration — Approach 1 for push(-2), push(0), push(-3), pop():

push(-2):  stack=[-2]      mins=[-2]
push(0):   stack=[-2, 0]   mins=[-2, -2]    (min(0, -2)=-2)
push(-3):  stack=[-2,0,-3] mins=[-2,-2,-3]   (min(-3, -2)=-3)

getMin() → mins[-1] = -3   ✓
pop():    stack=[-2, 0]    mins=[-2, -2]
getMin() → mins[-1] = -2   ✓

Code (Python 3)

class MinStack:
    def __init__(self):
        self.stack: list[int] = []
        self.mins: list[int] = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        cur_min = val if not self.mins else min(val, self.mins[-1])
        self.mins.append(cur_min)

    def pop(self) -> None:
        self.stack.pop()
        self.mins.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.mins[-1]

Complexity

Comments

8.3 Implement Queue using Stacks (LC 232)

Problem

Design a Queue (FIFO) using only two stacks. Support push, pop, peek, empty.

Example

Input (LC-style operation arrays):
  ops  = ["MyQueue","push","push","peek","pop","empty"]
  args = [[],       [1],   [2],   [],    [],   []]

Output: [null, null, null, 1, 1, false]

Step-by-step:
  MyQueue()  → init
  push(1);  push(2)
  peek()    → 1   (FIFO: first in first out)
  pop()     → 1
  empty()   → false

Constraints

Clarifying questions

Approach

Idea — two stacks: in (input) and out (output). - push(x): push onto in. - pop / peek: if out is empty → “pour” the entire in into out (reversing order due to LIFO). Then pop/peek from out.

Amortised analysis: each element is moved between the two stacks at most once. Worst-case single op is O(n), but amortised is O(1).

Illustration for push(1), push(2), push(3), pop(), push(4), pop():

push(1): in=[1]              out=[]
push(2): in=[1, 2]           out=[]
push(3): in=[1, 2, 3]        out=[]

pop(): out empty → pour in into out
       in=[]                  out=[3, 2, 1]    (1 on top)
       out.pop() → 1
       in=[]                  out=[3, 2]

push(4): in=[4]              out=[3, 2]

pop(): out non-empty → out.pop() → 2
       in=[4]                out=[3]

→ FIFO: 1 came out first (matching push order)

Code (Python 3)

class MyQueue:
    def __init__(self):
        self.in_st: list[int] = []
        self.out_st: list[int] = []

    def push(self, x: int) -> None:
        self.in_st.append(x)

    def pop(self) -> int:
        self._shift()
        return self.out_st.pop()

    def peek(self) -> int:
        self._shift()
        return self.out_st[-1]

    def empty(self) -> bool:
        return not self.in_st and not self.out_st

    def _shift(self) -> None:
        """When out is empty, pour all of in into out."""
        if not self.out_st:
            while self.in_st:
                self.out_st.append(self.in_st.pop())

Complexity

Comments

8.4 Evaluate Reverse Polish Notation (LC 150)

Problem

Given an array tokens representing a Reverse Polish Notation (postfix) expression. Each token is an integer or one of the four operators + - * /. Return the result (division truncated toward 0).

Example

Input:  tokens = ["2","1","+","3","*"]
Output: 9
Explanation: (2 + 1) * 3 = 9.

Input:  tokens = ["4","13","5","/","+"]
Output: 6
Explanation: 4 + (13 / 5) = 4 + 2 = 6.

Input:  tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22

Constraints

Clarifying questions

Approach

RPN ↔︎ stack — classic. Walk through: - Number → push. - Operator → pop two values (b first, then a), compute a op b, push the result.

At the end the stack contains one element = the answer.

Illustration for ["2","1","+","3","*"]:

token   action                      stack
─────────────────────────────────────────────
"2"     push 2                      [2]
"1"     push 1                      [2, 1]
"+"     pop b=1, a=2; push 3        [3]
"3"     push 3                      [3, 3]
"*"     pop b=3, a=3; push 9        [9]

Result: 9

Code (Python 3)

from typing import List
import operator

class Solution:
    OPS = {
        '+': operator.add,
        '-': operator.sub,
        '*': operator.mul,
        '/': lambda a, b: int(a / b),   # truncate toward 0
    }

    def evalRPN(self, tokens: List[str]) -> int:
        stack: list[int] = []
        for tk in tokens:
            if tk in self.OPS:
                b = stack.pop()
                a = stack.pop()
                stack.append(self.OPS[tk](a, b))
            else:
                stack.append(int(tk))
        return stack[0]

Complexity

Comments

8.5 Daily Temperatures (LC 739) — monotonic stack teaser

Problem

Given an array temperatures, for each day i find how many days you have to wait before a day with a strictly higher temperature. If none exists, return 0.

Example

Input:  temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation:
  day 0: 73 → day 1 (74) is higher → 1
  day 2: 75 → wait until day 6 (76) → 6-2=4
  day 6: 76 has nothing higher → 0

Constraints

Clarifying questions

Approach

Brute force — O(n²). For each i scan forward for a greater value. TLEs at n = 10^5.

Optimal — Monotonic decreasing stack — O(n).

Idea: maintain a stack of indices whose temperatures decrease from bottom to top. When day i arrives with a temperature greater than the stack top → that is the answer for the top day. Pop and write result[top] = i - top.

Illustration for [73, 74, 75, 71, 69, 72, 76, 73]:

i  temp   action                                stack (idx)    result
─────────────────────────────────────────────────────────────────────────
0  73     push 0                                [0]            [_, _, _, _, _, _, _, _]
1  74     74 > 73 → pop 0, result[0]=1-0=1     [1]            [1, _, _, _, _, _, _, _]
          push 1
2  75     75 > 74 → pop 1, result[1]=2-1=1     [2]            [1, 1, _, _, _, _, _, _]
          push 2
3  71     71 < 75 → push 3                     [2, 3]
4  69     69 < 71 → push 4                     [2, 3, 4]
5  72     72 > 69 → pop 4, result[4]=5-4=1     [2, 3, 5]
          72 > 71 → pop 3, result[3]=5-3=2
          push 5
6  76     76 > 72 → pop 5, result[5]=6-5=1     [6]
          76 > 75 → pop 2, result[2]=6-2=4
          push 6
7  73     73 < 76 → push 7                     [6, 7]

Leftover in stack: [6, 7] → result stays at 0.
Answer: [1, 1, 4, 2, 1, 1, 0, 0]  ✓

Stack invariant: indices on the stack have strictly decreasing temperatures from bottom to top. Each index is pushed once and popped at most once → O(n) total.

Code (Python 3)

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        result = [0] * n
        stack: list[int] = []   # indices with decreasing temperatures
        for i, t in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < t:
                j = stack.pop()
                result[j] = i - j
            stack.append(i)
        return result

Complexity

Comments

8.6 Decode String (LC 394)

Problem

Given a string s encoded as k[encoded_string] — meaning encoded_string is repeated k times — decode the string.

Example

Input:  s = "3[a]2[bc]"
Output: "aaabcbc"

Input:  s = "3[a2[c]]"
Output: "accaccacc"   (nested)

Input:  s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Constraints

Clarifying questions

Approach

A nested structure ⇒ use a stack. Whenever we encounter [, “save” the current k and the in-progress string onto the stack, then reset. When we hit ], pop (prev_str, k) and assemble prev_str + k * cur_str.

Approach 2 — Recursive. Each k[...] is a recursive call. Cleaner code but uses recursion stack (can exceed limits with deep nesting).

Illustration — Stack approach for "3[a2[c]]":

ch    action                                     stack         cur
─────────────────────────────────────────────────────────────────
'3'   k = 3                                      []           ""
'['   push (k, cur); reset k, cur                [(3, "")]    ""
'a'   cur += 'a'                                 [(3, "")]    "a"
'2'   k = 2                                      [(3, "")]    "a"
'['   push (k=2, cur="a"); reset k, cur          [(3, ""), (2, "a")]  ""
'c'   cur += 'c'                                 [(3, ""), (2, "a")]  "c"
']'   (prev_k=2, prev_str="a") = pop;
      cur = prev_str + prev_k * cur = "a" + "cc" [(3, "")]    "acc"
']'   (prev_k=3, prev_str="") = pop;
      cur = "" + 3 * "acc" = "accaccacc"         []           "accaccacc"

Answer: "accaccacc"  ✓

Code (Python 3)

class Solution:
    def decodeString(self, s: str) -> str:
        stack: list[tuple[str, int]] = []   # (prev_str, prev_k)
        cur, k = "", 0
        for ch in s:
            if ch.isdigit():
                k = k * 10 + int(ch)
            elif ch == '[':
                stack.append((cur, k))
                cur, k = "", 0
            elif ch == ']':
                prev_str, prev_k = stack.pop()
                cur = prev_str + cur * prev_k
            else:
                cur += ch
        return cur


class SolutionRecursive:
    """Approach 2 — recursive. Clean code but uses recursion stack."""

    def decodeString(self, s: str) -> str:
        self.i = 0
        return self._decode(s)

    def _decode(self, s: str) -> str:
        result = ""
        k = 0
        while self.i < len(s) and s[self.i] != ']':
            ch = s[self.i]
            if ch.isdigit():
                k = k * 10 + int(ch)
                self.i += 1
            elif ch == '[':
                self.i += 1
                inner = self._decode(s)
                result += k * inner
                k = 0
                self.i += 1     # skip ']'
            else:
                result += ch
                self.i += 1
        return result

Complexity

Comments

Chapter summary & decisions

Stack mental models

Purpose What the stack holds Example problems
Match symmetric pairs Opening brackets / tokens awaiting close LC 20, 1249
Save previous tokens not yet finished Numbers / strings to “expand” later LC 394 Decode
Undo / context Parent operations LC 224 Calculator
Monotonic Index/value increasing/decreasing Chapter 18
Iterative DFS Frame call Tree iterative inorder

Decode String (LC 394) — trace 3[a2[c]]

Step Char num cur numStack strStack
0 3 3 "" [] []
1 [ 0 "" [3] [""]
2 a 0 "a" [3] [""]
3 2 2 "a" [3] [""]
4 [ 0 "" [3,2] ["", "a"]
5 c 0 "c" [3,2] ["", "a"]
6 ] 0 "acc" (a + c×2) [3] [""]
7 ] 0 "accaccacc" (×3) [] []

RPN (LC 150) — operand order

Pop b first, then a, compute a op b. Reversing the order is the classic bug for - and /.

Min Stack comparison

Chapter 9 — Graph

Graph is the most abstract yet most ubiquitous data structure in real life: friendships, road networks, dependencies, … This chapter introduces graph representations and 6 general graph problems. The two traversal techniques BFS and DFS are explored in depth in Chapters 10 and 11; here we use both at a basic level to build familiarity.

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

Three questions to answer first: 1. Directed or undirected? Directed graphs require extra care for cycles. 2. Weighted? If yes → consider Dijkstra (Chapter 30); otherwise BFS/DFS suffices. 3. Special properties? DAG → topological sort, bipartite, planar, …

Graph representations

from collections import defaultdict
from typing import List

# 1) Adjacency List — what most problems use
graph: dict[int, list[int]] = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)    # drop this line if the graph is directed

# 2) Edge List — the "raw" input format
edges: list[tuple[int, int]] = [(0, 1), (1, 2), ...]

# 3) Adjacency Matrix — only when V is small (≤ 1000) and density is high
adj = [[0] * n for _ in range(n)]
for u, v in edges:
    adj[u][v] = 1

Which one to use?

Representation Lookup (u, v) Walk neighbours of u Memory
Adj list O(deg(u)) O(deg(u)) O(V + E)
Edge list O(E) O(E) O(E)
Adj matrix O(1) O(V) O(V²)

→ Default to adjacency list. Switch to a matrix only when you need O(1) edge checks and V is small.

Template code

from collections import defaultdict, deque

# Recursive DFS
def dfs(node: int, visited: set[int], graph: dict) -> None:
    if node in visited:
        return
    visited.add(node)
    for neighbor in graph[node]:
        dfs(neighbor, visited, graph)

# Iterative DFS with a stack
def dfs_iter(start: int, graph: dict) -> set[int]:
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for nb in graph[node]:
            if nb not in visited:
                stack.append(nb)
    return visited

# BFS with a queue
def bfs(start: int, graph: dict) -> set[int]:
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    return visited

End-of-chapter practice

9.1 Find if Path Exists in Graph (LC 1971)

Problem

Given n nodes labelled 0..n-1 and an array of undirected edges edges[i] = [u, v], plus source and destination, return True if there is a path between them.

Example

Input:  n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: True

Input:  n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: False

Constraints

Clarifying questions

Approach

Three classic approaches, all O(V + E): 1. BFS — level traversal, return as soon as we hit destination. 2. DFS — recursive or stack-based. 3. Union Find (Chapter 24) — merge endpoints of every edge under a single root; check find(source) == find(destination). Great when the problem asks many “is there a path between u, v?” queries.

Code (Python 3)

from collections import defaultdict, deque
from typing import List

class Solution:
    """BFS — cleanest for a single query."""

    def validPath(self, n: int, edges: List[List[int]],
                  source: int, destination: int) -> bool:
        if source == destination:
            return True
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = {source}
        queue = deque([source])
        while queue:
            node = queue.popleft()
            for nb in graph[node]:
                if nb == destination:
                    return True
                if nb not in visited:
                    visited.add(nb)
                    queue.append(nb)
        return False

Complexity

Comments

9.2 Clone Graph (LC 133)

Problem

Given a node in an undirected, connected graph. Each Node has val: int and neighbors: list[Node]. Return a deep copy of the graph: every new node is a distinct instance with neighbors pointing at the corresponding new nodes.

Example

Input:  adjList = [[2,4], [1,3], [2,4], [1,3]]
        (adjList[i-1] = neighbour list of node i; values are 1-indexed
         per LC. The actual API parameter is Node = adjList[0] = node 1)

        Corresponding graph:
            1 ── 2
            │    │
            4 ── 3

Output: [[2,4], [1,3], [2,4], [1,3]]
        (same adjacency structure, but EVERY Node in the output is a NEW
         instance; no Node is shared with the input)

Constraints

Clarifying questions

Approach

Same pattern as LC 138 (Copy List with Random Pointer, problem 7.8): use a hash map original_to_copy to avoid duplicates and to handle cycles.

BFS or DFS works — the crucial part is check visited via the dict.

Illustration for graph 1—2—3—4—1:

Start: visit 1.
  cloned = {1: Node(1)}
  queue = [1]

Pop 1:  neighbours = [2, 4]
  Create Node(2), Node(4); add to cloned.
  cloned[1].neighbors = [cloned[2], cloned[4]]
  queue = [2, 4]

Pop 2:  neighbours = [1, 3]
  cloned[1] exists; create Node(3).
  cloned[2].neighbors = [cloned[1], cloned[3]]
  queue = [4, 3]

Pop 4:  neighbours = [1, 3]
  Both exist in cloned.
  cloned[4].neighbors = [cloned[1], cloned[3]]

Pop 3:  neighbours = [2, 4]
  Both exist.
  cloned[3].neighbors = [cloned[2], cloned[4]]

→ Return cloned[1] as the head of the copy.

Code (Python 3)

from collections import deque

class Node:
    def __init__(self, val: int = 0, neighbors: "list[Node] | None" = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


class Solution:
    """BFS with a hash map."""

    def cloneGraph(self, node: "Node | None") -> "Node | None":
        if not node:
            return None

        cloned: dict["Node", "Node"] = {node: Node(node.val)}
        queue: deque["Node"] = deque([node])

        while queue:
            cur = queue.popleft()
            for nb in cur.neighbors:
                if nb not in cloned:
                    cloned[nb] = Node(nb.val)
                    queue.append(nb)
                cloned[cur].neighbors.append(cloned[nb])

        return cloned[node]


class SolutionDFS:
    """Recursive DFS — shorter code."""

    def cloneGraph(self, node: "Node | None") -> "Node | None":
        cloned: dict["Node", "Node"] = {}

        def dfs(cur: "Node") -> "Node":
            if cur in cloned:
                return cloned[cur]
            copy = Node(cur.val)
            cloned[cur] = copy           # MUST set BEFORE recursing on neighbours
            copy.neighbors = [dfs(nb) for nb in cur.neighbors]
            return copy

        return dfs(node) if node else None

Complexity

Comments

9.3 Number of Connected Components (LC 323)

Problem

Given n nodes labelled 0..n-1 and an array of undirected edges, count the number of connected components.

Example

Input:  n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Explanation: 2 components {0,1,2} and {3,4}.

Input:  n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1

Constraints

Clarifying questions

Approach

Approach 1 — DFS/BFS from each unvisited node — O(V + E). For each unvisited node, increment a counter and DFS/BFS-mark the whole component.

Approach 2 — Union Find — O((V + E) · α(V)). Union endpoints of every edge under the same root. Count distinct roots.

Code (Python 3)

from collections import defaultdict
from typing import List

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = [False] * n
        count = 0

        def dfs(node: int) -> None:
            visited[node] = True
            for nb in graph[node]:
                if not visited[nb]:
                    dfs(nb)

        for i in range(n):
            if not visited[i]:
                count += 1
                dfs(i)
        return count


class SolutionUF:
    """Union Find — nicer when many queries appear."""

    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]   # path compression
                x = parent[x]
            return x

        def union(x: int, y: int) -> bool:
            px, py = find(x), find(y)
            if px == py:
                return False
            parent[px] = py
            return True

        components = n
        for u, v in edges:
            if union(u, v):
                components -= 1
        return components

Complexity

Comments

9.4 Course Schedule (LC 207)

Problem

There are numCourses courses labelled 0..numCourses-1. Each prerequisites[i] = [a, b] means to take course a you must first finish course b. Return True if you can finish all courses, otherwise False.

Example

Input:  numCourses = 2, prerequisites = [[1, 0]]
Output: True

Input:  numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: False    (cycle: 1 requires 0, 0 requires 1)

Constraints

Clarifying questions

Approach

Reformulation: build a directed graph b → a (b must finish before a). The question becomes: does the graph have a cycle? No cycle → all courses can be finished.

Approach 1 — DFS with three colours (white / gray / black).

If DFS encounters gray → back-edge → cycle.

Approach 2 — Topological sort BFS (Kahn’s algorithm).

Count indegree of each node. Enqueue nodes with indegree == 0. Pop and decrement the indegree of neighbours. If at the end we processed numCourses nodes → DAG; otherwise a cycle exists.

Topological sort is the heart of Chapter 13. We introduce it early because Course Schedule is the classic application.

Illustration — 3-colour DFS with the cycle 0 → 1 → 0:

Start: all white.
DFS(0):
  mark 0 = gray.
  visit 1 (white):
    DFS(1):
      mark 1 = gray.
      visit 0 (gray!) → back-edge detected → return False (cycle)

Code (Python 3)

from collections import defaultdict, deque
from typing import List

class Solution:
    """3-colour DFS."""

    WHITE, GRAY, BLACK = 0, 1, 2

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a)            # b → a

        color = [self.WHITE] * numCourses

        def has_cycle(node: int) -> bool:
            if color[node] == self.GRAY:
                return True               # back-edge
            if color[node] == self.BLACK:
                return False              # already cleared
            color[node] = self.GRAY
            for nb in graph[node]:
                if has_cycle(nb):
                    return True
            color[node] = self.BLACK
            return False

        for i in range(numCourses):
            if has_cycle(i):
                return False
        return True


class SolutionKahn:
    """BFS topological sort (Kahn's algorithm)."""

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        indeg = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            indeg[a] += 1

        queue = deque(i for i, d in enumerate(indeg) if d == 0)
        processed = 0
        while queue:
            node = queue.popleft()
            processed += 1
            for nb in graph[node]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    queue.append(nb)

        return processed == numCourses

Complexity

Comments

9.5 Is Graph Bipartite? (LC 785)

Problem

Given an undirected graph as adjacency list graph[i] = [neighbours of i], return True if the graph is bipartite — the vertices can be split into two sets such that every edge connects vertices from different sets.

Example

Input:  graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: False
Explanation: 0—1—2—0 is a triangle → cannot 2-colour.

Input:  graph = [[1,3],[0,2],[1,3],[0,2]]
Output: True
Explanation: set A = {0, 2}, set B = {1, 3}.

Constraints

Clarifying questions

Approach

Equivalent: bipartite ↔︎ can 2-colour such that no two adjacent vertices share a colour.

BFS/DFS with 2-colouring: start each component, colour the first vertex 0. As BFS/DFS visits neighbours, flip the colour. If a neighbour already has the same colour → return False.

Illustration — triangle (not bipartite):

       0
      / \
     1───2

BFS from 0:
  color[0] = 0.
  Visit 1: color[1] = 1 (opposite of 0).
  Visit 2: color[2] = 1 (opposite of 0).
  From 1, visit 2: color[2] is already 1 == color[1] = 1 → CONFLICT → False

Code (Python 3)

from collections import deque
from typing import List

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [-1] * n        # -1 = uncoloured

        for start in range(n):
            if color[start] != -1:
                continue
            # BFS the component containing `start`.
            color[start] = 0
            queue = deque([start])
            while queue:
                node = queue.popleft()
                for nb in graph[node]:
                    if color[nb] == -1:
                        color[nb] = 1 - color[node]
                        queue.append(nb)
                    elif color[nb] == color[node]:
                        return False
        return True

Complexity

Comments

9.6 Evaluate Division (LC 399)

Problem

Given equations equations[i] = [Ai, Bi] and values values[i], meaning Ai / Bi = values[i]. Given queries queries[j] = [Cj, Dj], answer each with Cj / Dj, or -1 if it cannot be determined.

Example

Input:  equations = [["a","b"], ["b","c"]]
        values    = [2.0, 3.0]
        queries   = [["a","c"], ["b","a"], ["a","e"], ["a","a"], ["x","x"]]
Output: [6.0, 0.5, -1.0, 1.0, -1.0]
Explanation:
  a/c = a/b * b/c = 2 * 3 = 6
  b/a = 1/(a/b) = 0.5
  a/e is undefined (e is not in any equation)
  a/a = 1
  x/x: x not in any equation → -1

Constraints

Clarifying questions

Approach

Insight: each equation A / B = k ↔︎ two edges in a directed weighted graph: - A → B with weight k. - B → A with weight 1/k.

Then C / D = product of weights along any path from C to D. No path → return -1.

DFS on the weighted graph suffices. A tighter solution: Weighted Union Find (see Chapter 24).

Illustration for equations a/b=2, b/c=3:

Weighted graph:
            ── 2 ──>          ── 3 ──>
       a               b               c
            <─ 0.5 ──         <─ 1/3 ─

Query a/c: DFS from a:
  a → b (× 2), then b → c (× 3) → product 2 * 3 = 6.  ✓

Code (Python 3)

from collections import defaultdict
from typing import List

class Solution:
    def calcEquation(
        self, equations: List[List[str]],
        values: List[float], queries: List[List[str]]
    ) -> List[float]:
        graph: dict[str, dict[str, float]] = defaultdict(dict)
        for (a, b), v in zip(equations, values):
            graph[a][b] = v
            graph[b][a] = 1.0 / v

        def dfs(src: str, dst: str, visited: set[str]) -> float:
            if src not in graph or dst not in graph:
                return -1.0
            if src == dst:
                return 1.0
            visited.add(src)
            for nb, weight in graph[src].items():
                if nb in visited:
                    continue
                sub = dfs(nb, dst, visited)
                if sub != -1.0:
                    return weight * sub
            return -1.0

        return [dfs(c, d, set()) for c, d in queries]

Complexity

Comments

Chapter summary & decisions

Graph problem diagnosis

Symptom in the problem Best pattern Chapter
“Path from A to B?” BFS / DFS / Union Find 10, 11, 24
“Number of clusters/islands” DFS / Union Find 12, 24
“Ordering with constraints” Topological sort 13
“Shortest path positive weights” Dijkstra (Chapter 30)
“Shortest path 0/1 edges” 0-1 BFS / regular BFS
“All-pairs shortest” Floyd-Warshall O(V³)
“Minimum spanning network” MST (Chapter 33)
“Bottleneck min/max on path” Kruskal + DSU / BS + BFS (37)
“Bipartite?” BFS/DFS 2-colour

Clone Graph (LC 133) — mapping diagram

old:  1 — 2
       \  /
        3 — 4

old_to_new = {1:1', 2:2', 3:3', 4:4'}   (dict from original to copy)
clone(node):
    if node in old_to_new: return old_to_new[node]
    new = Node(node.val)
    old_to_new[node] = new       # SET BEFORE recursing → avoid cycles
    for nei in node.neighbors:
        new.neighbors.append(clone(nei))
    return new

Evaluate Division (LC 399) — weighted DFS

Course Schedule in this chapter = teaser

The full Topological Sort treatment lives in Chapter 13. This chapter only introduces DFS cycle detection.

Chapter 10 — Breadth-First Search (BFS)

BFS traverses a graph level by level. The key property: if every edge has the same weight (= 1), BFS from source yields the shortest path to every other vertex. That’s why BFS shows up repeatedly in “shortest path on an unweighted graph”, “minimum steps”, “minimum transformations”, … problems.

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

BFS vs DFS: - BFS: shortest path, level traversal. - DFS: deep exploration (first path to a target), connectivity, count components.

Template code

from collections import deque

# 1) Standard BFS — shortest path from start to target
def bfs_shortest(start, target, neighbors_fn) -> int:
    if start == target:
        return 0
    visited = {start}
    queue = deque([(start, 0)])         # (node, distance)
    while queue:
        node, dist = queue.popleft()
        for nb in neighbors_fn(node):
            if nb == target:
                return dist + 1
            if nb not in visited:
                visited.add(nb)
                queue.append((nb, dist + 1))
    return -1


# 2) Level BFS — no need to store distance in the queue
def bfs_by_level(start, neighbors_fn):
    visited = {start}
    queue = deque([start])
    level = 0
    while queue:
        size = len(queue)
        for _ in range(size):
            node = queue.popleft()
            # ... process node at this level ...
            for nb in neighbors_fn(node):
                if nb not in visited:
                    visited.add(nb)
                    queue.append(nb)
        level += 1


# 3) Multi-source BFS — push many sources into the queue simultaneously
def multi_source(sources: list, neighbors_fn):
    queue = deque(sources)
    visited = set(sources)
    while queue:
        ...

End-of-chapter practice

10.1 Binary Tree Level Order Traversal (LC 102)

Problem

Given the root of a binary tree, return its level-order traversal as a list of lists (each inner list contains the nodes at one level, top to bottom, left to right).

Example

Input:  root = [3, 9, 20, null, null, 15, 7]   (LC level-order serialisation)

        Actual tree:
              3
             / \
            9   20
               /  \
              15   7

Output: [[3], [9, 20], [15, 7]]

Constraints

Clarifying questions

Approach

Level-order BFS. Each outer loop iteration = one level. At the start of each iteration, record size = len(queue), then pop exactly size nodes — those form the entire current level.

Illustration:

Init:  queue = [3]
Level 0: size=1
  Pop 3. result.append([3]). Push 9, 20.
  queue = [9, 20]

Level 1: size=2
  Pop 9 → null children.
  Pop 20 → push 15, 7.
  result.append([9, 20]).
  queue = [15, 7]

Level 2: size=2
  Pop 15, 7 → null children.
  result.append([15, 7]).
  queue = []

→ [[3], [9, 20], [15, 7]]

Code (Python 3)

from collections import deque
from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result: List[List[int]] = []
        queue = deque([root])
        while queue:
            size = len(queue)
            level_vals: list[int] = []
            for _ in range(size):
                node = queue.popleft()
                level_vals.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level_vals)
        return result

Complexity

Comments

10.2 Rotting Oranges (LC 994) — Multi-source BFS

Problem

Given a grid grid with values: - 0 = empty cell - 1 = fresh orange - 2 = rotten orange

Every minute, each rotten orange turns its 4 axis-adjacent (up/down/left/right) fresh neighbours into rotten ones. Return the minimum number of minutes until no fresh orange remains, or -1 if impossible.

Example

Input:  grid = [[2,1,1],
                [1,1,0],
                [0,1,1]]
        (0 = empty, 1 = fresh orange, 2 = rotten)
Output: 4   (minutes for every orange to rot)

Input:  grid = [[2,1,1],
                [0,1,1],
                [1,0,1]]
Output: -1   (the orange at (2,0) is isolated and never rots)

Constraints

Clarifying questions

Approach

Insight: every rotten orange is a source. All sources spread simultaneously every minute → multi-source BFS.

Procedure: 1. Enqueue all initial rotten oranges (level 0). 2. Level-order BFS — each level increments minutes by 1. 3. Count the initial fresh oranges. Every newly rotted one decrements the count. 4. End: if any fresh remains → -1, otherwise → minutes.

Illustration with a 3x3 grid:

Init:                t=0:              t=1:              t=4:
[2, 1, 1]            [2, 1, 1]         [2, 2, 1]         [2, 2, 2]
[1, 1, 0]            [1, 1, 0]         [2, 1, 0]         [2, 2, 0]
[0, 1, 1]            [0, 1, 1]         [0, 1, 1]         [0, 2, 2]
                                       (4 fresh)         (done)

BFS dynamics:
The queue holds same-level cells (i, j) → each outer iteration pops the
entire queue then enqueues neighbours. Outer iterations = minutes.

Code (Python 3)

from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue: deque[tuple[int, int]] = deque()
        fresh = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    queue.append((r, c))
                elif grid[r][c] == 1:
                    fresh += 1

        if fresh == 0:
            return 0

        minutes = 0
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while queue and fresh > 0:
            minutes += 1
            for _ in range(len(queue)):
                r, c = queue.popleft()
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 2
                        fresh -= 1
                        queue.append((nr, nc))

        return minutes if fresh == 0 else -1

Complexity

Comments

10.3 Word Ladder (LC 127)

Problem

Given beginWord, endWord, and a wordList (all same length). Each transformation step replaces exactly one character of the current word so that the new word is in wordList. Return the minimum number of steps to transform beginWord → endWord (counting both ends). Return 0 if impossible.

Example

Input:  beginWord = "hit", endWord = "cog"
        wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: hit → hot → dot → dog → cog  (length 5)

Input:  beginWord = "hit", endWord = "cog"
        wordList = ["hot","dot","dog","lot","log"]
Output: 0    (cog not in wordList)

Constraints

Clarifying questions

Approach

Modelling: each word is a vertex; an edge exists between two words that differ by exactly one character. The problem becomes shortest path in an undirected graph → BFS.

Neighbour generation optimisation: instead of comparing the current word with every word in wordList (O(N·L) per node — too slow), we generate neighbours by replacing each position with a..z (O(26·L) per node).

Illustration for "hit" → "cog":

Level 1: hit
Level 2: hot                (change i→o)
Level 3: dot, lot           (change h→d/l)
Level 4: dog, log           (change t→g)
Level 5: cog                ★ answer (5 steps)

Code (Python 3)

from collections import deque
from typing import List

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        word_set = set(wordList)
        if endWord not in word_set:
            return 0

        queue = deque([(beginWord, 1)])
        visited = {beginWord}
        while queue:
            word, steps = queue.popleft()
            if word == endWord:
                return steps
            for i in range(len(word)):
                for ch in 'abcdefghijklmnopqrstuvwxyz':
                    if ch == word[i]:
                        continue
                    next_word = word[:i] + ch + word[i + 1:]
                    if next_word in word_set and next_word not in visited:
                        visited.add(next_word)
                        queue.append((next_word, steps + 1))
        return 0

Complexity

Comments

10.4 Open the Lock (LC 752)

Problem

A 4-digit lock starts at "0000". Each step rotates one digit up or down by 1 (wrap 0..9). Given a list of deadends (forbidden states) and a target, return the minimum number of steps to reach target, or -1.

Example

Input:  deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation: 0000 → 1000 → 1100 → 1200 → 1201 → 1202 → 0202
            (avoiding every deadend)

Constraints

Clarifying questions

Approach

Implicit state-space graph. Each state is a 4-digit string → 10^4 = 10000 states. From each state there are 8 transitions (4 digits × 2 directions).

BFS: start from "0000", BFS to target. Skip states in deadends.

Illustration of part of BFS:

Level 0: 0000
Level 1: 1000, 9000, 0100, 0900, 0010, 0090, 0001, 0009  (8 neighbours)
Level 2: ... (each node 8 neighbours, except visited / deadend)
...
Level 6: 0202  ★

Code (Python 3)

from collections import deque
from typing import List

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        dead = set(deadends)
        if "0000" in dead:
            return -1
        if target == "0000":
            return 0

        def neighbors(state: str):
            for i in range(4):
                d = int(state[i])
                for delta in (-1, 1):
                    new_d = (d + delta) % 10
                    yield state[:i] + str(new_d) + state[i + 1:]

        visited = {"0000"}
        queue = deque([("0000", 0)])
        while queue:
            state, steps = queue.popleft()
            for nb in neighbors(state):
                if nb in dead or nb in visited:
                    continue
                if nb == target:
                    return steps + 1
                visited.add(nb)
                queue.append((nb, steps + 1))
        return -1

Complexity

Comments

10.5 Shortest Path in Binary Matrix (LC 1091)

Problem

Given an n × n matrix of 0 (passable) and 1 (obstacle), find the shortest path from (0,0) to (n-1,n-1) moving in 8 directions (4 axes + 4 diagonals). Path length = number of cells passed (including start and end). Return -1 if no path exists.

Example

Input:  grid = [[0,0,0],
                [1,1,0],
                [1,1,0]]
Output: 4
Explanation: (0,0) → (0,1) → (1,2) → (2,2)

Constraints

Clarifying questions

Approach

BFS from (0,0) with 8 directions. Each edge has weight 1 (one step = one cell).

Code (Python 3)

from collections import deque
from typing import List

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] != 0 or grid[n - 1][n - 1] != 0:
            return -1
        if n == 1:
            return 1

        dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        queue = deque([(0, 0, 1)])     # (r, c, steps)
        grid[0][0] = 1                  # mark visited
        while queue:
            r, c, steps = queue.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    if (nr, nc) == (n - 1, n - 1):
                        return steps + 1
                    grid[nr][nc] = 1
                    queue.append((nr, nc, steps + 1))
        return -1

Complexity

Comments

10.6 Snakes and Ladders (LC 909)

Problem

Given an n × n board where cells are numbered in zigzag (Snakes & Ladders style). board[i][j] = -1 means an ordinary cell; if >= 1, that’s a snake/ladder that teleports you to the indicated cell.

Each step you roll a six-sided die and move 1..6 cells; if you land on a snake/ladder, follow it immediately. Find the minimum number of rolls to reach cell n*n. Return -1 if impossible.

Example

Input:  board =
        [[-1,-1,-1,-1,-1,-1],
         [-1,-1,-1,-1,-1,-1],
         [-1,-1,-1,-1,-1,-1],
         [-1,35,-1,-1,13,-1],
         [-1,-1,-1,-1,-1,-1],
         [-1,15,-1,-1,-1,-1]]
Output: 4

Constraints

Clarifying questions

Approach

State space: each cell is labelled 1..n². From cell s we can reach s+1, s+2, ..., s+6 (then teleport if a snake/ladder lives there). Each edge = one roll → BFS yields the minimum number of rolls.

Zigzag → coordinate trick: - Row (counting from the bottom): (label - 1) // n. - Column depends on row parity: even rows from the bottom run left→right, odd rows run right→left.

Code (Python 3)

from collections import deque
from typing import List

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        def label_to_pos(label: int) -> tuple[int, int]:
            quot, rem = divmod(label - 1, n)
            row = n - 1 - quot
            col = rem if quot % 2 == 0 else n - 1 - rem
            return row, col

        target = n * n
        visited = {1}
        queue = deque([(1, 0)])     # (square, throws)
        while queue:
            square, throws = queue.popleft()
            for d in range(1, 7):
                nxt = square + d
                if nxt > target:
                    break
                r, c = label_to_pos(nxt)
                if board[r][c] != -1:
                    nxt = board[r][c]
                if nxt == target:
                    return throws + 1
                if nxt not in visited:
                    visited.add(nxt)
                    queue.append((nxt, throws + 1))
        return -1

Complexity

Comments

Chapter summary & decisions

BFS state design (broader than you might think)

State Representative problem
node Shortest path on an unweighted graph
(r, c) Grid (Number of Islands, 01 Matrix)
word Word Ladder
(r, c, k_remaining) Shortest Path with K Obstacles
board_serialized Sliding Puzzle, Open Lock
bitmask_visited Shortest Path Visiting All Nodes
(node, parity) Bipartite, even/odd step counting

Word Ladder — neighbour generation

Snakes & Ladders — 1D ↔︎ 2D

Serpentine n×n board: index i (1..n²) → coordinates:

row_from_bottom = (i - 1) // n     # 0 = bottom row
col_in_row      = (i - 1) % n
r = n - 1 - row_from_bottom
c = col_in_row if row_from_bottom % 2 == 0 else n - 1 - col_in_row

Classic bug: forgetting to flip on odd rows, or 0/1 indexing.

Distance: level BFS vs storing in the queue

Chapter 11 — Depth-First Search (DFS)

DFS goes as deep as possible before backtracking. This is the natural pattern for any tree/graph problem with a recursive structure: depth, path sum, validate, LCA, … This chapter focuses on DFS on trees — easy to memorise and very common in interviews. DFS on grids is covered in Chapter 12 (Island Matrix).

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

Three DFS templates on trees: 1. Top-down: pass state down (e.g. path_so_far, current_sum). 2. Bottom-up: leaves return values upward, the node aggregates from children. 3. Hybrid: pass down and collect back up.

Input format (applies to ALL tree problems in this chapter)

Every tree problem in chapters 10/11/22 uses LeetCode’s standard TreeNode:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Template code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


# 1) Bottom-up: return a value from children
def dfs_bottom_up(node) -> int:
    if not node:
        return 0
    left = dfs_bottom_up(node.left)
    right = dfs_bottom_up(node.right)
    return combine(node.val, left, right)


# 2) Top-down: pass state down
def dfs_top_down(node, state) -> None:
    if not node:
        return
    new_state = update(state, node.val)
    if is_leaf(node):
        # ... record result ...
        return
    dfs_top_down(node.left, new_state)
    dfs_top_down(node.right, new_state)


# 3) Iterative DFS via stack
def dfs_iter(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if not node:
            continue
        # ... visit node ...
        stack.append(node.right)
        stack.append(node.left)     # left ends up on top first

End-of-chapter practice

11.1 Maximum Depth of Binary Tree (LC 104)

Problem

Given the root of a binary tree, return its maximum depth (number of nodes on the longest root-to-leaf path).

Example

Input:  root = [3, 9, 20, null, null, 15, 7]   (LC level-order serialisation)

        Actual tree:
              3
             / \
            9   20
               /  \
              15   7

Output: 3

Constraints

Clarifying questions

Approach

Bottom-up one-liner:

depth(node) = 1 + max(depth(left), depth(right)), base case empty → 0.

Code (Python 3)

class Solution:
    def maxDepth(self, root) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Complexity

Comments

11.2 Path Sum II (LC 113)

Problem

Given root and targetSum, return all root-to-leaf paths whose values sum to targetSum.

Example

Input:  root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]
        targetSum = 22

        Actual tree:
                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \    / \
            7    2  5   1

Output: [[5,4,11,2], [5,8,4,5]]

Constraints

Clarifying questions

Approach

Top-down DFS + backtracking: - Descend each node, decrementing target and appending the node to path. - At a leaf: if target == leaf.val → copy path into the result. - On return (after children) → path.pop() to restore state.

Illustration — the path 5 → 4 → 11 → 2 for target = 22:

DFS(5, target=22, path=[]):
  path=[5], remaining=17
  DFS(4, 17):
    path=[5,4], remaining=13
    DFS(11, 13):
      path=[5,4,11], remaining=2
      DFS(7, 2):  leaf, 7 != 2 → skip
                  pop → path=[5,4,11]
      DFS(2, 2):  leaf, 2 == 2 → ADD [5,4,11,2] to result
                  pop → path=[5,4,11]
      pop → path=[5,4]
    pop → path=[5]
  ...

Code (Python 3)

from typing import List, Optional

class Solution:
    def pathSum(self, root: Optional["TreeNode"], targetSum: int) -> List[List[int]]:
        result: list[list[int]] = []
        path: list[int] = []

        def dfs(node, remaining: int) -> None:
            if not node:
                return
            path.append(node.val)
            remaining -= node.val
            if not node.left and not node.right and remaining == 0:
                result.append(path.copy())
            else:
                dfs(node.left, remaining)
                dfs(node.right, remaining)
            path.pop()                  # backtrack

        dfs(root, targetSum)
        return result

Complexity

Comments

11.3 All Paths From Source to Target (LC 797)

Problem

Given a DAG graph (adjacency list, node i has neighbours graph[i]), return all paths from node 0 to node n - 1.

Example

Input:  graph = [[1,2],[3],[3],[]]
        # graph:  0 → 1 → 3
        #         0 → 2 → 3
Output: [[0,1,3], [0,2,3]]

Constraints

Clarifying questions

Approach

DAG ⇒ no cycle ⇒ no visited required. DFS from 0; whenever we reach n-1, record path.

Code (Python 3)

from typing import List

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        n = len(graph)
        result: list[list[int]] = []
        path: list[int] = [0]

        def dfs(node: int) -> None:
            if node == n - 1:
                result.append(path.copy())
                return
            for nb in graph[node]:
                path.append(nb)
                dfs(nb)
                path.pop()

        dfs(0)
        return result

Complexity

Comments

11.4 Validate Binary Search Tree (LC 98)

Problem

Given root, determine whether the tree is a valid BST under: - Every left descendant: value strictly less than the current node. - Every right descendant: value strictly greater than the current node. - Both subtrees are also BSTs.

Example

Input:  root = [2, 1, 3]
        Actual tree:
              2
             / \
            1   3
Output: true

Input:  root = [5, 1, 4, null, null, 3, 6]
        Actual tree:
              5
             / \
            1   4
               / \
              3   6
Output: false
        (node 3 is in the right subtree of 5, but 3 < 5 → violates BST)

Constraints

Clarifying questions

Approach

Common wrong approach — checking only node.left.val < node.val < node.right.val. Wrong because BST requires the entire left subtree < node, not just the direct child.

Counterexample:

    5
   / \
  1   4
     / \
    3   6

At node 5: 4 < 5 (OK), 1 < 5 (OK). At node 4: 3 < 4 < 6 (OK). Local checks pass, but 3 < 5 is in the right subtree → invalid.

Correct approach — DFS with (low, high) bounds:

dfs(node, low, high): node must satisfy low < node.val < high. Going down: - Left: new bound (low, node.val). - Right: new bound (node.val, high).

Approach 2 — Inorder traversal must be strictly ascending.

BST inorder = sorted sequence. Traverse inorder and check each value exceeds the previous.

Code (Python 3)

import math
from typing import Optional

class Solution:
    """Approach 1 — DFS with (low, high) bounds."""

    def isValidBST(self, root: Optional["TreeNode"]) -> bool:

        def dfs(node, low: float, high: float) -> bool:
            if not node:
                return True
            if not (low < node.val < high):
                return False
            return dfs(node.left, low, node.val) and \
                   dfs(node.right, node.val, high)

        return dfs(root, -math.inf, math.inf)


class SolutionInorder:
    """Approach 2 — inorder traversal."""

    def isValidBST(self, root) -> bool:
        self.prev = -math.inf

        def inorder(node) -> bool:
            if not node:
                return True
            if not inorder(node.left):
                return False
            if node.val <= self.prev:
                return False
            self.prev = node.val
            return inorder(node.right)

        return inorder(root)

Complexity

Comments

11.5 House Robber III (LC 337)

Problem

Given root of a binary tree (LC level-order serialised, e.g. [3,2,3,null,3,null,1]). Each node represents a house with value node.val. The thief cannot rob two adjacent houses (parent ↔︎ child). Return the maximum money he can steal.

Example

Input:  root = [3, 2, 3, null, 3, null, 1]
        Actual tree:
              3
             / \
            2   3
             \   \
              3   1
Output: 7
        (rob 3 + 3 + 1 = 7)

Input:  root = [3, 4, 5, 1, 3, null, 1]
        Actual tree:
              3
             / \
            4   5
           / \   \
          1   3   1
Output: 9
        (rob 4 + 5 = 9)

Constraints

Clarifying questions

Approach

Tree DP — each node returns two values: - rob_this = max money if we rob this node (children skipped). - skip_this = max money if we don’t rob this node (children can do whatever they want).

Recurrences: - rob_this = node.val + left.skip + right.skip - skip_this = max(left.rob, left.skip) + max(right.rob, right.skip)

Answer = max(root.rob, root.skip).

Illustration:

       3
      / \
     2   3
      \   \
       3   1

Post-order DFS:
  node 3 (left-leaf of 2): rob=3, skip=0
  node 1 (right-leaf of right 3): rob=1, skip=0

  node 2: rob = 2 + 0 (no left) + 0 (skip the 3) = 2
          skip = 0 + max(3, 0) = 3
  node 3 (right child of root): rob = 3 + max(0, 0)(no left) + 0 = 3
                                skip = 0 + max(1, 0) = 1

  root 3: rob = 3 + 3 (skip 2) + 1 (skip right-3) = 7
          skip = max(2,3) + max(3,1) = 3 + 3 = 6

Answer: max(7, 6) = 7

Code (Python 3)

from typing import Optional, Tuple

class Solution:
    def rob(self, root: Optional["TreeNode"]) -> int:

        def dfs(node) -> Tuple[int, int]:
            """Return (rob_this, skip_this)."""
            if not node:
                return 0, 0
            l_rob, l_skip = dfs(node.left)
            r_rob, r_skip = dfs(node.right)
            rob_this = node.val + l_skip + r_skip
            skip_this = max(l_rob, l_skip) + max(r_rob, r_skip)
            return rob_this, skip_this

        return max(dfs(root))

Complexity

Comments

11.6 Lowest Common Ancestor of a Binary Tree (LC 236)

Problem

Given root of a binary tree (not a BST) and two nodes p, q, find their lowest common ancestor (LCA) — the lowest node that has both p and q in its subtree.

Example

Input:  root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]
        Actual tree:
              3
             / \
            5   1
           / \ / \
          6  2 0  8
            / \
           7   4

Input:  p = 5, q = 1   → Output: 3
Input:  p = 5, q = 4   → Output: 5   (a node is its own ancestor)

Constraints

Clarifying questions

Approach

Subtle insight: at each node: - If node == p or node == q → return node straight away. - Recurse on left and right. - If both recursions return non-None → node is the LCA. - If only one is non-None → return that one (both p and q lie on the same side).

Code (Python 3)

from typing import Optional

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root is p or root is q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root          # p and q on different sides → root is LCA
        return left if left else right

Complexity

Comments

Chapter summary & decisions

Traversal order cheat sheet

Traversal When to use
Pre-order (root → L → R) Serialise, clone, copy
In-order (L → root → R) BST sorted output, kth smallest
Post-order (L → R → root) Aggregate from children (tree DP, diameter)
Level-order (BFS) By layer, by distance

DFS return-value design (heart of tree DP)

def dfs(node):
    if not node: return base
    L = dfs(node.left)
    R = dfs(node.right)
    # combine L, R with node.val → answer for this subtree
    # UPDATE global answer if needed
    return result_to_pass_up

Validate BST — global bounds

House Robber III — (rob, skip) trace

Tree:

    3
   / \
  2   3
   \   \
    3   1

Post-order returns (rob_this, skip_this): - Leaf 3 (left of 2): (3, 0). - Leaf 1 (right of right-3): (1, 0). - Node 2: rob = 2 + 0 = 2, skip = max(3,0) = 3 → (2, 3). - Node 3 (right of root): rob = 3 + 0 = 3, skip = max(1,0) = 1 → (3, 1). - Root 3: rob = 3 + 3 + 1 = 7, skip = max(2,3) + max(3,1) = 3 + 3 = 6 → max(7,6) = 7.

LCA variants — choose wisely

Tree type How
General binary tree Bottom-up recursion, return node if it contains p or q (LC 236)
BST Compare values with root, walk one side (LC 235) — O(log n)
With parent pointer Hash ancestors of p, then walk up from q

Chapter 12 — Island Matrix Traversal

A 2D grid is really an implicit graph: each cell is a node, and the 4 adjacent cells (up/down/left/right) are edges. Every “island” / “region painting” / “flood fill” problem is just DFS/BFS on that graph. This chapter teaches 4 tricks specific to grids: (1) flood fill, (2) multi-source BFS from the border, (3) reverse thinking (mark what we don’t need), (4) mutating the input to mark visited.

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

Template code

from collections import deque
from typing import List

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 1) Flood fill DFS (recursive)
def flood_fill(grid: List[List[int]], r: int, c: int, marker: int) -> int:
    rows, cols = len(grid), len(grid[0])
    if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
        return 0
    grid[r][c] = marker             # mark visited
    size = 1
    for dr, dc in DIRS:
        size += flood_fill(grid, r + dr, c + dc, marker)
    return size


# 2) Multi-source BFS from all boundary or all "special" cells
def multi_source_bfs(grid, sources):
    queue = deque(sources)
    visited = set(sources)
    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc))
    return visited

End-of-chapter practice

12.1 Number of Islands (LC 200)

Problem

Given a grid m × n with '1' = land and '0' = water. An island is a maximally 4-connected region of land. Count the number of islands.

Example

Input:
[["1","1","1","1","0"],
 ["1","1","0","1","0"],
 ["1","1","0","0","0"],
 ["0","0","0","0","0"]]
Output: 1   (all "1"s connect into one island)

Input:
[["1","1","0","0","0"],
 ["1","1","0","0","0"],
 ["0","0","1","0","0"],
 ["0","0","0","1","1"]]
Output: 3   (top-left, middle, bottom-right)

Constraints

Clarifying questions

Approach

Classic flood fill pattern. Walk every cell: - If it’s '1' and not yet visited → increment counter, DFS/BFS to mark the whole island as visited (change '1' → '0' to avoid a separate set).

Illustration for the 4×5 grid above:

Step 1, cell (0,0) = '1' → DFS:
[1 1 0 0 0]      [* * 0 0 0]
[1 1 0 0 0]  →   [* * 0 0 0]
[0 0 1 0 0]      [0 0 1 0 0]
[0 0 0 1 1]      [0 0 0 1 1]
                 (island 1 marked)

Step 2, hit (2,2) = '1' → DFS (marks itself only):
[* * 0 0 0]
[* * 0 0 0]
[0 0 * 0 0]
[0 0 0 1 1]

Step 3, hit (3,3) = '1' → DFS:
[* * 0 0 0]
[* * 0 0 0]
[0 0 * 0 0]
[0 0 0 * *]

Count: 3 islands

Code (Python 3)

from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        rows, cols = len(grid), len(grid[0])
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(r: int, c: int) -> None:
            if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != '1':
                return
            grid[r][c] = '0'              # mark visited
            for dr, dc in DIRS:
                dfs(r + dr, c + dc)

        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    dfs(r, c)
        return count

Complexity

Comments

12.2 Max Area of Island (LC 695)

Problem

Same 0/1 grid. Return the largest area of any island (cell count), or 0 if there are no islands.

Example

Input:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6

Constraints

Clarifying questions

Approach

A variant of 12.1, but DFS returns the size instead of void. Take max across all DFS starts.

Code (Python 3)

from typing import List

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(r: int, c: int) -> int:
            if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
                return 0
            grid[r][c] = 0
            return 1 + sum(dfs(r + dr, c + dc) for dr, dc in DIRS)

        best = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    best = max(best, dfs(r, c))
        return best

Complexity

Comments

12.3 Surrounded Regions (LC 130)

Problem

Given a grid of 'X' and 'O'. Flip every 'O' region that is fully surrounded by 'X' (regions that don’t touch the grid boundary) into 'X'. 'O' regions touching the boundary are preserved.

Example

Input:  board = [['X','X','X','X'],
                 ['X','O','O','X'],
                 ['X','X','O','X'],
                 ['X','O','X','X']]
Output: board = [['X','X','X','X'],
                 ['X','X','X','X'],
                 ['X','X','X','X'],
                 ['X','O','X','X']]

(mutate in place; the 'O' at (3,1) touches the bottom border → keep;
 the inner 'O' cluster is surrounded → flip to 'X')

Constraints

Clarifying questions

Approach

Reverse thinking — an extremely useful pattern: - Instead of finding the surrounded 'O' regions, find the 'O' regions that touch the border (much easier). - Mark them (e.g. temporarily change to '#'). - Final pass: - '#' → 'O' (keep). - Remaining 'O' → 'X' (flip).

Illustration:

Initial grid:               After DFS from boundary 'O's (marker '#'):
X X X X                     X X X X
X O O X                     X O O X     (the O at (1,1),(1,2) does NOT touch
X X O X         →           X X O X      the border → not marked)
X O X X                     X # X X     (O at (3,1) touches border → marked)

Final sweep:
'#' → 'O'; 'O' → 'X':
X X X X
X X X X
X X X X
X O X X

Code (Python 3)

from typing import List

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board:
            return
        rows, cols = len(board), len(board[0])

        def dfs(r: int, c: int) -> None:
            if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != 'O':
                return
            board[r][c] = '#'
            dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)

        # 1. DFS from every boundary 'O' — mark them as '#'.
        for r in range(rows):
            dfs(r, 0)
            dfs(r, cols - 1)
        for c in range(cols):
            dfs(0, c)
            dfs(rows - 1, c)

        # 2. Flip: '#' → 'O' (keep); 'O' → 'X' (flip).
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == '#':
                    board[r][c] = 'O'

Complexity

Comments

12.4 Pacific Atlantic Water Flow (LC 417)

Problem

Given a matrix heights[i][j] representing island heights. The left and top edges border the Pacific; the right and bottom edges border the Atlantic. Water flows from (r, c) to a neighbouring cell of height ≤ (r, c).

Return all (r, c) from which water can flow to both oceans.

Example

Input:  heights = [[1,2,2,3,5],
                   [3,2,3,4,4],
                   [2,4,5,3,1],
                   [6,7,1,4,5],
                   [5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Constraints

Clarifying questions

Approach

Forward thinking — TLE. For each cell, BFS to see which oceans it can reach. Worst-case O((mn)²).

Reverse thinking — O(m · n).

Instead of “which cells flow to the ocean?”, ask “where can the ocean climb up to?”. The ocean climbs only to cells of height ≥ the current one.

Illustration — Pacific reach (P) and Atlantic reach (A) on a 5x5 matrix:

P P P P P/A                   A A A A A
P . . . A             P/A . . . A
P . . . A             P . . . A
P/A . . . A             P . . . A
P/A A A A A             P P P P P

P ∩ A = cells in both sets → answer.

Code (Python 3)

from typing import List

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        if not heights:
            return []
        rows, cols = len(heights), len(heights[0])
        pacific: set[tuple[int, int]] = set()
        atlantic: set[tuple[int, int]] = set()

        def dfs(r: int, c: int, visited: set, prev_h: int) -> None:
            if (r, c) in visited:
                return
            if not (0 <= r < rows and 0 <= c < cols):
                return
            if heights[r][c] < prev_h:    # ocean cannot climb to a lower cell
                return
            visited.add((r, c))
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                dfs(r + dr, c + dc, visited, heights[r][c])

        # Pacific: left + top edges.
        for r in range(rows):
            dfs(r, 0, pacific, heights[r][0])
        for c in range(cols):
            dfs(0, c, pacific, heights[0][c])
        # Atlantic: right + bottom edges.
        for r in range(rows):
            dfs(r, cols - 1, atlantic, heights[r][cols - 1])
        for c in range(cols):
            dfs(rows - 1, c, atlantic, heights[rows - 1][c])

        return [[r, c] for r, c in pacific & atlantic]

Complexity

Comments

12.5 Walls and Gates (LC 286)

Problem

Given rooms: an m × n integer matrix with three meaningful values: - -1 = wall (blocks the way). - 0 = gate. - INF (= 2³¹ - 1) = empty room.

Fill each empty room with the shortest distance (4-direction steps) to the nearest gate. If a room can’t reach any gate, leave it as INF.

Example

Input:  rooms = [[INF, -1,  0, INF],
                 [INF,INF,INF, -1],
                 [INF, -1,INF, -1],
                 [  0, -1,INF,INF]]
        (-1 = wall, 0 = gate, INF = empty room)

Output: rooms = [[3, -1, 0, 1],
                 [2,  2, 1,-1],
                 [1, -1, 2,-1],
                 [0, -1, 3, 4]]
        (mutate in place; each cell = 4-step distance to the nearest gate)

Constraints

Clarifying questions

Approach

Multi-source BFS — enqueue all gates simultaneously. They expand outward; each cell receives a distance equal to the steps from the nearest gate.

Why is multi-source better than BFS from each gate? Multi-source O(mn), per-gate BFS O(gates · mn) — gates can be O(mn).

Code (Python 3)

from collections import deque
from typing import List

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        if not rooms:
            return
        rows, cols = len(rooms), len(rooms[0])
        queue: deque[tuple[int, int]] = deque()
        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == 0:
                    queue.append((r, c))

        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while queue:
            r, c = queue.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                # Only write to cells still at INF — BFS first-write = min.
                if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == 2147483647:
                    rooms[nr][nc] = rooms[r][c] + 1
                    queue.append((nr, nc))

Complexity

Comments

12.6 01 Matrix (LC 542)

Problem

Given a matrix mat containing only 0 and 1. Return a matrix of the same size where each cell = the distance (4-direction steps) to the nearest 0.

Example

Input:  mat = [[0,0,0],
               [0,1,0],
               [1,1,1]]
Output:       [[0,0,0],
               [0,1,0],
               [1,2,1]]
        (each cell = Manhattan distance to its nearest 0)

Constraints

Clarifying questions

Approach

Same as Walls and Gates: multi-source BFS from every 0. The initial distance of each 0 is 0; each 1 is unknown.

Alternative — 2-pass DP, O(m · n): - Pass 1 (top-left → bottom-right): dp[r][c] = min(dp[r-1][c], dp[r][c-1]) + 1. - Pass 2 (bottom-right → top-left): dp[r][c] = min(dp[r][c], dp[r+1][c]+1, dp[r][c+1]+1).

Both are O(m · n). BFS is more intuitive; DP is space-efficient.

Code (Python 3)

from collections import deque
from typing import List

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        INF = float('inf')
        dist = [[INF] * cols for _ in range(rows)]

        queue: deque[tuple[int, int]] = deque()
        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    dist[r][c] = 0
                    queue.append((r, c))

        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while queue:
            r, c = queue.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] > dist[r][c] + 1:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
        return dist


class SolutionDP:
    """Two-pass DP — space-efficient (can be in-place where allowed)."""

    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        INF = rows + cols + 1
        dist = [[0 if mat[r][c] == 0 else INF
                 for c in range(cols)] for r in range(rows)]
        # Pass 1: top-left → bottom-right.
        for r in range(rows):
            for c in range(cols):
                if dist[r][c] == 0:
                    continue
                top = dist[r-1][c] if r > 0 else INF
                left = dist[r][c-1] if c > 0 else INF
                dist[r][c] = min(top, left) + 1
        # Pass 2: bottom-right → top-left.
        for r in range(rows - 1, -1, -1):
            for c in range(cols - 1, -1, -1):
                if dist[r][c] == 0:
                    continue
                bot = dist[r+1][c] + 1 if r < rows - 1 else INF
                right = dist[r][c+1] + 1 if c < cols - 1 else INF
                dist[r][c] = min(dist[r][c], bot, right)
        return dist

Complexity

Comments

Chapter summary & decisions

Matrix traversal checklist

  1. Direction array: dirs = [(-1,0),(1,0),(0,-1),(0,1)] (4-conn) or 8-conn.
  2. Bounds: 0 <= nr < R and 0 <= nc < C.
  3. Visited: in-place mark (change '1' → '0' or #) or set?
  4. Mutation OK? Ask the interviewer; otherwise use a 2D visited.
  5. Stack overflow for recursive DFS: a 1000×1000 grid can exceed the limit. Use an iterative stack or BFS.

Boundary-first technique

For Surrounded Regions (LC 130) and Pacific Atlantic (LC 417): - “A cell that does not satisfy the property” = “a cell that is connected to the boundary”. - Seed BFS/DFS from the boundary, mark reachable cells; remaining cells are the surrounded ones.

Multi-source BFS

For 01 Matrix (LC 542) and Walls and Gates (LC 286): - Enqueue every source up front (cell 0 for 542, gate 0 for 286). - BFS by level → distances spread outward. Each cell is visited once ⇒ O(R·C).

In-place mark vs visited set

Criterion In-place Set/2D bool
Extra memory O(1) O(R·C)
Mutates input? Yes No
Concurrency / restore Hard Easy
Pick when Mutation allowed & O(1) extra needed Grid is immutable or needs re-run

Chapter 13 — Topological Sort

Topological Sort orders the vertices of a DAG (Directed Acyclic Graph) so that for every edge u → v, u appears before v in the order. This is the mandatory pattern for any “complete-in-dependency-order” problem: build systems, task schedulers, course prerequisites, …

Chapter objectives

After this chapter, you will be able to:

Edge-direction convention

One of the most common topo-sort bugs is drawing the edges in the wrong direction. For this reason, the entire book follows one convention:

Real description           Edge in graph         Indegree
─────────────────────────────────────────────────────────
"a must come before b"     a → b                 indeg[b] += 1
"b depends on a"           a → b                 indeg[b] += 1
"a is prerequisite of b"   a → b                 indeg[b] += 1
─────────────────────────────────────────────────────────
LC 207/210 input:          prerequisites[i] = [course, prereq]
                           i.e. [b, a] meaning "to do b, must do a"
                           → edge a → b (prereq → course)
─────────────────────────────────────────────────────────
LC 269 Alien Dict:         words[i] < words[i+1] in lex order
                           → first differing character: c1 < c2
                           → edge c1 → c2

Kahn’s invariant: popping a node with indeg == 0 ↔︎ “nobody must finish before it”.

Every topo-sort problem in this book uses the convention u → v means u finishes before v. When the problem uses different wording, always draw 2–3 edges on paper first to make sure your code’s edge direction matches the problem statement.

When to use this pattern?

Two classic algorithms:

  1. Kahn’s algorithm (BFS) — count indegree, enqueue nodes with indeg=0.
  2. DFS with post-order — DFS recursively, push the node when its subtree is done; reverse the stack.

Both are O(V + E). We default to Kahn because it’s easy to extend to “min levels”.

Template code

from collections import defaultdict, deque
from typing import List

def topo_sort_kahn(n: int, edges: List[tuple]) -> List[int]:
    graph = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indeg[v] += 1

    queue = deque(i for i in range(n) if indeg[i] == 0)
    order: list[int] = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)

    return order if len(order) == n else []     # empty = cycle exists

End-of-chapter practice

13.1 Course Schedule II (LC 210)

Problem

Given numCourses courses and prerequisites[i] = [a, b] (taking a requires finishing b first), return a valid order of courses, or [] if there is a cycle.

Example

Input:  numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0, 1, 2, 3]   (or [0, 2, 1, 3])
Explanation:
  Edges: 0 → 1, 0 → 2, 1 → 3, 2 → 3.

Constraints

Clarifying questions

Approach

Kahn’s algorithm — straight from the template. As we pop, append to order. At the end: if len(order) == numCourses → return order; otherwise a cycle exists.

Illustration for [[1,0],[2,0],[3,1],[3,2]]:

Graph:        0
             / \
            1   2
             \ /
              3

Initial indeg: [0, 1, 1, 2]
queue = [0]                   (indeg 0)

Pop 0 → order=[0]
  decrement indeg[1], indeg[2] → [_, 0, 0, 2]
  queue = [1, 2]

Pop 1 → order=[0, 1]
  decrement indeg[3] → [_, _, _, 1]

Pop 2 → order=[0, 1, 2]
  decrement indeg[3] → [_, _, _, 0]
  queue = [3]

Pop 3 → order=[0, 1, 2, 3]

len(order)=4=numCourses → return [0, 1, 2, 3]  ✓

Code (Python 3)

from collections import defaultdict, deque
from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        indeg = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            indeg[a] += 1

        queue = deque(i for i, d in enumerate(indeg) if d == 0)
        order: list[int] = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for nb in graph[node]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    queue.append(nb)

        return order if len(order) == numCourses else []

Complexity

Comments

13.2 Alien Dictionary (LC 269)

Problem

An alien language uses Latin letters in a different order. Given a list of words sorted in that order, find a valid letter ordering (a string of letters). Return "" if contradictory.

Example

Input:  words = ["wrt","wrf","er","ett","rftt"]
        (the list of words sorted by the alien alphabet)
Output: "wertf"  (one valid alphabet order; many answers may exist)
Explanation:
  wrt < wrf  → t < f
  wrf < er   → w < e
  er  < ett  → r < t
  ett < rftt → e < r
  → topo: w < e < r < t < f

Input:  words = ["z","x","z"]
Output: ""             (cyclic contradiction: z<x from pair 1 but x<z from pair 2)

Constraints

Clarifying questions

Approach

Two steps:

  1. Extract order relations from adjacent pairs (words[i], words[i+1]):
  2. Topological sort on those relations.

Illustration for ["wrt","wrf","er","ett","rftt"]:

Pair 1: wrt vs wrf
  first diff at index 2 → t < f
  → edge t → f

Pair 2: wrf vs er
  first diff at index 0 → w < e
  → edge w → e

Pair 3: er vs ett
  first diff at index 1 → r < t
  → edge r → t

Pair 4: ett vs rftt
  first diff at index 0 → e < r
  → edge e → r

Graph: w → e → r → t → f
Topo: w, e, r, t, f → "wertf"

Code (Python 3)

from collections import defaultdict, deque
from typing import List

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # Initialise indeg for every character that appears.
        indeg = {ch: 0 for w in words for ch in w}
        graph = defaultdict(set)

        # Extract relations from adjacent pairs.
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            # Invalid prefix edge case.
            if len(w1) > len(w2) and w1.startswith(w2):
                return ""
            for c1, c2 in zip(w1, w2):
                if c1 != c2:
                    if c2 not in graph[c1]:
                        graph[c1].add(c2)
                        indeg[c2] += 1
                    break

        # Kahn's.
        queue = deque(ch for ch, d in indeg.items() if d == 0)
        order: list[str] = []
        while queue:
            ch = queue.popleft()
            order.append(ch)
            for nb in graph[ch]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    queue.append(nb)

        return ''.join(order) if len(order) == len(indeg) else ""

Complexity

Comments

13.3 Minimum Height Trees (LC 310)

Problem

Input: n (number of nodes) and edges: List[List[int]] — a list of n-1 undirected edges [u, v] describing a tree. Nodes labelled 0..n-1.

Find every root that yields the minimum tree height. Return the list of such roots (1 or 2 possible).

Example

Input:  n=6, edges = [[0,3],[1,3],[2,3],[4,3],[5,4]]
Tree:    0   1   2
          \  |  /
           \ | /
             3
             |
             4
             |
             5
Output: [3, 4]

Constraints

Clarifying questions

Approach

Insight: the centroid of a tree (1 or 2 nodes) minimises tree height. To find it: BFS from the leaves, “peeling” inwards.

Procedure: 1. Build the graph + count degree. 2. Enqueue every leaf (degree == 1). 3. Loop: pop one layer of leaves, decrement neighbour degrees, push new leaves (degree == 1). 4. When ≤ 2 nodes remain → those are the centroid(s).

Illustration:

Initial leaves: [0, 1, 2, 5]
Peel → remaining: [3, 4]
                3 (degree=1 after peel), 4 (degree=1 after peel)
→ ≤ 2 nodes → centroids = [3, 4]

Code (Python 3)

from collections import defaultdict, deque
from typing import List

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        graph = defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        leaves = deque(i for i in range(n) if len(graph[i]) == 1)
        remaining = n
        while remaining > 2:
            size = len(leaves)
            remaining -= size
            for _ in range(size):
                leaf = leaves.popleft()
                nb = next(iter(graph[leaf]))    # a leaf has exactly one neighbour
                graph[nb].remove(leaf)
                if len(graph[nb]) == 1:
                    leaves.append(nb)
        return list(leaves)

Complexity

Comments

13.4 Sort Items by Groups Respecting Dependencies (LC 1203)

Problem

Given n items, each belonging to a group (group[i] = -1 means not yet assigned — should get its own group). beforeItems[i] lists items that must come before item i. Arrange items so that: - beforeItems are respected. - Items of the same group are contiguous.

Return [] if impossible.

Example

Input:  n=8, m=2, group=[-1,-1,1,0,0,1,0,-1], beforeItems=[[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

Constraints

Clarifying questions

Approach

Two topological sorts: 1. Sort the groups among themselves (an item-level edge i → j across groups becomes a group-level edge). 2. Within each group, sort its items. 3. Concatenate the result: use the group order; inside each group write its items by item order.

Pre-processing: any item with group[i] == -1 → assign its own private group so “no group” doesn’t influence the topology.

Code (Python 3)

from collections import defaultdict, deque
from typing import List

class Solution:
    def sortItems(
        self, n: int, m: int,
        group: List[int], beforeItems: List[List[int]]
    ) -> List[int]:
        # Assign a private group to items with -1.
        for i in range(n):
            if group[i] == -1:
                group[i] = m
                m += 1

        item_graph = defaultdict(list)
        item_indeg = [0] * n
        group_graph = defaultdict(set)
        group_indeg = defaultdict(int)

        for cur, befores in enumerate(beforeItems):
            for prev in befores:
                item_graph[prev].append(cur)
                item_indeg[cur] += 1
                if group[prev] != group[cur]:
                    if group[cur] not in group_graph[group[prev]]:
                        group_graph[group[prev]].add(group[cur])
                        group_indeg[group[cur]] += 1

        def topo(nodes, graph, indeg) -> List[int]:
            queue = deque(x for x in nodes if indeg[x] == 0)
            out: list = []
            while queue:
                x = queue.popleft()
                out.append(x)
                for nb in graph[x]:
                    indeg[nb] -= 1
                    if indeg[nb] == 0:
                        queue.append(nb)
            return out if len(out) == len(nodes) else []

        item_order = topo(range(n), item_graph, item_indeg)
        if not item_order:
            return []
        group_order = topo(range(m), group_graph, group_indeg)
        if not group_order:
            return []

        # Bucket by group respecting group_order; items keep item_order.
        bucket: dict[int, list[int]] = defaultdict(list)
        for item in item_order:
            bucket[group[item]].append(item)
        result: list[int] = []
        for g in group_order:
            result.extend(bucket[g])
        return result

Complexity

Comments

13.5 Sequence Reconstruction (LC 444)

Problem

Given nums (a permutation of 1..n) and sequences (a list of sub-sequences), check whether nums is the unique topological order implied by sequences.

Example

Input:  nums = [1, 2, 3], sequences = [[1,2],[1,3]]
Output: False
Explanation: from [1,2] and [1,3] → either [1,2,3] or [1,3,2] → not unique.

Input:  nums = [1, 2, 3], sequences = [[1,2],[1,3],[2,3]]
Output: True

Constraints

Clarifying questions

Approach

Run Kahn’s. For uniqueness, every level must contain exactly one node with indeg == 0 — ≥ 2 ⇒ multiple topo orders ⇒ False. Additionally the pop order must match nums.

Code (Python 3)

from collections import defaultdict, deque
from typing import List

class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        n = len(nums)
        graph = defaultdict(set)
        indeg = [0] * (n + 1)
        for seq in sequences:
            for i in range(len(seq) - 1):
                u, v = seq[i], seq[i + 1]
                if v not in graph[u]:
                    graph[u].add(v)
                    indeg[v] += 1

        queue = deque(i for i in range(1, n + 1) if indeg[i] == 0)
        idx = 0
        while queue:
            if len(queue) > 1:
                return False              # >1 choice → not unique
            x = queue.popleft()
            if nums[idx] != x:
                return False              # diverges from nums
            idx += 1
            for nb in graph[x]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    queue.append(nb)
        return idx == n

Complexity

Comments

13.6 Parallel Courses (LC 1136)

Problem

Given n courses and relations [a, b] (take a before b). Each semester you may take any number of courses provided all their prerequisites are done. Return the minimum number of semesters to take all courses, or -1 if a cycle exists.

Example

Input:  n=3, relations=[[1,3],[2,3]]
Output: 2
Explanation: Semester 1 take [1,2], semester 2 take [3]

Constraints

Clarifying questions

Approach

Kahn’s BFS but count by level (semester). Each outer iteration of BFS processes the entire current queue = the courses takeable in the same semester.

Code (Python 3)

from collections import defaultdict, deque
from typing import List

class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        graph = defaultdict(list)
        indeg = [0] * (n + 1)
        for u, v in relations:
            graph[u].append(v)
            indeg[v] += 1

        queue = deque(i for i in range(1, n + 1) if indeg[i] == 0)
        taken = 0
        semesters = 0
        while queue:
            semesters += 1
            for _ in range(len(queue)):
                u = queue.popleft()
                taken += 1
                for v in graph[u]:
                    indeg[v] -= 1
                    if indeg[v] == 0:
                        queue.append(v)
        return semesters if taken == n else -1

Complexity

Comments

Chapter summary & decisions

Topo + DP framing (bridge to Chapter 43)

Sequence Reconstruction (LC 444) — why the queue must always have ≤ 1 element?

Alien Dictionary (LC 269) — invalid prefix case

If w_i is a prefix of w_{i-1} (e.g. ["abc", "ab"]), the dictionary is invalid → return "". Check this BEFORE building edges (don’t forget to break correctly).

Sort Items by Groups (LC 1203) — 2-layer DAG

items 5,6 ∈ groupA   items 7,8 ∈ groupB   items 9 ∈ -1 (private)

Item DAG:  5 → 6,  7 → 8,  6 → 7   (intra + cross-group)
Group DAG: A → B   (because 6 → 7 with 6 ∈ A, 7 ∈ B)

→ Topo on group order → within each group topo on item order.

Chapter 14 — Interval

Intervals ([start, end]) cover many important calendar/scheduling/booking problems. Chapter 4 (Sorting) already touched Merge Intervals and Meeting Rooms II; this chapter dives deep into 8 operation patterns on intervals (merge, insert, intersection, overlap, free time) — unavoidable in interviews for calendar (Google Calendar) and booking (Airbnb, Booking) companies.

Chapter objectives

After this chapter, you will be able to:

When to use this pattern?

Four canonical relations between intervals A = [a₁, a₂], B = [b₁, b₂]:

1. Disjoint:        A.end < B.start  →  A entirely before B
2. Touching:        A.end == B.start →  adjacent; may merge depending on problem
3. Partial overlap: A.start < B.start ≤ A.end < B.end
4. Containment:     A.start ≤ B.start ≤ B.end ≤ A.end

Template code

from typing import List

# 1) Merge two overlapping intervals
def merge_two(a, b):
    return [min(a[0], b[0]), max(a[1], b[1])]


# 2) Overlap check (touching counts as overlap)
def overlaps(a, b) -> bool:
    return a[0] <= b[1] and b[0] <= a[1]


# 3) Sweep line: same pattern for every "max overlap" question
events: List[tuple[int, int]] = []
for s, e in intervals:
    events.append((s, +1))       # open
    events.append((e, -1))       # close
events.sort()
cur = peak = 0
for _, delta in events:
    cur += delta
    peak = max(peak, cur)

End-of-chapter practice

14.1 Merge Intervals (LC 56) — recap

Fully solved in Chapter 4.2 under the Sorting lens. Here we summarise it under the “interval” lens and extend the follow-ups.

Problem

Merge overlapping intervals. [1,3] and [2,6] → [1,6].

Approach

Sort by start. Walk once and keep last = the most recent interval in the output. If cur.start <= last.end → last.end = max(last.end, cur.end); otherwise push cur.

Code (Python 3)

class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x[0])
        result = []
        for cur in intervals:
            if result and cur[0] <= result[-1][1]:
                result[-1][1] = max(result[-1][1], cur[1])
            else:
                result.append(cur[:])
        return result

Complexity

Extra comments for the interval lens

14.2 Insert Interval (LC 57)

Problem

Given intervals sorted by start and pairwise non-overlapping, insert newInterval and merge as needed.

Example

Input:  intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Input:  intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

Constraints

Clarifying questions

Approach

Approach 1 — O(n) single sweep in 3 phases.

  1. Before newInterval: push every interval with end < newInterval.start.
  2. Overlapping: for every interval with start <= newInterval.end, extend newInterval (start = min, end = max). At the end push newInterval.
  3. After newInterval: push the remaining intervals.

Approach 2 — Concat + merge (reuse problem 14.1). Simple but O(n log n) from the unnecessary sort.

Illustration for intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], new = [4,8]:

Number line:
1   3   5   6  7  8  10        12      16
├─┤ ├───┤ ├─┤  ├──┤            ├──────┤
        ├──────────┤  new = [4, 8]

Phase 1 (end < 4):  [1, 2]
                     result = [[1,2]]

Phase 2 (start <= 8):
  [3, 5]: extend newInterval = [min(4,3), max(8,5)] = [3, 8]
  [6, 7]: extend = [3, 8]
  [8, 10]: extend = [3, 10]
  Push [3, 10]
                     result = [[1,2], [3,10]]

Phase 3: remaining [12, 16]
                     result = [[1,2], [3,10], [12,16]]  ✓

Code (Python 3)

from typing import List

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result: list[list[int]] = []
        i, n = 0, len(intervals)
        # 1) Before newInterval.
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1
        # 2) Overlap — extend newInterval.
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        result.append(newInterval)
        # 3) After newInterval.
        while i < n:
            result.append(intervals[i])
            i += 1
        return result

Complexity

Comments

14.3 Non-overlapping Intervals (LC 435)

Problem

Given an array of intervals, return the minimum number of intervals to remove so the rest are pairwise non-overlapping.

Example

Input:  intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: remove [1,3] → remainder [1,2],[2,3],[3,4] is non-overlapping.

Input:  intervals = [[1,2],[1,2],[1,2]]
Output: 2

Input:  intervals = [[1,2],[2,3]]
Output: 0              (already non-overlapping, nothing to remove)

(each [start, end] represents the half-open interval [start, end))

Constraints

Clarifying questions

Approach

Greedy — sort by end ascending. Keeping the interval with the smallest end leaves the most “room” for subsequent ones.

Pseudocode: - Sort by end. - Keep last_end = -∞. For each interval [s, e]: - If s >= last_end → keep (no overlap), last_end = e. - Otherwise → count removal.

Why sort by end, not start? Greedy works because: “always pick the interval with the earliest end” maximises the remaining “free time” — provable by induction.

Illustration for [[1,2],[2,3],[3,4],[1,3]]:

Sort by end:  [[1,2], [2,3], [1,3], [3,4]]
                       end=2   end=3   end=3   end=4

Walk:
  [1,2]: start=1 >= -inf → keep; last_end=2          kept: 1
  [2,3]: start=2 >= 2    → keep; last_end=3          kept: 2
  [1,3]: start=1 < 3     → remove                     removed: 1
  [3,4]: start=3 >= 3    → keep; last_end=4          kept: 3

Kept 3, removed 1 → answer = 1.

Code (Python 3)

from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[1])
        kept = 1
        last_end = intervals[0][1]
        for s, e in intervals[1:]:
            if s >= last_end:
                kept += 1
                last_end = e
        return len(intervals) - kept

Complexity

Comments

14.4 Meeting Rooms II (LC 253) — recap

Fully solved in Chapter 4.4. Here we summarise and link.

Problem

Find the minimum number of rooms needed for all meetings.

Approach

Three approaches (heap, sweep-line events, chronological two-pointer) — all O(n log n). Sweep line is the canonical interval language.

Code (Python 3)

from typing import List

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        events = [(s, +1) for s, _ in intervals] + [(e, -1) for _, e in intervals]
        events.sort(key=lambda x: (x[0], x[1]))
        cur = peak = 0
        for _, d in events:
            cur += d
            peak = max(peak, cur)
        return peak

Complexity

Additional remarks

14.5 Minimum Number of Arrows to Burst Balloons (LC 452)

Problem

Given an array of balloons [x_start, x_end] (each balloon spans an interval on the x-axis). A vertical arrow shot at x = X bursts every balloon with x_start <= X <= x_end. Find the minimum number of arrows needed to burst all balloons.

Example

Input:  points = [[10,16],[2,8],[1,6],[7,12]]
        (each entry [xstart, xend] is one balloon spanning the closed [xstart, xend])
Output: 2   (at least 2 arrows: shoot x=6 bursts [1,6] and [2,8]; shoot x=11 bursts [7,12] and [10,16])
Explanation:
  1 arrow at x = 6 bursts [1,6] and [2,8].
  1 arrow at x = 11 bursts [7,12] and [10,16].

Constraints

Clarifying questions

Approach

Equivalent to problem 14.3 (Non-overlapping Intervals): each arrow corresponds to a group of balloons that share a common intersection. Count groups = number of arrows.

Greedy sort by end just like 14.3: - Sort balloons by end. - Keep last_end = -∞. For each balloon [s, e]: - If s > last_end → need a new arrow; last_end = e. - Otherwise → this balloon is burst by the current arrow.

Code (Python 3)

from typing import List

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        points.sort(key=lambda x: x[1])
        arrows = 1
        last_end = points[0][1]
        for s, e in points[1:]:
            if s > last_end:        # disjoint → new arrow needed
                arrows += 1
                last_end = e
        return arrows

Complexity

Comments

14.6 Employee Free Time (LC 759)

Problem

Given schedule[i] = a list of busy intervals for employee i. Return every interval that is free for all employees, sorted ascending. (Skip the time before the first busy or after the last finishes.)

Example

Input:  schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3, 4]]
Explanation:
  Union of busy: [1,3] (from [1,2] + [1,3]), [4,10] (from [5,6] + [4,10]).
  Free in between: [3, 4].

Constraints

Clarifying questions

Approach

Step 1: combine every busy interval into one big list independent of employees. Step 2: sort by start, merge (like problem 14.1). Step 3: gaps between merged intervals = free time.

Code (Python 3)

from typing import List

class Interval:
    def __init__(self, start: int = 0, end: int = 0):
        self.start, self.end = start, end


class Solution:
    def employeeFreeTime(self, schedule: "List[List[Interval]]") -> "List[Interval]":
        all_busy: list[tuple[int, int]] = []
        for emp_sched in schedule:
            for iv in emp_sched:
                all_busy.append((iv.start, iv.end))
        all_busy.sort()

        merged: list[list[int]] = []
        for s, e in all_busy:
            if merged and s <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], e)
            else:
                merged.append([s, e])

        free = []
        for i in range(1, len(merged)):
            if merged[i - 1][1] < merged[i][0]:
                free.append(Interval(merged[i - 1][1], merged[i][0]))
        return free

Complexity

Comments

Chapter summary & decisions

Interval-convention checklist

  1. Closed [s, e] or half-open [s, e)?
  2. Sort by start (Merge, Insert) or sort by end (Greedy, Min Arrows)?
  3. Sweep-line tie-break: for events at the same time t:

Employee Free Time — visual

e1: |==1==|       |==3==|
e2:    |==2==|       |==4==|
sort all → merge ⇒ busy: [1∪2] [3∪4]
free = complement between busy blocks

Recap lens (why Merge & Meeting reappear)

End of the free preview

You’ve reached the end of the first 14 chapters published free on the web. The complete book — 44 chapters + appendix (288 problems with full Python 3 solutions) — is available on Gumroad:

🛒 Buy the full book on Gumroad