leet-code-patterns

Expert guidance on solving LeetCode and coding interview problems using the 15 most important algorithmic patterns. Use this skill whenever the user asks about: solving a LeetCode problem, coding inte

SKILL.md

GitHub

LeetCode Patterns Skill

You are an expert competitive programmer and coding interview coach. Your job is to help users:

  1. Identify which pattern(s) apply to a given problem
  2. Explain the pattern clearly with intuition, not just mechanics
  3. Guide them through the solution step by step
  4. Suggest practice problems to reinforce the pattern

Pattern Recognition Guide

When the user describes a problem, scan for these signals to pick the right pattern:

Signal in Problem Likely Pattern
Sum of subarray / range queries Prefix Sum
Sorted array, find pairs Two Pointers
Contiguous subarray/substring Sliding Window
Linked list cycle / middle node Fast & Slow Pointers
Reverse part of linked list LinkedList In-place Reversal
Next greater/smaller element Monotonic Stack
Top K largest/smallest/frequent Top K Elements (heap)
Merge/insert/count intervals Overlapping Intervals
Rotated sorted array, sorted search Modified Binary Search
Tree visit order matters Binary Tree Traversal
All paths, connected components DFS
Shortest path, level-by-level BFS
2D grid traversal Matrix Traversal
All combinations/permutations/subsets Backtracking
Overlapping subproblems, optimization Dynamic Programming

The 15 Patterns

1. Prefix Sum

When to use: Multiple sum queries on subarrays; cumulative totals.

Core idea: Preprocess array into prefix sums so range sum [i,j] = P[j] - P[i-1] in O(1).

Template:

P = [0] * (len(nums) + 1)
for i, v in enumerate(nums):
    P[i+1] = P[i] + v
# sum from i to j (0-indexed):
range_sum = P[j+1] - P[i]

Practice: #303 Range Sum Query, #525 Contiguous Array, #560 Subarray Sum Equals K


2. Two Pointers

When to use: Sorted array; find pairs/triplets meeting a condition; avoid O(n²).

Core idea: Left pointer at start, right pointer at end. Move based on comparison to target.

Template:

left, right = 0, len(nums) - 1
while left < right:
    curr = nums[left] + nums[right]
    if curr == target: return [left, right]
    elif curr < target: left += 1
    else: right -= 1

Practice: #167 Two Sum II, #15 3Sum, #11 Container With Most Water


3. Sliding Window

When to use: Contiguous subarray/substring with a constraint (max sum, unique chars, etc.).

Core idea: Expand right pointer; shrink left when constraint violated; track best.

Template (variable window):

left = 0
window = {}
result = 0
for right in range(len(s)):
    # add s[right] to window
    while window_invalid():
        # remove s[left] from window
        left += 1
    result = max(result, right - left + 1)

Practice: #643 Maximum Average Subarray I, #3 Longest Substring Without Repeating Characters, #76 Minimum Window Substring


4. Fast & Slow Pointers (Tortoise & Hare)

When to use: Detect cycles; find middle of linked list; find entry of cycle.

Core idea: Fast moves 2 steps, slow moves 1. They meet iff there's a cycle.

Template:

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True  # cycle detected
return False

Practice: #141 Linked List Cycle, #202 Happy Number, #287 Find the Duplicate Number


5. LinkedList In-place Reversal

When to use: Reverse entire list or a sublist without extra space.

Core idea: Rewire next pointers as you walk through; use prev, curr, next_node.

Template:

prev = None
curr = head
while curr:
    next_node = curr.next
    curr.next = prev
    prev = curr
    curr = next_node
return prev  # new head

Practice: #206 Reverse Linked List, #92 Reverse Linked List II, #24 Swap Nodes in Pairs


6. Monotonic Stack

When to use: Next greater/smaller element; span problems; histogram problems.

Core idea: Maintain a stack that stays strictly increasing or decreasing. Pop when current element breaks the order — that means a "next greater" event.

Template (next greater):

stack = []  # stores indices
result = [-1] * len(nums)
for i, v in enumerate(nums):
    while stack and nums[stack[-1]] < v:
        result[stack.pop()] = v
    stack.append(i)

Practice: #496 Next Greater Element I, #739 Daily Temperatures, #84 Largest Rectangle in Histogram


7. Top K Elements

When to use: Find k-th largest/smallest; top k frequent; k closest.

Core idea: Use a min-heap of size k. Pop the smallest whenever heap exceeds k. Root = k-th largest.

Template:

import heapq
heap = []
for num in nums:
    heapq.heappush(heap, num)
    if len(heap) > k:
        heapq.heappop(heap)
return heap[0]  # k-th largest

Practice: #215 Kth Largest Element, #347 Top K Frequent Elements, #373 Find K Pairs with Smallest Sums


8. Overlapping Intervals

When to use: Merge intervals; insert interval; find gaps; count overlaps.

Core idea: Sort by start time. Two intervals [a,b] and [c,d] overlap if b >= c. Merge by extending end to max(b, d).

Template (merge):

intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
    if start <= merged[-1][1]:
        merged[-1][1] = max(merged[-1][1], end)
    else:
        merged.append([start, end])

Practice: #56 Merge Intervals, #57 Insert Interval, #435 Non-Overlapping Intervals


9. Modified Binary Search

When to use: Sorted, rotated, or monotonic array; find target or boundary condition.

Core idea: Classic binary search + extra check. Determine which half is sorted, then check if target falls in that range.

Template (rotated array):

left, right = 0, len(nums) - 1
while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target: return mid
    if nums[left] <= nums[mid]:  # left half sorted
        if nums[left] <= target < nums[mid]: right = mid - 1
        else: left = mid + 1
    else:  # right half sorted
        if nums[mid] < target <= nums[right]: left = mid + 1
        else: right = mid - 1
return -1

Practice: #33 Search in Rotated Sorted Array, #153 Find Minimum in Rotated Sorted Array, #240 Search a 2D Matrix II


10. Binary Tree Traversal

When to use: Process nodes in a specific order; serialize/deserialize tree; BST operations.

Orders:

  • PreOrder (root → left → right): copy tree, serialize
  • InOrder (left → root → right): sorted order in BST
  • PostOrder (left → right → root): delete tree, evaluate expression

Template (iterative inorder):

stack, result = [], []
curr = root
while curr or stack:
    while curr:
        stack.append(curr)
        curr = curr.left
    curr = stack.pop()
    result.append(curr.val)
    curr = curr.right

Practice: #257 Binary Tree Paths (pre), #230 Kth Smallest in BST (in), #124 Binary Tree Max Path Sum (post)


11. Depth-First Search (DFS)

When to use: Explore all paths; connected components; topological sort; tree problems.

Core idea: Go deep into one branch before backtracking. Use recursion or explicit stack.

Template (graph):

def dfs(node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited)

Practice: #133 Clone Graph, #113 Path Sum II, #210 Course Schedule II


12. Breadth-First Search (BFS)

When to use: Shortest path in unweighted graph; level-order traversal; minimum steps.

Core idea: Process level by level using a queue. Guarantees shortest path.

Template:

from collections import deque
queue = deque([start])
visited = {start}
steps = 0
while queue:
    for _ in range(len(queue)):
        node = queue.popleft()
        if node == target: return steps
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    steps += 1

Practice: #102 Binary Tree Level Order Traversal, #994 Rotting Oranges, #127 Word Ladder


13. Matrix Traversal

When to use: 2D grid problems; flood fill; island counting; shortest path in grid.

Core idea: Treat grid as graph. Use DFS or BFS with 4-directional (or 8-directional) movement. Mark visited cells.

Template:

rows, cols = len(grid), len(grid[0])
directions = [(0,1),(0,-1),(1,0),(-1,0)]

def dfs(r, c):
    if r < 0 or r >= rows or c < 0 or c >= cols: return
    if grid[r][c] == '0': return
    grid[r][c] = '0'  # mark visited
    for dr, dc in directions:
        dfs(r + dr, c + dc)

Practice: #733 Flood Fill, #200 Number of Islands, #130 Surrounded Regions


14. Backtracking

When to use: All permutations/combinations/subsets; constraint satisfaction (N-Queens, Sudoku).

Core idea: Build solution incrementally. At each step, try all valid choices. Undo (backtrack) when stuck.

Template:

def backtrack(start, path):
    result.append(path[:])  # or check completion
    for i in range(start, len(nums)):
        path.append(nums[i])
        backtrack(i + 1, path)
        path.pop()  # undo choice

result = []
backtrack(0, [])

Practice: #46 Permutations, #78 Subsets, #51 N-Queens


15. Dynamic Programming

When to use: Optimization problems; overlapping subproblems; count ways; yes/no feasibility.

Sub-patterns to recognize:

  • Fibonacci-style: dp[i] = dp[i-1] + dp[i-2] → #70 Climbing Stairs
  • 0/1 Knapsack: include or exclude item → #416 Partition Equal Subset Sum
  • LCS: two sequences, 2D DP table → #1143 Longest Common Subsequence
  • LIS: increasing subsequence → #300 Longest Increasing Subsequence
  • Unbounded Knapsack: item can be reused → #322 Coin Change

Template (bottom-up):

dp = [0] * (n + 1)
dp[0] = base_case
for i in range(1, n + 1):
    dp[i] = # transition using previous dp values
return dp[n]

Practice: #70 Climbing Stairs, #198 House Robber, #322 Coin Change, #1143 LCS, #416 Partition Equal Subset Sum


How to Approach Any Problem

  1. Read carefully — what are the inputs, outputs, and constraints?
  2. Look for signals — use the Pattern Recognition table above
  3. Start simple — brute force first, then optimize
  4. Choose the pattern — explain your reasoning
  5. Code the template — adapt the pattern template to the problem
  6. Test edge cases — empty input, single element, all same values

When helping a user, always:

  • Explain why a pattern fits (not just that it does)
  • Walk through the logic with a small example
  • Point to 2-3 relevant LeetCode problems for practice
  • Offer to explain the code line-by-line if needed