Vivek Kaushik
AboutBlogWorkMy Work Ethics
DSA Patterns

DSA Patterns

Created
Feb 21, 2026 01:53 AM
Tags

1️⃣ HashMap / Frequency Counting Pattern

Used In

  • Two Sum
  • Valid Anagram
  • Contains Duplicate
  • Top K Frequent

Core Idea

Store counts or seen values to reduce nested loops.

Template – Frequency Count

var freq = new Dictionary<int, int>();

foreach (var num in nums)
    freq[num] = freq.GetValueOrDefault(num) + 1;
Time: O(n)
Space: O(n)

2️⃣ Sliding Window (Variable Size)

Used In

  • Longest Substring Without Repeating Characters

Core Idea

Maintain window [left, right] and expand right.
Shrink from left when condition breaks.

Template

int left = 0;
var map = new Dictionary<char, int>();

for (int right = 0; right < s.Length; right++) {
    if (map.TryGetValue(s[right], out int index)) {
        left = Math.Max(left, index + 1);
    }
    map[s[right]] = right;
    max = Math.Max(max, right - left + 1);
}
Invariant:
Window always valid (no duplicates).
Time: O(n)
Space: O(n)

3️⃣ Prefix Sum + HashMap

Used In

  • Subarray Sum Equals K

Core Idea

If prefixSum - k exists before, subarray found.

Template

var dict = new Dictionary<int, int>();
dict[0] = 1;

int sum = 0;
int count = 0;

foreach (var num in nums) {
    sum += num;

    if (dict.TryGetValue(sum - k, out int freq))
        count += freq;

    dict[sum] = dict.GetValueOrDefault(sum) + 1;
}
Invariant:
Store frequency of prefix sums.
Time: O(n)
Space: O(n)

4️⃣ Two Pointers – Sorted Array

Used In

  • 3Sum
  • Merge Intervals (after sorting)

Core Idea

Sort first. Move pointers inward based on comparison.

3Sum Skeleton

Array.Sort(nums);

for (int i = 0; i < nums.Length - 2; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) continue;

    int left = i + 1;
    int right = nums.Length - 1;

    while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];

        if (sum == 0) {
            // record
            left++;
            right--;
        }
        else if (sum < 0)
            left++;
        else
            right--;
    }
}
Time: O(n^2)

5️⃣ Binary Search (Classic)

Used In

  • Binary Search (#704)
  • Search in sorted arrays
  • Lower/Upper bound problems

Core Idea

Search space is sorted. At each step, eliminate half of the array.
Invariant: If target exists, it must lie within [left, right].

Template

int left = 0;
int right = nums.Length - 1;

while (left <= right) {
    int mid = left + (right - left) / 2;

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

return -1;
Time: O(log n)
Space: O(1)

6️⃣ Binary Search – Rotated Sorted Array

Used In

  • Search in Rotated Sorted Array (#33)

Core Idea

Even after rotation, at least one half (left or right of mid) is always sorted.
Use that sorted half to decide where the target must lie.
Invariant:
One half is sorted at every step.

Template

while (left <= right) {
    int mid = left + (right - left) / 2;

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

    if (nums[left] <= nums[mid]) {
        if (target >= nums[left] && target < nums[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    else {
        if (target > nums[mid] && target <= nums[right])
            left = mid + 1;
        else
            right = mid - 1;
    }
}
Time: O(log n)
Space: O(1)

7️⃣ Linked List – Iterative Reverse

Used In

  • Reverse Linked List (#206)

Core Idea

Reverse pointers one by one while preserving next reference.
Invariant: prev always points to reversed portion.

Template

ListNode prev = null;
ListNode curr = head;

while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
}

return prev;
Time: O(n)
Space: O(1)

8️⃣ Tree – DFS (Recursive Template)

Used In

  • Maximum Depth (#104)
  • Validate BST (#98)
  • LCA (#236)

Core Idea

Solve subproblems on left and right subtree recursively.
Invariant: Each recursive call solves a smaller subtree.

Template

bool DFS(TreeNode node) {
    if (node == null) return true;

    bool left = DFS(node.left);
    bool right = DFS(node.right);

    return left && right;
}
Time: O(n)
Space: O(h) where h = tree height

9️⃣ Validate BST

Used In

  • Validate Binary Search Tree (#98)

Core Idea

Each node must lie within a valid range (min, max).
Pass constraints down recursively.
Invariant:
All left subtree values < node.val < all right subtree values.
bool IsValid(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;

    return IsValid(node.left, min, node.val)
        && IsValid(node.right, node.val, max);
}
Time: O(n)
Space: O(h)

🔟 Level Order Traversal (BFS)

Used In

  • Binary Tree Level Order Traversal (#102)

Core Idea

Use queue to process tree level by level.
Process all nodes at current level before moving deeper.

Template

var queue = new Queue<TreeNode>();
queue.Enqueue(root);

while (queue.Count > 0) {
    int size = queue.Count;

    for (int i = 0; i < size; i++) {
        var node = queue.Dequeue();

        if (node.left != null) queue.Enqueue(node.left);
        if (node.right != null) queue.Enqueue(node.right);
    }
}
Time: O(n)
Space: O(n)

1️⃣1️⃣ Backtracking – Subsets

Used In

  • Subsets (#78)
  • Combination Sum (#39)

Core Idea

For each element, choose include or exclude.
Explore decision tree fully.
Invariant:
Undo choice after recursive call (backtrack step).

Template

void Backtrack(int index, List<int> current) {
    if (index == nums.Length) {
        result.Add(new List<int>(current));
        return;
    }

    current.Add(nums[index]);
    Backtrack(index + 1, current);
    current.RemoveAt(current.Count - 1);

    Backtrack(index + 1, current);
}
Time: O(2^n)
Space: O(n) recursion depth

1️⃣2️⃣ Heap – Top K Frequent

Used In

  • Top K Frequent Elements (#347)
  • Kth Largest Element

Core Idea

Maintain a min heap of size k.
Remove smallest when size exceeds k.
Invariant:
Heap always contains top k largest frequencies.

Template

var pq = new PriorityQueue<int, int>();

foreach (var entry in freq) {
    pq.Enqueue(entry.Key, entry.Value);
    if (pq.Count > k)
        pq.Dequeue();
}
Time: O(n log k)
Space: O(n)
 
Table of Contents
1️⃣ HashMap / Frequency Counting PatternUsed InCore IdeaTemplate – Frequency Count2️⃣ Sliding Window (Variable Size)Used InCore IdeaTemplate3️⃣ Prefix Sum + HashMapUsed InCore IdeaTemplate4️⃣ Two Pointers – Sorted ArrayUsed InCore Idea3Sum Skeleton5️⃣ Binary Search (Classic)Used InCore IdeaTemplate6️⃣ Binary Search – Rotated Sorted ArrayUsed InCore IdeaTemplate7️⃣ Linked List – Iterative ReverseUsed InCore IdeaTemplate8️⃣ Tree – DFS (Recursive Template)Used InCore IdeaTemplate9️⃣ Validate BSTUsed InCore Idea🔟 Level Order Traversal (BFS)Used InCore IdeaTemplate1️⃣1️⃣ Backtracking – SubsetsUsed InCore IdeaTemplate1️⃣2️⃣ Heap – Top K FrequentUsed InCore IdeaTemplate
Copyright 2026 Vivek Kaushik