Introduction

I always find patterns fascinating and just come out of write Grpc in Go, C#, Typescript, Rust and Java. So using approaches is a common thing for me. Filled this intro up so will press on.

A Picture Says A Thousands Words

Prefix Sum

Purpose

This is used to calculate the sum of an array between two ranges. E.g. you have the rating of a movie in an array from 0-6 and you want to figure out how did it do between day 2 and day 5. The idea is you hold the sum of each index in an array. So and array 1,2,3,4 you would calculate 1, 3, 6, 10. That way if you want 1-2 it would be p[2] - p[0] = 6-1 = 5

Concept

Given an input array `A` of length `n`, the prefix sum array `P` is defined as:

`P[0] = A[0]`
`P[i] = P[i-1] + A[i]` for `i > 0`

This allows fast computation of the sum of any subarray `A[l..r]` using:

`sum = P[r] - P[l-1]` (with edge case handling for `l = 0`)

Implementation (JavaScript)

function prefixSum(arr) {
  const result = [];
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
    result.push(sum);
  }
  return result;
}

Example

Input:

const A = [3, 1, 4, 1, 5];
const P = prefixSum(A); // [3, 4, 8, 9, 14]

To compute sum of A[1..3] (i.e., 1 + 4 + 1):

`P[3] - P[0] = 9 - 3 = 6`

Adding 0

In some cases people add a 0 to the beginning of the array

Simplifies range sum queries: no need for special-case handling when `l = 0`
Aligns `P[i]` with the sum of the first `i` elements of `A`
Avoids off-by-one errors in indexing
Makes the prefix sum array length `n + 1`, which is often more ergonomic in 1-based indexing contexts

This allows fast computation of the sum of any subarray `A[l..r]` using:

`sum = P[r+1] - P[l]`

Use Cases

Fast range sum queries
Histogram equalization
Cumulative frequency tables
Sliding window optimizations

Notes

Can be extended to 2D arrays for matrix prefix sums
Useful in competitive programming and data preprocessing

Two Pointer Pattern

Purpose

Optimize traversal of arrays or linked lists by using two indices (pointers) to reduce time complexity, often from O(n²) to O(n). The real life example was you’re processing a sorted audit log of user login timestamps. You want to detect if any user has logged in twice within a 5-minute window. Spent a bit of time understanding the O(n²) thing. As the formula for doing the search manually was - n × (n - 1) / 2. The -1 and /2 are ignored to make n². This would be better written for me a n x 0.5(n-1). It is far more easy to see that the 0.5 will influence the outcome but we are still dealing with a parabola (quadratic)

Concept

Use two pointers to scan or compare elements in a sequence:

Left and Right: Often used for searching or shrinking a window.
Fast and Slow: Used for cycle detection or distance-based logic.

Typical setup:

Initialize two pointers (`i`, `j`) at different positions.
Move one or both based on problem constraints.
Avoid nested loops by leveraging sorted input or monotonic properties.

Common Use Cases

Finding pairs with a target sum in a sorted array
Removing duplicates in-place
Merging sorted arrays
Sliding window optimizations
Cycle detection in linked lists (Floyd’s algorithm)

Example: Pair Sum in Sorted Array

This example is where you are looking for a value say 5 in a sorted array e.g. 0,1,3,5,11,12.

function hasPairWithSum(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return true;
    if (sum < target) left++;
    else right--;
  }

  return false;
}

Implementation (Rust)

Just for a laugh

fn has_pair_with_sum(sorted: &[i32], target: i32) -> bool {
    let (mut left, mut right) = (0, sorted.len() - 1);

    while left < right {
        let sum = sorted[left] + sorted[right];
        if sum == target {
            return true;
        } else if sum < target {
            left += 1;
        } else {
            right -= 1;
        }
    }

    false
}

fn main() {
    let nums = vec![1, 2, 4, 7, 11, 15];
    let target = 15;

    if has_pair_with_sum(&nums, target) {
        println!("Found a pair that sums to {}", target);
    } else {
        println!("No pair found");
    }
}

Why It Works

Sorted input allows directional decisions (increase left or decrease right).
Avoids brute-force O(n²) pair checking.
Efficient for problems with monotonic constraints.

Variants

Pattern	Use Case	Movement Logic
Left–Right	Sorted array pair sum	Move inward based on sum
Fast–Slow	Cycle detection	Fast moves 2x, slow moves 1x
Sliding Window	Max sum subarray	Expand/shrink window based on condition

Speed Comparison

This table compares the brute-force and two-pointer approaches for finding a pair of numbers that sum to a target in a sorted array.

Method	Description	Time Complexity	Checks for n = 5	Checks for n = 100	Checks for n = 1,000
Brute-force	Try every possible pair using nested loops	O(n²)	10	4,950	499,500
Two-pointer	Start at both ends, move inward based on sum comparison	O(n)	≤ 4	≤ 99	≤ 999

Notes

Often paired with prefix sums or hash maps for hybrid strategies
Works best when input is sorted or has predictable structure

Sliding Window Pattern

Purpose

Efficiently process contiguous subarrays or substrings by maintaining a moving window of elements. Reduces time complexity from O(n²) to O(n) in many cases. Gosh the robot does put it in bizarre words for me. This is when you are asked the highest value sub array e.g. given an array 5,2,4,3,-1,9,3,7,6. What is the maximum value for 4 elements. To reduce the traversal of the array for each window we remove the element on the left leaving the window and add the element on the right entering the window.

Concept

Use two pointers (`start`, `end`) to define a window over a sequence:

Expand the window by moving `end` forward.
Shrink the window by moving `start` forward when constraints are violated.
Track metrics (sum, length, frequency) within the window.

Common Use Cases

Maximum sum of k-length subarray
Longest substring without repeating characters
Minimum window that satisfies a condition
Real-time stream processing (e.g., rolling averages)

Example: Max Sum of Subarray of Size k

fn max_sum_subarray(arr: &[i32], k: usize) -> i32 {
    if arr.len() < k { return 0; }

    let mut max_sum = 0;
    let mut window_sum = arr[..k].iter().sum();

    max_sum = window_sum;

    for i in k..arr.len() {
        window_sum += arr[i] - arr[i - k];
        max_sum = max_sum.max(window_sum);
    }

    max_sum
}

Why It Works

Avoids recomputing sums from scratch
Maintains a fixed-size or dynamic window
Efficient for problems involving contiguous elements

Variants

Variant	Use Case	Window Behavior
Fixed-size	Max sum of k-length subarray	Window slides forward by 1
Dynamic-size	Longest substring without repeats	Expand/shrink based on condition
Frequency-based	Minimum window with all chars	Track counts in a hashmap

Notes

Often combined with hash maps or frequency counters
Works best on arrays, strings, or streams
Can be extended to 2D grids or time-based windows

Related Patterns

Prefix Sum: for cumulative metrics
Two Pointer: for sorted arrays or pair comparisons
Monotonic Queue: for sliding window max/min with order constraints

Fast and Slow Pointer Pattern

Purpose

Efficiently traverse sequences (arrays, linked lists, streams) using two pointers moving at different speeds. Commonly used for:

Cycle detection
Finding the middle of a list
Detecting duplicates or convergence
Space-efficient traversal

The important bit for me was the word cycle. It means when a node points to back to another node. This appears to be a common thing to detect.

Concept

Use two pointers:

`slow` moves one step at a time
`fast` moves two steps at a time

General Algorithm

1. Initialize slow = 0, fast = 0
2. While fast and fast.next exist:
   a. slow = slow.next
   b. fast = fast.next.next
3. If slow == fast → cycle detected

Example: Cycle Detection in Linked List

As mentions above, this is detecting when one node, points to a previous.

fn has_cycle(head: &Option<Box<ListNode>>) -> bool {
    let mut slow = head.as_ref();
    let mut fast = head.as_ref();

    while let (Some(s), Some(f)) = (slow, fast.and_then(|f| f.next.as_ref())) {
        slow = s.next.as_ref();
        fast = f.next.as_ref();
        if std::ptr::eq(slow, fast) {
            return true;
        }
    }

    false
}

Example: Finding Middle of Linked List

The example which made the most sense was a LRU (Least Recently Used) cache. You look for the middle to dump the oldest.

ListNode findMiddle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow; // Middle node
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Cycle detection	O(n)	O(1)
Find middle	O(n)	O(1)
Detect convergence	O(n)	O(1)

Related Patterns

Sliding Window: for subarray/substring processing
Two Pointer: for sorted arrays and pair comparisons
Floyd’s Tortoise and Hare: formal name for cycle detection variant

Notes

Works best on linked lists or sequences with implicit structure
Avoids extra memory allocation
Can be extended to detect loop entry point

In-Place Reversal Pattern

Purpose

Reverse the order of elements in a sequence (array, string, linked list) without using extra space. This pattern is used for:

Memory-efficient transformations
Buffer cleanup or reordering
Palindrome checks
Undo operations

Couldn't really find an example except for reversing byte buffer.

Concept

Use two pointers to swap elements from both ends toward the center:

`left = 0`, `right = n - 1`
While `left < right`, swap `A[left]` and `A[right]`, then move inward

General Algorithm

1. Initialize left = 0, right = n - 1
2. While left < right:
   a. Swap A[left] and A[right]
   b. Increment left, decrement right

Example: Reverse Array In-Place

fn reverse_in_place(arr: &mut [i32]) {
    let mut left = 0;
    let mut right = arr.len().saturating_sub(1);

    while left < right {
        arr.swap(left, right);
        left += 1;
        right -= 1;
    }
}

Example: Reverse String In-Place (Rust)

fn reverse_string(s: &mut Vec<char>) {
    let mut left = 0;
    let mut right = s.len().saturating_sub(1);

    while left < right {
        s.swap(left, right);
        left += 1;
        right -= 1;
    }
}

Example: Reverse String In-Place (C#)

public static void ReverseInPlace(byte[] buffer)
{
    int left = 0;
    int right = buffer.Length - 1;

    while (left < right)
    {
        byte temp = buffer[left];
        buffer[left] = buffer[right];
        buffer[right] = temp;

        left++;
        right--;
    }
}

byte[] payload = new byte[] { 1, 2, 3, 4, 5 };
ReverseInPlace(payload);
// payload is now { 5, 4, 3, 2, 1 }

Example: Carousel

Finally a use case I can understand. A carousel is a blog of posts maybe and you want them in descending order.

// components/InPlaceCarousel.tsx
import React from "react";

interface CarouselProps {
  items: string[];
  reversed?: boolean;
}

function reverseInPlace<T>(arr: T[]): void {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
}

export const InPlaceCarousel: React.FC<CarouselProps> = ({ items, reversed = false }) => {
  const displayItems = [...items]; // clone to avoid mutating props

  if (reversed) {
    reverseInPlace(displayItems); // mutate the clone
  }

  return (
    <div className="flex overflow-x-auto space-x-4 p-4">
      {displayItems.map((item, index) => (
        <div
          key={index}
          className="min-w-[200px] h-[120px] bg-gray-100 rounded-md flex items-center justify-center shadow-md"
        >
          {item}
        </div>
      ))}
    </div>
  );
};

And usage

// pages/index.tsx
import { InPlaceCarousel } from "@/components/InPlaceCarousel";

export default function Home() {
  const items = ["Alpha", "Beta", "Gamma", "Delta"];

  return (
    <main className="p-8">
      <h2 className="text-xl font-bold mb-4">Normal Order</h2>
      <InPlaceCarousel items={items} />

      <h2 className="text-xl font-bold mt-8 mb-4">Reversed In-Place</h2>
      <InPlaceCarousel items={items} reversed />
    </main>
  );
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Array reversal	O(n)	O(1)
String reversal	O(n)	O(1)
Linked list reversal	O(n)	O(1)

Use Cases

Reversing buffers or byte streams
Palindrome validation
Undoing transformations
Reversing singly linked lists (with pointer rewiring)
UI animations (e.g., reversing carousel order)

Related Patterns

Two Pointer Pattern: used to drive the reversal
Fast and Slow Pointer: for midpoint detection before reversal
Stack-based reversal: alternative using extra space

Notes

Works best on mutable sequences
For linked lists, requires pointer rewiring instead of index swapping
Can be extended to reverse subarrays or segments

Monotonic Stack Pattern

Purpose

Maintain a stack that is either strictly increasing or decreasing to efficiently solve problems involving:

Next Greater Element (NGE)
Next Smaller Element (NSE)
Span problems (e.g., stock span)
Histogram area calculations

This was a bit tricky for me. The goal is to not do a calculation for everything in the array. So is we had a height of a histogram held in an array e.g. [2, 1, 5, 6, 2, 3, 0]. Every time you pop an element, you calculate the area for the element popped. For brute force this may be ~36 calculations with monotonic ~18

Step	Index (i)	Height h[i]	Stack Before	Action	Area Computed	Stack After
0	0	2	[]	Push 0	—	[0]
1	1	1	[0]	Pop 0 (height=2, width=1)	2 × 1 = 2	[]
			[]	Push 1	—	[1]
2	2	5	[1]	Push 2	—	[1, 2]
3	3	6	[1, 2]	Push 3	—	[1, 2, 3]
4	4	2	[1, 2, 3]	Pop 3 (height=6, width=1)	6 × 1 = 6	[1, 2]
			[1, 2]	Pop 2 (height=5, width=2)	5 × 2 = 10	[1]
			[1]	Push 4	—	[1, 4]
5	5	3	[1, 4]	Push 5	—	[1, 4, 5]
6	6	0	[1, 4, 5]	Pop 5 (height=3, width=1)	3 × 1 = 3	[1, 4]
			[1, 4]	Pop 4 (height=2, width=4)	2 × 4 = 8	[1]
			[1]	Pop 1 (height=1, width=6)	1 × 6 = 6	[]
			[]	Push 6	—	[6]

Concept

Use a stack to track indices or values while enforcing a monotonic order:

**Increasing stack**: top is smallest, used for next smaller elements
**Decreasing stack**: top is largest, used for next greater elements

General Algorithm

1. Initialize empty stack
2. Iterate over array:
   a. While stack is not empty and current violates monotonicity:
      - Pop from stack
   b. Push current index/value onto stack

Example: Next Greater Element

public int[] NextGreaterElements(int[] nums) {
    int n = nums.Length;
    int[] result = new int[n];
    Stack<int> stack = new();

    for (int i = n - 1; i >= 0; i--) {
        while (stack.Count > 0 && stack.Peek() <= nums[i]) {
            stack.Pop();
        }

        result[i] = stack.Count == 0 ? -1 : stack.Peek();
        stack.Push(nums[i]);
    }

    return result;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Next Greater/Smaller Element	O(n)	O(n)
Histogram Area	O(n)	O(n)

Use Cases

Finding next greater/smaller elements
Calculating largest rectangle in histogram
Stock span problems
Sliding window optimizations
Rainwater trapping (with two-pointer variant)

Related Patterns

Two Pointer Pattern: often used alongside for bidirectional sweeps
In-Place Reversal: used in post-processing results
Prefix Sum: complements monotonic stack in histogram or span problems

Notes

Stack stores indices for flexibility
Can be adapted for circular arrays (modulo indexing)
Useful in both frontend (layout calculations) and backend (data stream analysis)

Top K Elements

Purpose

Efficiently retrieve the k largest elements from a dataset, typically for ranking, filtering, or prioritization. This is foundational in analytics, search, and real-time systems. This does seem to be something I might want to do. Many of these I have not really come across in 40 years of doing this. I do not work, in general, in analysis or graphics. So here goes.

Concept

Maintain a dynamic structure (usually a min-heap of size k) that tracks the top k values as the array is processed. This avoids sorting the entire array and reduces time complexity when k ≪ n.

Common Use Cases

Ranking top scores or metrics
Search engines: top relevant results
Real-time dashboards: top trending items
Log analysis: top error types or sources

Example (Typescript)

To find the to K Elements you can put the elements in a MinHeap. There are two types of these Min and Max.

To find the largest we use the minHeap and for the smallest the maxHeap (not shown)

class MinHeap {
  private heap: number[] = [];

  size(): number {
    return this.heap.length;
  }

  peek(): number | undefined {
    return this.heap[0];
  }

  push(val: number): void {
    this.heap.push(val);
    this.bubbleUp();
  }

  pop(): number | undefined {
    if (this.heap.length === 0) return undefined;
    const top = this.heap[0];
    const end = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.bubbleDown();
    }
    return top;
  }

  private bubbleUp(): void {
    let idx = this.heap.length - 1;
    const element = this.heap[idx];
    while (idx > 0) {
      const parentIdx = Math.floor((idx - 1) / 2);
      const parent = this.heap[parentIdx];
      if (element >= parent) break;
      this.heap[idx] = parent;
      this.heap[parentIdx] = element;
      idx = parentIdx;
    }
  }

  private bubbleDown(): void {
    let idx = 0;
    const length = this.heap.length;
    const element = this.heap[0];
    while (true) {
      let leftIdx = 2 * idx + 1;
      let rightIdx = 2 * idx + 2;
      let swapIdx: number | null = null;

      if (leftIdx < length) {
        if (this.heap[leftIdx] < element) swapIdx = leftIdx;
      }

      if (rightIdx < length) {
        if (
          (swapIdx === null && this.heap[rightIdx] < element) ||
          (swapIdx !== null && this.heap[rightIdx] < this.heap[leftIdx])
        ) {
          swapIdx = rightIdx;
        }
      }

      if (swapIdx === null) break;
      this.heap[idx] = this.heap[swapIdx];
      this.heap[swapIdx] = element;
      idx = swapIdx;
    }
  }

  toSortedArray(): number[] {
    const copy = [...this.heap];
    const result: number[] = [];
    while (this.size() > 0) {
      result.push(this.pop()!);
    }
    this.heap = copy;
    return result.reverse(); // largest to smallest
  }
}

function topKElements(nums: number[], k: number): number[] {
  const heap = new MinHeap();

  for (const num of nums) {
    if (heap.size() < k) {
      heap.push(num);
    } else if (num > heap.peek()!) {
      heap.pop();
      heap.push(num);
    }
  }

  return heap.toSortedArray();
}

// Example usage:
const nums = [3, 1, 5, 12, 2, 11];
const k = 3;
console.log(topKElements(nums, k)); // Output: [12, 11, 5]

Why It Works

Using a min-heap of size k ensures:

The smallest of the top k is always at the root
Any new value greater than the root replaces it
Heap maintains top k values in O(n log k) time

This avoids full sorting (O(n log n)) and is optimal when k is much smaller than n.

Variants

Top K Frequent Elements (by frequency)
Top K in Streaming Data (online updates)
Top K with Ties (handle duplicates)
Top K by Custom Comparator (e.g., score + timestamp)

Notes

Use max-heap if you need smallest k elements
Quickselect is faster for unsorted arrays when order doesn’t matter
Sorting is simplest but less efficient for large n
Heap-based approach is ideal for real-time or memory-constrained systems

Overlapping Intervals

Purpose

Detect and merge overlapping intervals in a list of ranges. This pattern is used to:

Consolidate time blocks or resource allocations
Detect conflicts in scheduling or bookings
Normalize ranges for efficient querying

Concept

Sort intervals by start time, then iterate and merge overlapping ones:

If current interval overlaps with the previous → merge
Else → add as a new block

Common Use Cases

Calendar event conflict resolution
CPU or memory range merging
Booking system availability
Firewall rule normalization
Genomic range analysis

Example: Merge Overlapping Intervals (TypeScript)

type Interval = [number, number];

function mergeIntervals(intervals: Interval[]): Interval[] {
  if (intervals.length === 0) return [];

  // Sort by start time
  intervals.sort((a, b) => a[0] - b[0]);

  const merged: Interval[] = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const [prevStart, prevEnd] = merged[merged.length - 1];
    const [currStart, currEnd] = intervals[i];

    if (currStart <= prevEnd) {
      // Overlap → merge
      merged[merged.length - 1][1] = Math.max(prevEnd, currEnd);
    } else {
      // No overlap → add new
      merged.push([currStart, currEnd]);
    }
  }

  return merged;
}

// Example usage:
const input: Interval[] = [[1, 3], [2, 6], [8, 10], [9, 12]];
console.log(mergeIntervals(input)); // Output: [[1, 6], [8, 12]]

Why It Works

Sorting ensures intervals are processed in order
Overlap is detected by comparing current start with previous end
Merging is done in-place, preserving minimal space usage
Guarantees non-overlapping output in O(n log n) time

Variants

Insert and merge a new interval into existing list
Count total coverage (union of intervals)
Detect conflicts without merging
Interval intersection (e.g., common availability)

Notes

Sorting is key — without it, merging fails
Can be adapted to handle open/closed intervals
Useful in both frontend (calendar UI) and backend (range indexing)
For large datasets, consider segment trees or interval trees

Binary Search

Purpose

Efficiently locate a target value or decision point in a sorted array or monotonic search space. Reduces time complexity from O(n) to O(log n). Basically you start from the middle and test if the target value is < or > and discard search the other side thus saving time. Rinse and repeat.

Concept

Repeatedly divide the search space in half:

Compare target with middle element
Narrow search to left or right half based on comparison
Stop when target is found or search space is empty

Common Use Cases

Search for a target in sorted array
Find first or last occurrence of a value
Locate insertion point (lower/upper bound)
Binary search on answer (e.g., min/max feasible value)
Peak finding in unimodal arrays

Example: Basic Binary Search (TypeScript)

function binarySearch(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1; // not found
}

Why It Works

Sorted input guarantees predictable direction
Halving search space each step → O(log n) time
Works on arrays, ranges, or virtual search spaces

Variants

Lower bound: first index ≥ target
Upper bound: first index > target
First/last occurrence with duplicates
Binary search on answer (e.g., capacity, radius, speed)
Search in rotated or infinite arrays (see Modified Binary Search)

Notes

Always validate sorted input before applying
Watch for overflow in `mid = (left + right) / 2` → use `left + (right - left) / 2`
Can be adapted to floats, ranges, or custom comparators
Foundation for many optimization and decision problems

Modified Binary Search

Purpose

Adapt binary search to solve problems where the array is:

Rotated or partially sorted
Contains duplicates or gaps
Requires condition-based search (not exact match)

Used to locate elements, boundaries, or decision points in O(log n) time. For example given

Rotated Arrays

A rotated array is a sorted array that’s been shifted circularly

[1, 2, 3, 4, 5, 6]

After rotating right by 2 positions:

[5, 6, 1, 2, 3, 4]

After rotating left by 2 positions:

[3, 4, 5, 6, 1, 2]

Concept

Standard binary search assumes a fully sorted array. Modified variants:

Adjust mid-point logic based on structure
Use conditions to guide search direction
Often return boundaries (first/last occurrence, peak, etc.)

Common Use Cases

Search in rotated sorted array
Find peak element in mountain array
Locate first/last occurrence of target
Binary search on answer (e.g., min/max feasible value)
Search in infinite or unknown-sized array

Example: Search in Rotated Sorted Array (TypeScript)

function searchRotated(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) return mid;

    // Left half is sorted
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    // Right half is sorted
    else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

Why It Works

Rotated arrays have one sorted half → use that to guide search
Mid-point comparison reveals which half is sorted
Conditions narrow search space while preserving O(log n) time

Variants

Find minimum in rotated array
Binary search on answer (e.g., capacity, speed, radius)
Peak finding in unimodal arrays
First/last occurrence with duplicates
Search in infinite array using exponential bounds

Notes

Always validate which half is sorted before deciding direction
Watch for edge cases with duplicates (may degrade to O(n))
Binary search on answer is powerful for optimization problems
Useful in both algorithmic interviews and backend range queries

Tree Traversal

Traversal Types

There a four of types of key traversal.

Traversal	Order	Data Structure	Analogy	Common Use Cases
Pre-order	Node → Left → Right	Stack (recursion or explicit)	Packing a suitcase: handle current item before sub-items	Serialize tree, prefix expression
In-order	Left → Node → Right	Stack (recursion or explicit)	Reading a book: left page, center binding, right page	BST: sorted order, expression evaluation
Post-order	Left → Right → Node	Stack (recursion or explicit)	Cleaning a room: tidy sub-areas before marking complete	Delete tree, postfix expression
Level-order (BFS)	Top-down, left to right	Queue	Breadth-first: process all nodes at current depth	Shortest path, friend-of-friend expansion

Pre-order

In-order

Depth-First Search (DFS)

Purpose

Explore as deep as possible along each branch before backtracking. DFS is ideal for problems involving exhaustive search, pathfinding with constraints, or recursive structure traversal.

More Visual

For DFS we search done rather than across

A clear picture of searching would be

Concept

Use a stack (explicit or via recursion) to dive deep into each path:

Start from a source node
Explore one neighbor fully before moving to the next
Backtrack when no unvisited neighbors remain

Common Use Cases

Pathfinding with constraints (e.g., all paths, cycle detection)
Topological sorting
Solving puzzles (e.g., Sudoku, N-Queens)
Tree traversals (preorder, inorder, postorder)
Backtracking problems (e.g., permutations, combinations)

Example: Cycle Detection in Directed Graph (TypeScript)

function hasCycle(graph: Map<number, number[]>): boolean {
  const visited = new Set<number>();
  const recStack = new Set<number>();

  function dfs(node: number): boolean {
    if (recStack.has(node)) return true;
    if (visited.has(node)) return false;

    visited.add(node);
    recStack.add(node);

    for (const neighbor of graph.get(node) || []) {
      if (dfs(neighbor)) return true;
    }

    recStack.delete(node);
    return false;
  }

  for (const node of graph.keys()) {
    if (dfs(node)) return true;
  }

  return false;
}

Why It Works

Recursion or stack ensures deep traversal
Backtracking allows full path exploration
Recursion stack can track path state (e.g., for cycle detection)
Efficient for problems with branching decisions

Variants

Recursive DFS (natural for trees)
Iterative DFS using a stack
Post-order DFS for dependency resolution
DFS with state tracking (e.g., visited + path constraints)

Notes

Use a stack (or recursion) — depth-first means diving deep
Track visited nodes to avoid infinite loops
Ideal for problems where you need to explore **all** possibilities
Can be adapted to grids, graphs, trees, or implicit state spaces

Breadth-First Search (BFS)

Purpose

Explore nodes or states level by level, starting from a root or source. BFS guarantees the shortest path in unweighted graphs and is ideal for problems involving proximity, reachability, or layered expansion.

More Visual

Basically we search the tree level by level. Here are some terms

And this is a clearer (hopefully) image showing the approach.

Concept

Use a queue to process nodes in the order they’re discovered:

Start from a source node
Visit all immediate neighbors before moving deeper
Track visited nodes to avoid cycles or redundant work

Common Use Cases

Shortest path in unweighted graphs
Level-order traversal of trees
Finding connected components
Maze solving (minimum steps)
Social network expansion (e.g., friend-of-friend)

Example: Shortest Path in Unweighted Graph (TypeScript)

function bfsShortestPath(graph: Map<number, number[]>, start: number, target: number): number {
  const visited = new Set<number>();
  const queue: [number, number][] = [[start, 0]]; // [node, distance]

  while (queue.length > 0) {
    // Remove and return first in queue
    const [node, dist] = queue.shift()!;

    // If node == target return
    if (node === target) return dist;

    // If node already exists continue
    if (visited.has(node)) continue;

    // Else add Node
    visited.add(node);

    // Iterate over neighbours and push onto queue (visited)
    for (const neighbours of graph.get(node) || []) {
      queue.push([neighbor, dist + 1]);
    }
  }

  return -1; // target not reachable
}

Why It Works

Queue ensures nodes are processed in order of discovery
Guarantees shortest path in unweighted graphs
Avoids revisiting nodes via a visited set
Naturally fits problems with layered or radial expansion

Variants

Level-order traversal in binary trees
Multi-source BFS (e.g., fire spread from multiple points)
Bidirectional BFS (search from both ends)
BFS with state tracking (e.g., grid + keys collected)

Notes

Use a queue, not a stack — order matters
Track visited nodes to prevent infinite loops
For weighted graphs, use Dijkstra’s algorithm instead
Can be adapted to grids, trees, graphs, or even implicit state spaces

BFS vs DFS Comparison

Feature	Breadth-First Search (BFS)	Depth-First Search (DFS)
Traversal Order	Level by level	Deep into one branch before backtracking
Data Structure	Queue (FIFO)	Stack (explicit or via recursion)
Use Case Example	Find shortest path in an unweighted graph	Detect cycles or explore all paths
Real-World Analogy	Ripples from a stone in a pond	Maze solving by going as far as possible before turning back
Guarantees Shortest Path?	✅ Yes (in unweighted graphs)	❌ No
Memory Usage	Can be high (stores all nodes at current level)	Often lower (stores one path at a time)
Common Problems	Level-order traversal, shortest path, friend-of-friend expansion	Topological sort, cycle detection, puzzle solving
Grid Traversal Behavior	Expands outward evenly	Dives deep into one direction
Recursive?	Rarely (usually iterative with queue)	Often recursive
Suitable For Large Graphs?	Yes, if depth is shallow	Yes, if depth is manageable
Example Question	"Find the shortest path from A to B in a maze"	"Find all paths from A to B in a maze"
Failure Mode	Can consume lots of memory if graph is wide	Can hit recursion limits if graph is deep

Matrix Traversal

Backtracking

DP Patterns

Summary

Here is a quick table

Pattern	Example Question	Core Insight	Real-World Analogy
Prefix Sum	"Given an array, find the sum of elements between indices i and j in constant time."	Precompute cumulative totals to answer range queries fast.	Running total on a spreadsheet column.
Two Pointer Pattern	"Find if any two numbers in a sorted array sum to a target."	Use two indices moving inward to reduce search space.	Scanning a sorted guest list from both ends.
Sliding Window Pattern	"Find the longest substring with at most K distinct characters."	Maintain a moving window to track dynamic subarrays.	Monitoring bandwidth usage over the last 5 minutes.
Fast and Slow Pointer	"Detect if a linked list has a cycle."	Use two pointers at different speeds to detect loops.	Two runners on a circular track — one eventually laps the other.
In-Place Reversal	"Reverse a linked list or array without extra space."	Swap elements directly to conserve memory.	Flipping a pancake stack without using another plate.
Monotonic Stack	"Find the next greater element for each item in an array."	Use a stack that maintains increasing or decreasing order.	Tracking temperature spikes — discard cooler days.
Top K Elements	"Find the K largest numbers in a stream."	Use a heap or priority queue to maintain top values.	Keeping top 10 scores on a leaderboard.
Overlapping Intervals	"Merge overlapping meeting times."	Sort and merge intervals based on start/end.	Scheduling rooms for overlapping bookings.
Binary Search	"Find a target in a sorted array."	Divide and conquer by halving the search space.	Looking up a name in a phone book.
Modified Binary Search	"Find the minimum in a rotated sorted array."	Binary search with logic to handle disrupted order.	Searching a rotated clock face for noon.
Tree Traversal	"Print all nodes in a binary tree in-order."	Visit nodes in a structured sequence.	Walking through a nested folder structure.
DFS (Depth-First Search)	"Find all paths from root to leaf in a tree."	Explore one branch deeply before backtracking.	Maze solving by going as far as possible before turning back.
BFS (Breadth-First Search)	"Find the shortest path in an unweighted graph."	Explore all neighbors level by level.	Ripples spreading from a stone in a pond.
Matrix Traversal	"Search for a value in a 2D grid."	Navigate rows and columns with bounds checks.	Scanning a spreadsheet for a keyword.
Backtracking	"Solve a Sudoku puzzle."	Try, fail, and undo — recursively explore options.	Lock picking by trying combinations and rewinding.
DP Patterns	"Find the minimum cost to climb stairs with variable steps."	Break problems into overlapping subproblems with memoization.	Budgeting monthly expenses by reusing past calculations.

LeetCode Patterns

Introduction

A Picture Says A Thousands Words

Prefix Sum

Purpose

Concept

Implementation (JavaScript)

Example

Adding 0

Use Cases

Notes

Two Pointer Pattern

Purpose

Concept

Common Use Cases

Example: Pair Sum in Sorted Array

Implementation (Rust)

Why It Works

Variants

Speed Comparison

Notes

Sliding Window Pattern

Purpose

Concept

Common Use Cases

Example: Max Sum of Subarray of Size k

Why It Works

Variants

Notes

Related Patterns

Fast and Slow Pointer Pattern

Purpose

Concept

General Algorithm

Example: Cycle Detection in Linked List

Example: Finding Middle of Linked List

Time and Space Complexity

Related Patterns

Notes

See Also

In-Place Reversal Pattern

Purpose

Concept

General Algorithm

Example: Reverse Array In-Place

Example: Reverse String In-Place (Rust)

Example: Reverse String In-Place (C#)

Example: Carousel

Time and Space Complexity

Use Cases

Related Patterns

Notes

Monotonic Stack Pattern

Purpose

Concept

General Algorithm

Example: Next Greater Element

Time and Space Complexity

Use Cases

Related Patterns

Notes

Top K Elements

Purpose

Concept

Common Use Cases

Example (Typescript)

Why It Works

Variants

Notes

Overlapping Intervals

Purpose

Concept

Common Use Cases

Example: Merge Overlapping Intervals (TypeScript)

Why It Works

Variants

Notes

Binary Search

Purpose

Concept