Video summary

ТЫ БУДЕШЬ СРАДАТЬ ОТ АЛГОРИТМОВ! (пока не посмотришь это видео)

Main summary

Key takeaways

Educational

Main ideas / lessons

  • Preparation philosophy: Don’t rely on memorizing solutions to individual problems. Instead, learn reusable algorithmic patterns/frameworks and recognize “green flags” (task cues) that indicate which pattern applies.
  • Video structure (overall):
    1. Start from a popular LeetCode topic
    2. Look at interview/statistics emphasis (frequency “green/yellow/red” zones)
    3. Teach the core patterns within the topic
    4. Give example tasks and show how to solve them
    5. Combine knowledge into a single framework for choosing the right pattern quickly
  • Core meta-skill: When you see the problem wording, quickly identify which pattern is relevant (often via task structure like “two pointers”, “fixed window”, “frequency counting”, etc.).

Detailed methodology / instructions by topic

1) Two Pointers (indexing/sides; “fast & slow”)

Pattern A: Two pointers on a sorted array (“two sides”)

Task cues: Sorted array; often “two numbers add up to target.”

Method

  • Initialize:
    • L = start (beginning)
    • R = end (last index)
  • Loop while L < R:
    • Compute sum = nums[L] + nums[R]
    • If sum < target: move L right
    • If sum > target: move R left
    • If sum == target: return positions / answer
  • If no match: return -1 (or equivalent)

Complexities: Time O(n), memory O(1).

Pattern B: Two pointers for palindrome check

Task cues: “Given a word, check if palindrome.”

Method

  • L at left end, R at right end
  • While L < R: compare characters; move inward accordingly
  • If all pairs match → palindrome else not

Core idea: Shrink the window between pointers.

Pattern C: Two pointers for common elements of two sorted arrays (“two arrays, one pointer each”)

Task cues: “Find common elements between two sorted arrays.”

Method

  • Initialize pointers P1, P2 at starts
  • While both are within bounds:
    • If arr1[P1] < arr2[P2]: increment P1
    • If arr1[P1] > arr2[P2]: increment P2
    • If equal:
      • Add to result
      • Increment both

Complexities: Time O(n + m), memory proportional to output.

Pattern D: Fast & Slow pointers (in-place zero/space operations)

Task cues: Modify array/string in-place while maintaining order.

Method

  • Initialize:
    • fast reads through array
    • slow writes next “kept” position
  • Loop while fast in bounds:
    • If element is “allowed” (e.g., non-zero): swap or write to slow, then advance both
    • If element is “discarded” (e.g., zero): advance only fast
  • End: non-discarded elements end up at the front; discards at end.

Example cue logic:

  • slow = write index
  • fast = read index

Complexities: Time O(n), memory O(1).

Final framework for two pointers

  • If two arrays: use “each-pointer” pattern.
  • If in-place modification: use “fast & slow.”
  • Else, prefer “two sides” for sorted/symmetric narrowing.

2) Sliding Window

Pattern A: Fixed-size sliding window

Task cues: “Max/min of k consecutive elements/products/properties.”

Method

  • Compute sum/product for first window of size k
  • Slide:
    • Subtract left element leaving window
    • Add right element entering window
  • Track max (or min)

Transition formula: new = old - left + right

Complexities: Time O(n), memory O(1).

Pattern B: Non-overlapping windows

Task cues: Arrays where segments/ranges are built greedily and do not overlap (often “combine consecutive runs”).

Method

  • Initialize L and R
  • Expand R while condition holds (e.g., strictly increasing by 1)
  • Process the found run into answer
  • Move both to next starting point

Complexities: Time O(n), since pointers only advance.

Pattern C: Intersecting windows

Task cues: You can “keep extending” but must shrink to maintain a constraint (e.g., “max length with at most k flips”).

Method

  • Initialize:
    • L = 0, R = -1
    • Track constraint counter (e.g., zeros in window)
  • Expand R until constraint would be violated
  • Update answer based on valid window
  • Narrow by moving L and updating counter
  • Repeat until L exits array

Key rule: Maintain window validity by updating the constraint state during both expansion and contraction.

Complexities: Time O(n), memory O(1).

Sliding Window identification rules

  • “Fixed length k” → fixed window.
  • “Groups don’t intersect” → non-overlapping.
  • “Need to consider overlapping sequences under a constraint” → intersecting.

3) Hash Table Framework (frequency + key/value inversion)

Pattern A: Counting technique

Task cues: “Check possibility based on frequency” (palindrome anagram, anagram check, etc.)

Method

  • Build dictionary: count[char]++
  • Post-process counts (e.g., palindrome condition: ≤1 odd frequency)
  • Return based on rule

Complexities: Time O(n), memory O(#unique).

Pattern B: KVK (“key-value inversion” / frequency buckets)

Task cues: “Sort by frequency” or “top k frequent elements.”

Method

  • Count frequencies: count[elem]
  • Invert into buckets/array: freqBuckets[freq].push(elem)
  • Traverse buckets from high frequency to low to build result

Complexities: Time roughly linear with bounded overhead; memory O(n).

Hash table decision rule

  • If you need frequency comparisons/calculations → Counting.
  • If you need ordering/sorting by frequency or extracting top-k → KVK.

4) Points & Segments (Intervals)

Pre-knowledge (basic definitions)

  • Segment = pair coordinates.
  • Intersection exists if:
    • max(start1, start2) <= min(end1, end2)
  • Union of intersecting segments:
    • start = min(starts), end = max(ends)
    • (but only after verifying intersection)

Pattern A: Segment method (merge intersecting segments)

Method

  • Sort segments by start
  • Start result with first segment
  • For each next segment:
    • If it intersects the last result segment → merge
    • Else → append as new segment

Complexity: Time O(n log n) due to sorting.

Pattern B: Two pointers on segments (intersections between two lists)

Method

  • Put pointer i at start of list A; j at start of list B
  • While both pointers are in range:
    • If segments intersect → add intersection to result
    • Move pointer with the smaller end forward

Complexities: Time O(n + m).

Pattern C: Dot method (events at points; max simultaneous rooms/platforms)

Task cues: “Max number of simultaneous active intervals.”

Method

  • Transform each interval [start, end] into points/events:
    • (start, +1)
    • (end, -1)
  • Sort points by coordinate; for same coordinate, process -1 before +1 (room becomes free before becomes busy)
  • Sweep with counter; answer = maximum counter value

Complexities: Time dominated by sorting O(n log n).

5) Binary Search

Pattern A: Basic binary search (boundary between good/bad)

Task cues: Sorted array; find last good (or first bad) boundary.

Method

  • Define monotonic “good” predicate:
    • If nums[mid] <= target → good else bad
  • Maintain L and R such that:
    • after loop, L lands on last good
    • R on first bad
  • Final step: verify answer

Complexities: Time O(log n), memory O(1).

Pattern B: Double binary search (find first and last occurrence)

Task cues: Need range [first, last] for target.

Method

  • Run binary search #1 to find boundary for last occurrence
  • Run binary search #2 to find boundary for first occurrence
  • If not found in either → return [-1, -1]

Complexities: Time O(log n) overall (conceptually 2*log n).

Special case mentioned: rotated sorted array

  • Use double binary search to find rotation offset, then binary search within shifted order.

Decision rule

  • Simple boundary → basic.
  • Need a range or require “preparation binary search” → double.

6) Stack (LIFO) and related variants

Pattern A: Stack of intermediate results

Task cues: Nested structure with validation (brackets matching, RPN evaluation).

Method

  • Traverse elements:
    • If opening → push
    • If closing → pop and verify match
  • At end: stack must be empty (for correctness)

Complexities: Time O(n), memory O(n).

Pattern B: Monotonic stack

Task cues: For each element, find nearest greater/smaller element to right/left.

Method (nearest greater to the right example)

  • Traverse from right to left
  • Maintain stack with monotonic property (e.g., decreasing/increasing depending on goal)
  • While stack top violates condition, pop
  • Answer for current is stack top (or -1 if empty)
  • Push current

Complexities: Time O(n) (each element pushed/popped at most once).

Pattern C: Pseudo-stack

Task cues: Brackets correctness where you only need balance magnitude, not actual stack contents.

Method

  • Maintain balance
  • On ‘(’ → balance++
  • On ‘)’ → balance--
  • If balance < 0 → invalid immediately
  • End valid iff balance == 0

Complexities: Time O(n), memory O(1).

Stack framework summary

  • Nearest greater/smaller → monotonic stack.
  • Need only stack size/balance → pseudo-stack.
  • Otherwise nested/remembering types/values → intermediate stack.

7) Prefix Sum

Core idea

  • Prefix array allows O(1) range sum queries: sum(i..j) = prefix[j] - prefix[i-1] (with correct indexing).

  • Useful for many aggregate queries on arrays/matrices.

Pattern A: Array sums (2D aggregation)

Task cues: Aggregate by rows/columns/diagonals in a 2D grid (rook/queen).

Method

  • Precompute sums for each row and each column (and diagonals when needed)
  • For each cell, compute attacked/affected sum using precomputed arrays
  • Track max/min as required

Complexities: Typically O(n*m) time and O(n+m) memory.

Pattern B: Running prefix (replace suffix/prefix arrays with variables)

Task cues: Split point where left sum == right sum, etc.

Method

  • Compute total sum
  • Maintain prefix sum variable while scanning
  • Compute suffix = total - prefix - current
  • Check condition; update prefix as you move

Complexities: Time O(n), memory O(1).

8) Linked Lists

Pattern A: Dummy node (“dummy knot”)

Task cues: When deletion/insert at head would complicate cases; avoid special casing.

Method

  • Create dummy node before head
  • Use pointers to traverse and modify links
  • Return dummy.next (and delete dummy if no GC)

Complexity: Typically O(n) (depends on traversal).

Pattern B: Partial reversals

Task cues: Palindrome on singly linked list when you can’t traverse backward.

Method

  • Find middle (slow/fast)
  • Reverse only the second half
  • Compare first half and reversed second half node-by-node

Complexities: Time O(n), memory O(1).

Also covered basics (not framed as “pattern”)

  • Middle of singly list via slow/fast pointers.
  • In-place reversal with pointer rewiring.
  • Merging two sorted lists using dummy node.

Linked list decision rule

  • If you need to build new list or deletion can touch head → dummy node.
  • If you need two-sided comparison but list is singly → partial reversals.

9) Brute Force vs Backtracking (combinatorics)

Pattern A: Brute force

Task cues: Enumerate all possibilities with limited pruning (or none).

Method (phone keypad combinations example)

  • Maintain a queue/deque of partial strings
  • Pop first partial; if empty or partial length too short:
    • Generate next letter options for next digit
    • Append new partials to the queue
  • Stop when partial length equals input length
  • Collect all completed strings

Complexities: Exponential, e.g. O(4^n) in keypad case.

Pattern B: Backtracking

Task cues: Validity constraints can prune early (e.g., balanced parentheses).

Method (generate correct parentheses)

  • Start with queue/deque holding:
    • counts of open and close brackets used so far
    • current partial string
  • At each step:
    • Add ‘(’ only if openUsed < n
    • Add ‘)’ only if closeUsed < openUsed
  • Stop when length reaches 2n
  • Return all valid sequences

Key distinction: Prune invalid branches before reaching full length.

Complexity: Related to Catalan numbers (exponential but much smaller than full 2^(2n) enumeration).

Decision rule

  • If you can prune invalid branches early → backtracking.
  • If you effectively must try everything → brute force.

10) Trees (Binary trees emphasized): Bottom-up vs Top-down

Pattern A: Bottom-up

Meaning: Collect info from children to compute parent.

Method template

  • Base case: empty node → return neutral value (e.g., 0 height)
  • Recurse left/right
  • Combine children results to form answer info
  • Return value required by parent (often “height” even when answer uses “diameter”)

Example: Diameter of binary tree

  • Update global maximum using leftHeight + rightHeight
  • Return height up the recursion

Complexities: Time O(n), memory O(h) recursion depth.

Pattern B: Top-down

Meaning: Pass accumulated state from root to children.

Method template

  • Base: empty node
  • Recurse into children with updated parameter (sumSoFar, level, path constraints)
  • Use recursion results to build answer (often boolean)

Example: Path sum root-to-leaf

  • Pass sumToHere down
  • At leaf, compare to target

Complexities: Time O(n), memory O(h).

Tree framework rule

  • Need “from leaves upward aggregation” → bottom-up.
  • Need “carry information from root to children” → top-down.

11) Graphs: BFS/DFS + components + topological order

Graph basics

  • Graph stored typically via adjacency list (hash map vertex → neighbor list).
  • Connected component: maximal group of mutually reachable nodes (for undirected graphs).

Pattern A: BFS traversal (wave)

Task cues: Shortest path in unweighted graphs; distance in steps.

Method

  • Initialize queue with start node; mark visited; store distance for start = 0
  • While queue not empty:
    • Pop front node
    • For each neighbor:
      • If not visited: mark visited, set neighbor distance = current + 1, push
    • If finish found: return distance
  • If never found: return -1

Complexities: Time O(n + m), memory O(n).

Pattern B: DFS traversal

Task cues: Reachability; exploring depth branches; cycle detection variants (not expanded here).

Method

  • Use stack (LIFO) + visited
  • Pop node, push unvisited valid neighbors

Complexities: Time O(n + m), memory O(n).

Rule of thumb

  • “Minimum/shortest distance” → BFS.
  • “In other cases” either can work, but BFS is practical for shortest paths.

Pattern C: Connected components

Method

  • Build graph (adjacency list)
  • Iterate over all vertices
  • For each unvisited vertex: run BFS/DFS to mark its component; increment component count

Complexities: O(n + m).

Pattern D: Topological order / dependency order (Kahn’s algorithm)

Task cues: DAG ordering; “task prerequisites” ordering.

Method

  • Compute indegree for each vertex
  • Push all indegree==0 vertices into queue
  • While queue not empty:
    • Pop node; add to answer list
    • For each outgoing edge to neighbor:
      • decrement neighbor indegree
      • if neighbor indegree becomes 0: push it
  • If answer size == number of vertices → valid order; else → cycle exists → return empty list

Complexities: O(n + m).

Rule

  • Need shortest path steps → shortest-path (BFS).

Original video