20 PATTERN Architecture

D

Qubits of DPK

April 11, 2026

Core DSA

PATTERN 1: Simple Traversal & Accumulation

Signal: “Scan and compute something”

Concepts

  • Arrays (1D, 2D)
  • Matrix traversal
  • Basic accumulation logic
  • Simple counters
  • Basic linked list traversal

Problems Look Like

  • Find max/min/sum
  • Count elements
  • Spiral / zigzag traversal
  • Maintain running state
30 problems here = muscle memory
No tricks. Just clean thinking.

PATTERN 2: Hashing as State Memory

Signal: “Have I seen this before?”

Concepts

  • HashMap / HashSet
  • Frequency counting
  • Prefix + Hash
  • Visited state tracking
  • Cycle detection

Problems Look Like

  • Two sum
  • Longest subarray with sum K
  • Duplicate detection
  • Anagram grouping
Key thought:
“What state am I revisiting?”

PATTERN 3: Prefix / Suffix / Precomputation

Signal: “Repeated range queries”

Concepts

  • Prefix sums
  • Suffix arrays
  • Prefix + Hash
  • Kadane’s Algorithm
  • Range queries

Problems Look Like

  • Subarray sums
  • Zero sum subarray
  • Rainwater (prefix version)
  • Equilibrium index
Key realization:
“Can I precompute once and reuse?”

PATTERN 4: Two Pointers & Sliding Window

Signal: “Contiguous / sorted / window constraint”

Concepts

  • Two pointers
  • Fixed window
  • Variable window
  • Fast–slow pointers

Problems Look Like

  • Pair sum
  • 3Sum
  • Longest substring without repeat
  • Container with most water
After 30 problems:
You instantly smell window problems.

PATTERN 5: Linked List Thinking (Pointer Control)

Signal: “You don’t have indices.”

Concepts

  • Slow–fast pointer
  • Dummy node technique
  • Pointer rewiring
  • Cycle detection
  • Reverse logic

Problems Look Like

  • Reverse linked list
  • Remove Nth node
  • Reorder list
  • Merge k lists
  • LRU cache
Golden rule:
“Where does this pointer point after operation?”

PATTERN 6: Sorting & Ordering Logic

Signal: “Order simplifies logic”

Concepts

  • Comparator sorting
  • Merge sort
  • Interval sorting
  • Greedy setup via sorting

Problems Look Like

  • Merge intervals
  • Activity selection
  • Minimum platforms
  • Largest number formation
Habit:
“What if I sort first?”

PATTERN 7: Binary Search (Index + Answer)

Signal: “Monotonic yes/no space”

Concepts

  • Classic binary search
  • First/last occurrence
  • Binary search on answer
  • Feasibility function

Problems Look Like

  • Aggressive cows
  • Painter partition
  • Capacity problems
  • Rotated array search
Key line:
“Answer space is monotonic.”

PATTERN 8: Monotonic Stack

Signal: “Nearest greater/smaller”

Concepts

  • Increasing stack
  • Decreasing stack
  • Histogram logic
  • Contribution boundaries

Problems Look Like

  • Next greater element
  • Largest rectangle
  • Stock span
  • Rainwater (stack)
Once clicked → permanent pattern.

PATTERN 9: Greedy Algorithms

Signal: “Local optimal may be global optimal”

Concepts

  • Activity selection
  • Scheduling
  • Interval merging
  • Exchange argument

Problems Look Like

  • Job scheduling
  • Huffman encoding
  • Jump game
  • Gas station
Always ask:
“Why is this choice safe?”

PATTERN 10: Recursion & Backtracking

Signal: “Try → Undo → Try next”

Concepts

  • Recursion tree
  • Decision branching
  • Backtracking template
  • Pruning

Problems Look Like

  • Subsets
  • Permutations
  • N-Queens
  • Sudoku
  • Rat in maze
Write choices in English first.

PATTERN 11: Tree Recursion (Binary Tree + BST)

Signal: “Solve left + solve right + combine”

Concepts

  • DFS recursion
  • Height/depth logic
  • LCA
  • BST properties

Problems Look Like

  • Diameter
  • Balanced tree
  • Max path sum
  • Validate BST
Key question:
“What does my recursive function return?”

PATTERN 12: Heap / Priority Queue Thinking

Signal: “Need best element repeatedly”

Concepts

  • Min heap / Max heap
  • Top K
  • Streaming median
  • Scheduling with heap

Problems Look Like

  • Kth largest
  • Merge K lists
  • Task scheduler
  • IPO problem
Sorting once ≠ dynamic best selection.

PATTERN 13: Dynamic Programming

Signal: “Overlapping subproblems”

Sub-Patterns

  • 1D DP
  • 2D DP
  • Knapsack
  • LIS / LCS
  • Grid DP

Problems Look Like

  • House robber
  • Coin change
  • Partition problems
  • Edit distance
Rule:
If recursion repeats → DP candidate.

PATTERN 14A: Graph Traversal & Properties

Signal: “Nodes + edges + reachability”

Concepts

  • BFS / DFS
  • Cycle detection
  • Topological sort
  • MST
  • Dijkstra

Problems Look Like

  • Course schedule
  • Connected components
  • Shortest path
  • Bridges
Graph modeling clarity begins here.

PATTERN 14B: Multi-Source BFS

Signal: “Minimum steps / spreading”

Concepts

  • Level expansion
  • Distance matrix
  • Multiple starting nodes

Problems Look Like

  • Rotting oranges
  • 01 matrix
  • Shortest path grid
  • Nearest exit
One level = one unit time.

PATTERN 15: Union–Find (Connectivity Thinking)

Signal: “Dynamic grouping”

Concepts

  • DSU
  • Path compression
  • Union by rank
  • Component tracking

Problems Look Like

  • Accounts merge
  • Redundant connection
  • Number of islands II
  • MST (Kruskal)
Key idea:
“What does one set represent?”

PATTERN 16: Trie / Prefix Tree Thinking

Signal: “Shared prefixes”

Concepts

  • Trie insert/search
  • Prefix pruning
  • Bitwise trie

Problems Look Like

  • Word search II
  • Autocomplete
  • Maximum XOR
  • Replace words
Ask:
“What repeated prefix work am I avoiding?”

PATTERN 17: Contribution Technique

Signal: “Sum over all subarrays”

Concepts

  • Boundary counting
  • Monotonic stack integration
  • Mathematical contribution
  • Last-seen index logic

Problems Look Like

  • Sum of subarray minimums
  • Total strength
  • Subarray ranges
  • Total appeal
Golden thought:
“How many subarrays include index i?”

PATTERN 18: Bit Manipulation

Signal: “Encode state in bits”

Concepts

  • XOR cancellation
  • Bitmask
  • Mask DP
  • State compression

Problems Look Like

  • Single number
  • Subsets (bitmask)
  • TSP (mask DP)
  • Parallel courses II
Always define:
“What does this bit represent?”

PATTERN 19: State Machine / Greedy Transitions

Signal: “Small number of states”

Concepts

  • Hold/sell states
  • Cooldown transitions
  • Transaction modeling
  • Compressed DP

Problems Look Like

  • Stock with cooldown
  • Stock with K transactions
  • Maximum alternating sum
  • Sequence validity problems
Key question:
“What are my states?”

PATTERN 20: Interval / Partition DP

Signal: “Choose the split”

Concepts

  • dp[l][r]
  • Split loop
  • Game DP
  • Merge cost DP

Problems Look Like

  • Matrix chain multiplication
  • Burst balloons
  • Palindrome partitioning II
  • Merge stones
Ask:
“Where do I split this interval?”

How to Apply the 30-Problem Rule (Non-Negotiable)

For each pattern:

First 10 (Easy)

  • Full self-solve
  • English explanation
  • Clean code

Next 10 (Medium)

  • English → Code → Dry run
  • Focus on pattern recognition

Last 10 (Hard)

  • Sit with discomfort
  • Derive logic slowly
  • No solution peeking